./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 4fc63b2a Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/config/AutomizerReach.xml -i ../../sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU --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 22d9a6832a4080412e38f5d573b63985f3b10b3c2009b6559595c7c0bbda414f --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4fc63b2 [2024-10-31 21:59:20,836 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-31 21:59:20,923 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-31 21:59:20,929 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-31 21:59:20,931 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-31 21:59:20,966 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-31 21:59:20,967 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-31 21:59:20,968 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-31 21:59:20,968 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-31 21:59:20,970 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-31 21:59:20,970 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-31 21:59:20,970 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-31 21:59:20,971 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-31 21:59:20,973 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-31 21:59:20,974 INFO L153 SettingsManager]: * Use SBE=true [2024-10-31 21:59:20,974 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-31 21:59:20,974 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-31 21:59:20,975 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-31 21:59:20,975 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-31 21:59:20,975 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-31 21:59:20,979 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-31 21:59:20,980 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-31 21:59:20,980 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-31 21:59:20,980 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-31 21:59:20,981 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-31 21:59:20,981 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-31 21:59:20,981 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-31 21:59:20,981 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-31 21:59:20,982 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-31 21:59:20,982 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-31 21:59:20,982 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-31 21:59:20,982 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-31 21:59:20,983 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-31 21:59:20,983 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-31 21:59:20,983 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-31 21:59:20,983 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-31 21:59:20,984 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-31 21:59:20,984 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-31 21:59:20,984 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-31 21:59:20,984 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-31 21:59:20,985 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-31 21:59:20,985 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-31 21:59:20,985 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_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/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_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU 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 -> 22d9a6832a4080412e38f5d573b63985f3b10b3c2009b6559595c7c0bbda414f [2024-10-31 21:59:21,302 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-31 21:59:21,334 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-31 21:59:21,337 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-31 21:59:21,338 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-31 21:59:21,339 INFO L274 PluginConnector]: CDTParser initialized [2024-10-31 21:59:21,340 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/../../sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c Unable to find full path for "g++" [2024-10-31 21:59:23,533 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-31 21:59:23,887 INFO L384 CDTParser]: Found 1 translation units. [2024-10-31 21:59:23,888 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c [2024-10-31 21:59:23,899 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/data/276781ffc/d697e9316316486b9238e0ed7321bf2c/FLAG533bc05f1 [2024-10-31 21:59:23,922 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/data/276781ffc/d697e9316316486b9238e0ed7321bf2c [2024-10-31 21:59:23,926 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-31 21:59:23,928 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-31 21:59:23,932 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-31 21:59:23,933 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-31 21:59:23,939 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-31 21:59:23,940 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.10 09:59:23" (1/1) ... [2024-10-31 21:59:23,941 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@67515723 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:23, skipping insertion in model container [2024-10-31 21:59:23,944 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.10 09:59:23" (1/1) ... [2024-10-31 21:59:23,971 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-31 21:59:24,266 WARN L251 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_47f8d8d4-b355-4490-bb7e-0e98516fa004/sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c[946,959] [2024-10-31 21:59:24,272 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-31 21:59:24,300 INFO L200 MainTranslator]: Completed pre-run [2024-10-31 21:59:24,349 WARN L251 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_47f8d8d4-b355-4490-bb7e-0e98516fa004/sv-benchmarks/c/recursive-simple/fibo_2calls_4-2.c[946,959] [2024-10-31 21:59:24,349 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-31 21:59:24,392 INFO L204 MainTranslator]: Completed translation [2024-10-31 21:59:24,396 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24 WrapperNode [2024-10-31 21:59:24,396 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-31 21:59:24,397 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-31 21:59:24,397 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-31 21:59:24,398 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-31 21:59:24,410 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,416 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,430 INFO L138 Inliner]: procedures = 14, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2024-10-31 21:59:24,431 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-31 21:59:24,431 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-31 21:59:24,432 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-31 21:59:24,432 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-31 21:59:24,444 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,444 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,445 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,458 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-31 21:59:24,458 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,458 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,461 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,463 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,464 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,468 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,474 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-31 21:59:24,475 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-31 21:59:24,475 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-31 21:59:24,476 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-31 21:59:24,477 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (1/1) ... [2024-10-31 21:59:24,490 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-31 21:59:24,502 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:24,521 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-31 21:59:24,525 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-31 21:59:24,561 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-31 21:59:24,562 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-31 21:59:24,562 INFO L130 BoogieDeclarations]: Found specification of procedure fibo2 [2024-10-31 21:59:24,562 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo2 [2024-10-31 21:59:24,562 INFO L130 BoogieDeclarations]: Found specification of procedure fibo1 [2024-10-31 21:59:24,562 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo1 [2024-10-31 21:59:24,563 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-31 21:59:24,563 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-31 21:59:24,631 INFO L238 CfgBuilder]: Building ICFG [2024-10-31 21:59:24,633 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-31 21:59:24,808 INFO L? ?]: Removed 8 outVars from TransFormulas that were not future-live. [2024-10-31 21:59:24,808 INFO L287 CfgBuilder]: Performing block encoding [2024-10-31 21:59:24,821 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-31 21:59:24,821 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-31 21:59:24,821 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 09:59:24 BoogieIcfgContainer [2024-10-31 21:59:24,822 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-31 21:59:24,824 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-31 21:59:24,824 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-31 21:59:24,827 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-31 21:59:24,828 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 31.10 09:59:23" (1/3) ... [2024-10-31 21:59:24,829 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f1af497 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.10 09:59:24, skipping insertion in model container [2024-10-31 21:59:24,829 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 09:59:24" (2/3) ... [2024-10-31 21:59:24,829 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f1af497 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.10 09:59:24, skipping insertion in model container [2024-10-31 21:59:24,829 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 09:59:24" (3/3) ... [2024-10-31 21:59:24,831 INFO L112 eAbstractionObserver]: Analyzing ICFG fibo_2calls_4-2.c [2024-10-31 21:59:24,850 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-31 21:59:24,851 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-31 21:59:24,929 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-31 21:59:24,940 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@5f3b32c0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-31 21:59:24,941 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-31 21:59:24,946 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 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) [2024-10-31 21:59:24,963 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-10-31 21:59:24,963 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:24,965 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 21:59:24,966 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:24,976 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:24,977 INFO L85 PathProgramCache]: Analyzing trace with hash 1123300790, now seen corresponding path program 1 times [2024-10-31 21:59:24,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:24,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [774986819] [2024-10-31 21:59:24,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:24,990 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:25,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:25,222 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:25,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:25,296 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-31 21:59:25,297 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:25,297 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [774986819] [2024-10-31 21:59:25,298 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [774986819] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 21:59:25,298 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 21:59:25,298 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 21:59:25,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1345169521] [2024-10-31 21:59:25,301 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 21:59:25,306 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-31 21:59:25,306 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:25,328 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-31 21:59:25,328 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 21:59:25,330 INFO L87 Difference]: Start difference. First operand has 29 states, 20 states have (on average 1.3) internal successors, (26), 21 states have internal predecessors, (26), 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 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 21:59:25,397 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:25,397 INFO L93 Difference]: Finished difference Result 39 states and 48 transitions. [2024-10-31 21:59:25,401 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-31 21:59:25,404 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2024-10-31 21:59:25,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:25,413 INFO L225 Difference]: With dead ends: 39 [2024-10-31 21:59:25,413 INFO L226 Difference]: Without dead ends: 27 [2024-10-31 21:59:25,417 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 21:59:25,424 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:25,425 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 124 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-31 21:59:25,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-10-31 21:59:25,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-10-31 21:59:25,477 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-10-31 21:59:25,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2024-10-31 21:59:25,483 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 10 [2024-10-31 21:59:25,484 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:25,484 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2024-10-31 21:59:25,484 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 21:59:25,485 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2024-10-31 21:59:25,487 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-10-31 21:59:25,487 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:25,488 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 21:59:25,488 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-10-31 21:59:25,492 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:25,493 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:25,493 INFO L85 PathProgramCache]: Analyzing trace with hash 1177745932, now seen corresponding path program 1 times [2024-10-31 21:59:25,494 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:25,494 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [189290089] [2024-10-31 21:59:25,494 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:25,494 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:25,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:25,566 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:25,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:25,617 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-31 21:59:25,618 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:25,618 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [189290089] [2024-10-31 21:59:25,618 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [189290089] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 21:59:25,619 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 21:59:25,619 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 21:59:25,619 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [964353896] [2024-10-31 21:59:25,619 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 21:59:25,624 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-31 21:59:25,624 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:25,625 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-31 21:59:25,625 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 21:59:25,625 INFO L87 Difference]: Start difference. First operand 27 states and 34 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 21:59:25,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:25,669 INFO L93 Difference]: Finished difference Result 33 states and 41 transitions. [2024-10-31 21:59:25,669 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-31 21:59:25,670 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2024-10-31 21:59:25,670 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:25,671 INFO L225 Difference]: With dead ends: 33 [2024-10-31 21:59:25,672 INFO L226 Difference]: Without dead ends: 29 [2024-10-31 21:59:25,672 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 21:59:25,674 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 125 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 [2024-10-31 21:59:25,675 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 125 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-31 21:59:25,676 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-10-31 21:59:25,683 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 27. [2024-10-31 21:59:25,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 5 states have call successors, (5), 2 states have call predecessors, (5), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-10-31 21:59:25,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 34 transitions. [2024-10-31 21:59:25,685 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 34 transitions. Word has length 11 [2024-10-31 21:59:25,685 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:25,686 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 34 transitions. [2024-10-31 21:59:25,686 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 21:59:25,686 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 34 transitions. [2024-10-31 21:59:25,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-10-31 21:59:25,687 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:25,688 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 21:59:25,688 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-10-31 21:59:25,688 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:25,689 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:25,689 INFO L85 PathProgramCache]: Analyzing trace with hash 2110588723, now seen corresponding path program 1 times [2024-10-31 21:59:25,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:25,690 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2035917571] [2024-10-31 21:59:25,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:25,690 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:25,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:25,819 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:25,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:25,924 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:25,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:25,997 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-31 21:59:26,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:26,006 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-31 21:59:26,007 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:26,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2035917571] [2024-10-31 21:59:26,011 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2035917571] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 21:59:26,011 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [793800454] [2024-10-31 21:59:26,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:26,012 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:26,012 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:26,016 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 21:59:26,018 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-31 21:59:26,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:26,106 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-31 21:59:26,113 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 21:59:26,259 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-31 21:59:26,259 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 21:59:26,523 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-31 21:59:26,524 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [793800454] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 21:59:26,524 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 21:59:26,524 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7, 7] total 13 [2024-10-31 21:59:26,525 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [816145905] [2024-10-31 21:59:26,525 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 21:59:26,526 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-10-31 21:59:26,526 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:26,527 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-10-31 21:59:26,527 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2024-10-31 21:59:26,528 INFO L87 Difference]: Start difference. First operand 27 states and 34 transitions. Second operand has 13 states, 10 states have (on average 3.2) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2024-10-31 21:59:26,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:26,731 INFO L93 Difference]: Finished difference Result 55 states and 75 transitions. [2024-10-31 21:59:26,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-31 21:59:26,733 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 3.2) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) Word has length 23 [2024-10-31 21:59:26,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:26,734 INFO L225 Difference]: With dead ends: 55 [2024-10-31 21:59:26,734 INFO L226 Difference]: Without dead ends: 31 [2024-10-31 21:59:26,735 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2024-10-31 21:59:26,739 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 19 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 145 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 159 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 145 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:26,740 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 163 Invalid, 159 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 145 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-31 21:59:26,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-10-31 21:59:26,754 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 29. [2024-10-31 21:59:26,754 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 21 states have internal predecessors, (23), 5 states have call successors, (5), 2 states have call predecessors, (5), 4 states have return successors, (8), 5 states have call predecessors, (8), 5 states have call successors, (8) [2024-10-31 21:59:26,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 36 transitions. [2024-10-31 21:59:26,757 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 36 transitions. Word has length 23 [2024-10-31 21:59:26,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:26,758 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 36 transitions. [2024-10-31 21:59:26,758 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 3.2) internal successors, (32), 13 states have internal predecessors, (32), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2024-10-31 21:59:26,759 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 36 transitions. [2024-10-31 21:59:26,760 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-10-31 21:59:26,760 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:26,762 INFO L215 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] [2024-10-31 21:59:26,776 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-31 21:59:26,962 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:26,963 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:26,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:26,964 INFO L85 PathProgramCache]: Analyzing trace with hash 1277869167, now seen corresponding path program 1 times [2024-10-31 21:59:26,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:26,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1347280487] [2024-10-31 21:59:26,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:26,964 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:26,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:27,021 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:27,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:27,151 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:27,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:27,192 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-31 21:59:27,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:27,208 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-31 21:59:27,208 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:27,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1347280487] [2024-10-31 21:59:27,209 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1347280487] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 21:59:27,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [842864126] [2024-10-31 21:59:27,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:27,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:27,210 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:27,212 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 21:59:27,213 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-31 21:59:27,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:27,262 INFO L255 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-31 21:59:27,263 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 21:59:27,321 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-31 21:59:27,321 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 21:59:27,574 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-31 21:59:27,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [842864126] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 21:59:27,575 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 21:59:27,575 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 13 [2024-10-31 21:59:27,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [78218562] [2024-10-31 21:59:27,575 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 21:59:27,576 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-10-31 21:59:27,576 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:27,577 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-10-31 21:59:27,580 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2024-10-31 21:59:27,580 INFO L87 Difference]: Start difference. First operand 29 states and 36 transitions. Second operand has 13 states, 11 states have (on average 2.909090909090909) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (7), 1 states have call predecessors, (7), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-31 21:59:27,864 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:27,864 INFO L93 Difference]: Finished difference Result 53 states and 74 transitions. [2024-10-31 21:59:27,865 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-31 21:59:27,865 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.909090909090909) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (7), 1 states have call predecessors, (7), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) Word has length 24 [2024-10-31 21:59:27,865 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:27,869 INFO L225 Difference]: With dead ends: 53 [2024-10-31 21:59:27,872 INFO L226 Difference]: Without dead ends: 49 [2024-10-31 21:59:27,873 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 46 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2024-10-31 21:59:27,874 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 38 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 180 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 120 SdHoareTripleChecker+Invalid, 209 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 180 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:27,875 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 120 Invalid, 209 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 180 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-31 21:59:27,876 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-10-31 21:59:27,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 47. [2024-10-31 21:59:27,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 9 states have call successors, (9), 4 states have call predecessors, (9), 6 states have return successors, (17), 9 states have call predecessors, (17), 9 states have call successors, (17) [2024-10-31 21:59:27,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 65 transitions. [2024-10-31 21:59:27,899 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 65 transitions. Word has length 24 [2024-10-31 21:59:27,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:27,899 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 65 transitions. [2024-10-31 21:59:27,899 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.909090909090909) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (7), 1 states have call predecessors, (7), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-31 21:59:27,900 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 65 transitions. [2024-10-31 21:59:27,901 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-10-31 21:59:27,901 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:27,901 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 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] [2024-10-31 21:59:27,918 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-31 21:59:28,101 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-10-31 21:59:28,102 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:28,102 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:28,103 INFO L85 PathProgramCache]: Analyzing trace with hash -2061621832, now seen corresponding path program 1 times [2024-10-31 21:59:28,103 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:28,103 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1552727826] [2024-10-31 21:59:28,103 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:28,103 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:28,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:28,151 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:28,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:28,182 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:28,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:28,216 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:28,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:28,238 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-31 21:59:28,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:28,242 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-10-31 21:59:28,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:28,246 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 5 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-31 21:59:28,246 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:28,246 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1552727826] [2024-10-31 21:59:28,247 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1552727826] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 21:59:28,247 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1857093857] [2024-10-31 21:59:28,247 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:28,247 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:28,247 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:28,249 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 21:59:28,251 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-31 21:59:28,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:28,309 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-31 21:59:28,311 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 21:59:28,416 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-31 21:59:28,416 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 21:59:29,038 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-31 21:59:29,040 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1857093857] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 21:59:29,041 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 21:59:29,041 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 8, 9] total 15 [2024-10-31 21:59:29,041 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1763627466] [2024-10-31 21:59:29,042 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 21:59:29,044 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-31 21:59:29,044 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:29,045 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-31 21:59:29,048 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=169, Unknown=0, NotChecked=0, Total=210 [2024-10-31 21:59:29,049 INFO L87 Difference]: Start difference. First operand 47 states and 65 transitions. Second operand has 15 states, 12 states have (on average 3.9166666666666665) internal successors, (47), 15 states have internal predecessors, (47), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2024-10-31 21:59:29,384 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:29,384 INFO L93 Difference]: Finished difference Result 109 states and 177 transitions. [2024-10-31 21:59:29,385 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-10-31 21:59:29,385 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 12 states have (on average 3.9166666666666665) internal successors, (47), 15 states have internal predecessors, (47), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) Word has length 36 [2024-10-31 21:59:29,386 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:29,388 INFO L225 Difference]: With dead ends: 109 [2024-10-31 21:59:29,390 INFO L226 Difference]: Without dead ends: 65 [2024-10-31 21:59:29,391 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 75 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2024-10-31 21:59:29,393 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 32 mSDsluCounter, 143 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 238 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:29,395 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 164 Invalid, 238 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 205 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-31 21:59:29,396 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-10-31 21:59:29,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 63. [2024-10-31 21:59:29,419 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 41 states have (on average 1.2439024390243902) internal successors, (51), 44 states have internal predecessors, (51), 12 states have call successors, (12), 5 states have call predecessors, (12), 9 states have return successors, (29), 13 states have call predecessors, (29), 12 states have call successors, (29) [2024-10-31 21:59:29,421 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 92 transitions. [2024-10-31 21:59:29,421 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 92 transitions. Word has length 36 [2024-10-31 21:59:29,422 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:29,422 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 92 transitions. [2024-10-31 21:59:29,422 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 12 states have (on average 3.9166666666666665) internal successors, (47), 15 states have internal predecessors, (47), 11 states have call successors, (13), 1 states have call predecessors, (13), 5 states have return successors, (13), 3 states have call predecessors, (13), 11 states have call successors, (13) [2024-10-31 21:59:29,422 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 92 transitions. [2024-10-31 21:59:29,424 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-10-31 21:59:29,424 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:29,425 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 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] [2024-10-31 21:59:29,447 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-31 21:59:29,628 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:29,628 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:29,629 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:29,629 INFO L85 PathProgramCache]: Analyzing trace with hash 1167294498, now seen corresponding path program 1 times [2024-10-31 21:59:29,629 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:29,629 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [67720732] [2024-10-31 21:59:29,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:29,630 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:29,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:29,686 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:29,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:29,736 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:29,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:29,825 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:29,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:29,832 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-31 21:59:29,835 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:29,844 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-31 21:59:29,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:29,864 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-10-31 21:59:29,865 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:29,865 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [67720732] [2024-10-31 21:59:29,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [67720732] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 21:59:29,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [442270626] [2024-10-31 21:59:29,868 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:29,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:29,868 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:29,871 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 21:59:29,873 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-31 21:59:29,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:29,935 INFO L255 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-31 21:59:29,937 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 21:59:30,067 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-31 21:59:30,067 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 21:59:30,504 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-31 21:59:30,505 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [442270626] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 21:59:30,506 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 21:59:30,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 17 [2024-10-31 21:59:30,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759760480] [2024-10-31 21:59:30,506 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 21:59:30,507 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-10-31 21:59:30,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:30,508 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-10-31 21:59:30,509 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=220, Unknown=0, NotChecked=0, Total=272 [2024-10-31 21:59:30,510 INFO L87 Difference]: Start difference. First operand 63 states and 92 transitions. Second operand has 17 states, 16 states have (on average 3.0625) internal successors, (49), 17 states have internal predecessors, (49), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) [2024-10-31 21:59:30,934 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:30,934 INFO L93 Difference]: Finished difference Result 179 states and 325 transitions. [2024-10-31 21:59:30,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-31 21:59:30,935 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 3.0625) internal successors, (49), 17 states have internal predecessors, (49), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) Word has length 37 [2024-10-31 21:59:30,935 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:30,938 INFO L225 Difference]: With dead ends: 179 [2024-10-31 21:59:30,938 INFO L226 Difference]: Without dead ends: 119 [2024-10-31 21:59:30,940 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 77 SyntacticMatches, 4 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 92 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=102, Invalid=404, Unknown=0, NotChecked=0, Total=506 [2024-10-31 21:59:30,940 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 35 mSDsluCounter, 215 mSDsCounter, 0 mSdLazyCounter, 315 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 248 SdHoareTripleChecker+Invalid, 353 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:30,941 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 248 Invalid, 353 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 315 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-31 21:59:30,942 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2024-10-31 21:59:30,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 100. [2024-10-31 21:59:30,967 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 64 states have (on average 1.21875) internal successors, (78), 67 states have internal predecessors, (78), 21 states have call successors, (21), 7 states have call predecessors, (21), 14 states have return successors, (63), 25 states have call predecessors, (63), 21 states have call successors, (63) [2024-10-31 21:59:30,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 162 transitions. [2024-10-31 21:59:30,973 INFO L78 Accepts]: Start accepts. Automaton has 100 states and 162 transitions. Word has length 37 [2024-10-31 21:59:30,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:30,974 INFO L471 AbstractCegarLoop]: Abstraction has 100 states and 162 transitions. [2024-10-31 21:59:30,974 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 3.0625) internal successors, (49), 17 states have internal predecessors, (49), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (12), 6 states have call predecessors, (12), 10 states have call successors, (12) [2024-10-31 21:59:30,974 INFO L276 IsEmpty]: Start isEmpty. Operand 100 states and 162 transitions. [2024-10-31 21:59:30,980 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-10-31 21:59:30,980 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:30,981 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 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, 1, 1] [2024-10-31 21:59:31,006 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-31 21:59:31,181 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:31,181 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:31,182 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:31,182 INFO L85 PathProgramCache]: Analyzing trace with hash 384535367, now seen corresponding path program 1 times [2024-10-31 21:59:31,182 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:31,182 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [340192933] [2024-10-31 21:59:31,182 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:31,183 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:31,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,238 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:31,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,275 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:31,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,310 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:31,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,370 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:31,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,376 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-31 21:59:31,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,381 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-31 21:59:31,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,404 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2024-10-31 21:59:31,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,407 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 15 proven. 4 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-31 21:59:31,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:31,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [340192933] [2024-10-31 21:59:31,407 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [340192933] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 21:59:31,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2018406619] [2024-10-31 21:59:31,408 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:31,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:31,408 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:31,410 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 21:59:31,417 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-31 21:59:31,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:31,479 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-31 21:59:31,481 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 21:59:31,579 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 12 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-10-31 21:59:31,579 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 21:59:31,981 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 12 proven. 13 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-10-31 21:59:31,981 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2018406619] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 21:59:31,982 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 21:59:31,982 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 9] total 16 [2024-10-31 21:59:31,982 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [618513421] [2024-10-31 21:59:31,982 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 21:59:31,983 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-10-31 21:59:31,983 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:31,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-10-31 21:59:31,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=189, Unknown=0, NotChecked=0, Total=240 [2024-10-31 21:59:31,985 INFO L87 Difference]: Start difference. First operand 100 states and 162 transitions. Second operand has 16 states, 15 states have (on average 3.533333333333333) internal successors, (53), 16 states have internal predecessors, (53), 10 states have call successors, (15), 1 states have call predecessors, (15), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2024-10-31 21:59:32,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:32,327 INFO L93 Difference]: Finished difference Result 262 states and 510 transitions. [2024-10-31 21:59:32,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-10-31 21:59:32,328 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 3.533333333333333) internal successors, (53), 16 states have internal predecessors, (53), 10 states have call successors, (15), 1 states have call predecessors, (15), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) Word has length 51 [2024-10-31 21:59:32,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:32,336 INFO L225 Difference]: With dead ends: 262 [2024-10-31 21:59:32,336 INFO L226 Difference]: Without dead ends: 165 [2024-10-31 21:59:32,337 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 109 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=79, Invalid=301, Unknown=0, NotChecked=0, Total=380 [2024-10-31 21:59:32,338 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 30 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 286 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 191 SdHoareTripleChecker+Invalid, 322 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 286 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:32,340 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 191 Invalid, 322 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 286 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-31 21:59:32,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 165 states. [2024-10-31 21:59:32,394 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 165 to 139. [2024-10-31 21:59:32,395 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 89 states have (on average 1.202247191011236) internal successors, (107), 91 states have internal predecessors, (107), 31 states have call successors, (31), 10 states have call predecessors, (31), 18 states have return successors, (103), 37 states have call predecessors, (103), 31 states have call successors, (103) [2024-10-31 21:59:32,397 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 241 transitions. [2024-10-31 21:59:32,398 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 241 transitions. Word has length 51 [2024-10-31 21:59:32,400 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:32,401 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 241 transitions. [2024-10-31 21:59:32,401 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 3.533333333333333) internal successors, (53), 16 states have internal predecessors, (53), 10 states have call successors, (15), 1 states have call predecessors, (15), 6 states have return successors, (17), 9 states have call predecessors, (17), 10 states have call successors, (17) [2024-10-31 21:59:32,401 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 241 transitions. [2024-10-31 21:59:32,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-10-31 21:59:32,406 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:32,406 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 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] [2024-10-31 21:59:32,428 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-10-31 21:59:32,611 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:32,611 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:32,611 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:32,611 INFO L85 PathProgramCache]: Analyzing trace with hash -1130362923, now seen corresponding path program 1 times [2024-10-31 21:59:32,612 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:32,612 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1640275207] [2024-10-31 21:59:32,612 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:32,612 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:32,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,669 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:32,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,720 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:32,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,793 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:32,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,900 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:32,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,908 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-31 21:59:32,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,916 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-31 21:59:32,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,926 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-31 21:59:32,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:32,946 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 19 proven. 11 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-10-31 21:59:32,947 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:32,947 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1640275207] [2024-10-31 21:59:32,947 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1640275207] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 21:59:32,947 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1301112028] [2024-10-31 21:59:32,948 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:32,948 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:32,948 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:32,950 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 21:59:32,951 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-31 21:59:33,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:33,013 INFO L255 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-31 21:59:33,015 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 21:59:33,086 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-10-31 21:59:33,087 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 21:59:33,350 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 18 proven. 5 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-10-31 21:59:33,351 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1301112028] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 21:59:33,351 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 21:59:33,351 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 7, 7] total 17 [2024-10-31 21:59:33,351 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [629377825] [2024-10-31 21:59:33,351 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 21:59:33,352 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-10-31 21:59:33,352 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:33,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-10-31 21:59:33,354 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=220, Unknown=0, NotChecked=0, Total=272 [2024-10-31 21:59:33,354 INFO L87 Difference]: Start difference. First operand 139 states and 241 transitions. Second operand has 17 states, 16 states have (on average 3.3125) internal successors, (53), 17 states have internal predecessors, (53), 8 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (16), 10 states have call predecessors, (16), 8 states have call successors, (16) [2024-10-31 21:59:33,754 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:33,754 INFO L93 Difference]: Finished difference Result 344 states and 697 transitions. [2024-10-31 21:59:33,755 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-10-31 21:59:33,755 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 16 states have (on average 3.3125) internal successors, (53), 17 states have internal predecessors, (53), 8 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (16), 10 states have call predecessors, (16), 8 states have call successors, (16) Word has length 52 [2024-10-31 21:59:33,755 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:33,758 INFO L225 Difference]: With dead ends: 344 [2024-10-31 21:59:33,758 INFO L226 Difference]: Without dead ends: 117 [2024-10-31 21:59:33,762 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 109 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 80 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=92, Invalid=370, Unknown=0, NotChecked=0, Total=462 [2024-10-31 21:59:33,763 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 36 mSDsluCounter, 194 mSDsCounter, 0 mSdLazyCounter, 348 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 227 SdHoareTripleChecker+Invalid, 382 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 348 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:33,763 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 227 Invalid, 382 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 348 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-10-31 21:59:33,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-10-31 21:59:33,793 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 94. [2024-10-31 21:59:33,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 61 states have (on average 1.180327868852459) internal successors, (72), 62 states have internal predecessors, (72), 20 states have call successors, (20), 7 states have call predecessors, (20), 12 states have return successors, (64), 24 states have call predecessors, (64), 20 states have call successors, (64) [2024-10-31 21:59:33,795 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 156 transitions. [2024-10-31 21:59:33,798 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 156 transitions. Word has length 52 [2024-10-31 21:59:33,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:33,798 INFO L471 AbstractCegarLoop]: Abstraction has 94 states and 156 transitions. [2024-10-31 21:59:33,799 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 16 states have (on average 3.3125) internal successors, (53), 17 states have internal predecessors, (53), 8 states have call successors, (14), 1 states have call predecessors, (14), 6 states have return successors, (16), 10 states have call predecessors, (16), 8 states have call successors, (16) [2024-10-31 21:59:33,799 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 156 transitions. [2024-10-31 21:59:33,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2024-10-31 21:59:33,801 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:33,801 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 21:59:33,827 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-10-31 21:59:34,005 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:34,005 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:34,005 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:34,006 INFO L85 PathProgramCache]: Analyzing trace with hash -492645000, now seen corresponding path program 2 times [2024-10-31 21:59:34,006 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:34,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [916256648] [2024-10-31 21:59:34,006 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:34,006 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:34,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,076 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 21:59:34,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,155 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:34,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,214 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:34,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,264 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:34,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,286 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-31 21:59:34,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,291 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-10-31 21:59:34,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,297 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-10-31 21:59:34,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,326 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 21:59:34,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,345 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-10-31 21:59:34,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 21:59:34,385 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 37 proven. 23 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-10-31 21:59:34,385 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 21:59:34,385 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [916256648] [2024-10-31 21:59:34,386 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [916256648] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 21:59:34,386 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [97559465] [2024-10-31 21:59:34,386 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-31 21:59:34,386 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:34,386 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 21:59:34,388 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 21:59:34,390 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-31 21:59:34,461 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-31 21:59:34,461 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-31 21:59:34,462 INFO L255 TraceCheckSpWp]: Trace formula consists of 166 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-31 21:59:34,464 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 21:59:34,575 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 38 proven. 8 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-31 21:59:34,575 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 21:59:35,042 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 38 proven. 9 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2024-10-31 21:59:35,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [97559465] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 21:59:35,043 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 21:59:35,043 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 8, 9] total 22 [2024-10-31 21:59:35,044 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1617868362] [2024-10-31 21:59:35,044 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 21:59:35,044 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-10-31 21:59:35,045 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 21:59:35,046 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-10-31 21:59:35,046 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=389, Unknown=0, NotChecked=0, Total=462 [2024-10-31 21:59:35,046 INFO L87 Difference]: Start difference. First operand 94 states and 156 transitions. Second operand has 22 states, 21 states have (on average 3.2857142857142856) internal successors, (69), 22 states have internal predecessors, (69), 12 states have call successors, (19), 1 states have call predecessors, (19), 9 states have return successors, (22), 14 states have call predecessors, (22), 12 states have call successors, (22) [2024-10-31 21:59:35,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 21:59:35,576 INFO L93 Difference]: Finished difference Result 189 states and 336 transitions. [2024-10-31 21:59:35,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-10-31 21:59:35,577 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 3.2857142857142856) internal successors, (69), 22 states have internal predecessors, (69), 12 states have call successors, (19), 1 states have call predecessors, (19), 9 states have return successors, (22), 14 states have call predecessors, (22), 12 states have call successors, (22) Word has length 66 [2024-10-31 21:59:35,577 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 21:59:35,579 INFO L225 Difference]: With dead ends: 189 [2024-10-31 21:59:35,579 INFO L226 Difference]: Without dead ends: 86 [2024-10-31 21:59:35,580 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 139 SyntacticMatches, 4 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 218 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=168, Invalid=824, Unknown=0, NotChecked=0, Total=992 [2024-10-31 21:59:35,581 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 65 mSDsluCounter, 237 mSDsCounter, 0 mSdLazyCounter, 460 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 266 SdHoareTripleChecker+Invalid, 516 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 460 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-31 21:59:35,581 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 266 Invalid, 516 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 460 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-31 21:59:35,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-10-31 21:59:35,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 77. [2024-10-31 21:59:35,591 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 53 states have (on average 1.150943396226415) internal successors, (61), 52 states have internal predecessors, (61), 12 states have call successors, (12), 8 states have call predecessors, (12), 11 states have return successors, (31), 16 states have call predecessors, (31), 12 states have call successors, (31) [2024-10-31 21:59:35,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 104 transitions. [2024-10-31 21:59:35,592 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 104 transitions. Word has length 66 [2024-10-31 21:59:35,594 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 21:59:35,596 INFO L471 AbstractCegarLoop]: Abstraction has 77 states and 104 transitions. [2024-10-31 21:59:35,597 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 3.2857142857142856) internal successors, (69), 22 states have internal predecessors, (69), 12 states have call successors, (19), 1 states have call predecessors, (19), 9 states have return successors, (22), 14 states have call predecessors, (22), 12 states have call successors, (22) [2024-10-31 21:59:35,597 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 104 transitions. [2024-10-31 21:59:35,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-10-31 21:59:35,598 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 21:59:35,598 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 21:59:35,617 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-31 21:59:35,798 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 21:59:35,799 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 21:59:35,800 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 21:59:35,800 INFO L85 PathProgramCache]: Analyzing trace with hash 780870354, now seen corresponding path program 1 times [2024-10-31 21:59:35,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 21:59:35,800 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1834552538] [2024-10-31 21:59:35,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 21:59:35,801 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 21:59:35,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 21:59:35,813 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 21:59:35,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 21:59:35,848 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 21:59:35,849 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-10-31 21:59:35,850 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-10-31 21:59:35,852 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-10-31 21:59:35,855 INFO L407 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 21:59:35,894 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-10-31 21:59:35,898 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 31.10 09:59:35 BoogieIcfgContainer [2024-10-31 21:59:35,898 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-10-31 21:59:35,899 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-31 21:59:35,899 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-31 21:59:35,899 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-31 21:59:35,899 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 09:59:24" (3/4) ... [2024-10-31 21:59:35,900 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-10-31 21:59:35,962 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/witness.graphml [2024-10-31 21:59:35,962 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-31 21:59:35,963 INFO L158 Benchmark]: Toolchain (without parser) took 12035.02ms. Allocated memory was 144.7MB in the beginning and 184.5MB in the end (delta: 39.8MB). Free memory was 112.4MB in the beginning and 128.9MB in the end (delta: -16.5MB). Peak memory consumption was 24.9MB. Max. memory is 16.1GB. [2024-10-31 21:59:35,963 INFO L158 Benchmark]: CDTParser took 0.34ms. Allocated memory is still 144.7MB. Free memory is still 113.3MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-31 21:59:35,963 INFO L158 Benchmark]: CACSL2BoogieTranslator took 464.87ms. Allocated memory is still 144.7MB. Free memory was 112.4MB in the beginning and 100.4MB in the end (delta: 12.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-31 21:59:35,964 INFO L158 Benchmark]: Boogie Procedure Inliner took 33.66ms. Allocated memory is still 144.7MB. Free memory was 99.8MB in the beginning and 98.7MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-31 21:59:35,964 INFO L158 Benchmark]: Boogie Preprocessor took 42.97ms. Allocated memory is still 144.7MB. Free memory was 98.7MB in the beginning and 97.2MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-31 21:59:35,964 INFO L158 Benchmark]: RCFGBuilder took 346.48ms. Allocated memory is still 144.7MB. Free memory was 97.2MB in the beginning and 86.2MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-31 21:59:35,964 INFO L158 Benchmark]: TraceAbstraction took 11074.33ms. Allocated memory was 144.7MB in the beginning and 184.5MB in the end (delta: 39.8MB). Free memory was 85.7MB in the beginning and 132.1MB in the end (delta: -46.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-31 21:59:35,965 INFO L158 Benchmark]: Witness Printer took 63.78ms. Allocated memory is still 184.5MB. Free memory was 132.1MB in the beginning and 128.9MB in the end (delta: 3.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-10-31 21:59:35,966 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.34ms. Allocated memory is still 144.7MB. Free memory is still 113.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 464.87ms. Allocated memory is still 144.7MB. Free memory was 112.4MB in the beginning and 100.4MB in the end (delta: 12.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 33.66ms. Allocated memory is still 144.7MB. Free memory was 99.8MB in the beginning and 98.7MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 42.97ms. Allocated memory is still 144.7MB. Free memory was 98.7MB in the beginning and 97.2MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 346.48ms. Allocated memory is still 144.7MB. Free memory was 97.2MB in the beginning and 86.2MB in the end (delta: 11.0MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 11074.33ms. Allocated memory was 144.7MB in the beginning and 184.5MB in the end (delta: 39.8MB). Free memory was 85.7MB in the beginning and 132.1MB in the end (delta: -46.4MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 63.78ms. Allocated memory is still 184.5MB. Free memory was 132.1MB in the beginning and 128.9MB in the end (delta: 3.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 41]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L38] int x = 4; VAL [x=4] [L39] CALL, EXPR fibo1(x) VAL [\old(n)=4] [L10] COND FALSE !(n < 1) VAL [\old(n)=4, n=4] [L12] COND FALSE !(n == 1) VAL [\old(n)=4, n=4] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=3] [L20] COND FALSE !(n < 1) VAL [\old(n)=3, n=3] [L22] COND FALSE !(n == 1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=2] [L10] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L12] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-1) VAL [\old(n)=1] [L20] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L22] COND TRUE n == 1 [L23] return 1; VAL [\old(n)=1, \result=1] [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=2, n=2] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=0] [L20] COND TRUE n < 1 [L21] return 0; VAL [\old(n)=0, \result=0] [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=2, n=2] [L15] return fibo2(n-1) + fibo2(n-2); [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=3, n=3] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=3, n=3] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-1) VAL [\old(n)=4, n=4] [L15] CALL, EXPR fibo2(n-2) VAL [\old(n)=2] [L20] COND FALSE !(n < 1) VAL [\old(n)=2, n=2] [L22] COND FALSE !(n == 1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-1) VAL [\old(n)=1] [L10] COND FALSE !(n < 1) VAL [\old(n)=1, n=1] [L12] COND TRUE n == 1 [L13] return 1; VAL [\old(n)=1, \result=1] [L25] RET, EXPR fibo1(n-1) VAL [\old(n)=2, n=2] [L25] CALL, EXPR fibo1(n-2) VAL [\old(n)=0] [L10] COND TRUE n < 1 [L11] return 0; VAL [\old(n)=0, \result=0] [L25] RET, EXPR fibo1(n-2) VAL [\old(n)=2, n=2] [L25] return fibo1(n-1) + fibo1(n-2); [L15] RET, EXPR fibo2(n-2) VAL [\old(n)=4, n=4] [L15] return fibo2(n-1) + fibo2(n-2); [L39] RET, EXPR fibo1(x) VAL [x=4] [L39] int result = fibo1(x); [L40] COND TRUE result == 3 VAL [x=4] [L41] reach_error() VAL [x=4] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 11.0s, OverallIterations: 10, TraceHistogramMax: 5, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 2.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 311 SdHoareTripleChecker+Valid, 1.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 255 mSDsluCounter, 1628 SdHoareTripleChecker+Invalid, 1.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1373 mSDsCounter, 240 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1963 IncrementalHoareTripleChecker+Invalid, 2203 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 240 mSolverCounterUnsat, 255 mSDtfsCounter, 1963 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 768 GetRequests, 607 SyntacticMatches, 22 SemanticMatches, 139 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 557 ImplicationChecksByTransitivity, 1.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=139occurred in iteration=7, InterpolantAutomatonStates: 112, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 85 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 5.5s InterpolantComputationTime, 664 NumberOfCodeBlocks, 664 NumberOfCodeBlocksAsserted, 18 NumberOfCheckSat, 865 ConstructedInterpolants, 0 QuantifiedInterpolants, 1861 SizeOfPredicates, 12 NumberOfNonLiveVariables, 780 ConjunctsInSsa, 50 ConjunctsInUnsatCore, 23 InterpolantComputations, 2 PerfectInterpolantSequences, 494/648 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-10-31 21:59:36,004 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47f8d8d4-b355-4490-bb7e-0e98516fa004/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE