./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound2.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_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/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_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/config/AutomizerReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound2.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/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_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/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 e89b4ab54b22145b4041cfb458aca993f2d791ac86940dcd03d48a90a5273393 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4fc63b2 [2024-10-31 22:18:44,092 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-31 22:18:44,198 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-31 22:18:44,206 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-31 22:18:44,207 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-31 22:18:44,239 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-31 22:18:44,240 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-31 22:18:44,240 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-31 22:18:44,241 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-31 22:18:44,242 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-31 22:18:44,242 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-31 22:18:44,243 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-31 22:18:44,243 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-31 22:18:44,244 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-31 22:18:44,244 INFO L153 SettingsManager]: * Use SBE=true [2024-10-31 22:18:44,245 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-31 22:18:44,245 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-31 22:18:44,246 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-31 22:18:44,247 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-31 22:18:44,247 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-31 22:18:44,247 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-31 22:18:44,248 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-31 22:18:44,248 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-31 22:18:44,249 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-31 22:18:44,249 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-31 22:18:44,249 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-31 22:18:44,250 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-31 22:18:44,250 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-31 22:18:44,251 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-31 22:18:44,251 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-31 22:18:44,251 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-31 22:18:44,252 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-31 22:18:44,252 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-31 22:18:44,253 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-31 22:18:44,253 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-31 22:18:44,253 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-31 22:18:44,254 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-31 22:18:44,254 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-31 22:18:44,254 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-31 22:18:44,255 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-31 22:18:44,255 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-31 22:18:44,256 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-31 22:18:44,256 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_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/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_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/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 -> e89b4ab54b22145b4041cfb458aca993f2d791ac86940dcd03d48a90a5273393 [2024-10-31 22:18:44,520 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-31 22:18:44,552 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-31 22:18:44,555 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-31 22:18:44,557 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-31 22:18:44,557 INFO L274 PluginConnector]: CDTParser initialized [2024-10-31 22:18:44,559 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/../../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound2.c Unable to find full path for "g++" [2024-10-31 22:18:46,678 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-31 22:18:46,864 INFO L384 CDTParser]: Found 1 translation units. [2024-10-31 22:18:46,865 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound2.c [2024-10-31 22:18:46,872 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/data/35ff5bae1/7e92849b869d4e229a6f4943360aa26b/FLAG46b526e4c [2024-10-31 22:18:46,885 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/data/35ff5bae1/7e92849b869d4e229a6f4943360aa26b [2024-10-31 22:18:46,888 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-31 22:18:46,889 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-31 22:18:46,890 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-31 22:18:46,890 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-31 22:18:46,896 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-31 22:18:46,900 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.10 10:18:46" (1/1) ... [2024-10-31 22:18:46,902 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@506d1094 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:46, skipping insertion in model container [2024-10-31 22:18:46,902 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.10 10:18:46" (1/1) ... [2024-10-31 22:18:46,930 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-31 22:18:47,123 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_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound2.c[489,502] [2024-10-31 22:18:47,144 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-31 22:18:47,154 INFO L200 MainTranslator]: Completed pre-run [2024-10-31 22:18:47,167 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_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound2.c[489,502] [2024-10-31 22:18:47,182 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-31 22:18:47,197 INFO L204 MainTranslator]: Completed translation [2024-10-31 22:18:47,198 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47 WrapperNode [2024-10-31 22:18:47,198 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-31 22:18:47,199 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-31 22:18:47,199 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-31 22:18:47,199 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-31 22:18:47,210 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,218 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,235 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 57 [2024-10-31 22:18:47,235 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-31 22:18:47,236 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-31 22:18:47,236 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-31 22:18:47,236 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-31 22:18:47,248 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,248 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,250 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,259 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 22:18:47,260 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,260 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,263 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,266 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,267 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,268 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,270 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-31 22:18:47,270 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-31 22:18:47,271 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-31 22:18:47,271 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-31 22:18:47,272 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (1/1) ... [2024-10-31 22:18:47,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-31 22:18:47,289 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:47,300 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-31 22:18:47,302 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-31 22:18:47,326 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-31 22:18:47,326 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-31 22:18:47,326 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-31 22:18:47,327 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-31 22:18:47,327 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-31 22:18:47,327 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-31 22:18:47,327 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-31 22:18:47,327 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-31 22:18:47,386 INFO L238 CfgBuilder]: Building ICFG [2024-10-31 22:18:47,388 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-31 22:18:47,545 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-10-31 22:18:47,545 INFO L287 CfgBuilder]: Performing block encoding [2024-10-31 22:18:47,558 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-31 22:18:47,558 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-31 22:18:47,559 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 10:18:47 BoogieIcfgContainer [2024-10-31 22:18:47,559 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-31 22:18:47,562 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-31 22:18:47,562 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-31 22:18:47,565 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-31 22:18:47,566 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 31.10 10:18:46" (1/3) ... [2024-10-31 22:18:47,567 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1ff296af and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.10 10:18:47, skipping insertion in model container [2024-10-31 22:18:47,567 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:18:47" (2/3) ... [2024-10-31 22:18:47,567 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1ff296af and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 31.10 10:18:47, skipping insertion in model container [2024-10-31 22:18:47,567 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 10:18:47" (3/3) ... [2024-10-31 22:18:47,569 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound2.c [2024-10-31 22:18:47,589 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-31 22:18:47,589 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-31 22:18:47,649 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-31 22:18:47,655 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;@26e4e583, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-31 22:18:47,656 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-31 22:18:47,660 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-31 22:18:47,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-10-31 22:18:47,669 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:47,670 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:47,670 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:47,677 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:47,677 INFO L85 PathProgramCache]: Analyzing trace with hash 501437177, now seen corresponding path program 1 times [2024-10-31 22:18:47,689 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:47,689 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [799047476] [2024-10-31 22:18:47,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:47,691 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:47,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-31 22:18:47,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [973840644] [2024-10-31 22:18:47,890 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:47,890 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:47,891 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:47,893 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:47,899 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-31 22:18:47,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:47,976 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-31 22:18:47,983 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:48,157 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-31 22:18:48,157 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-31 22:18:48,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:48,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [799047476] [2024-10-31 22:18:48,161 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-31 22:18:48,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [973840644] [2024-10-31 22:18:48,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [973840644] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:18:48,162 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 22:18:48,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 22:18:48,166 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [964588126] [2024-10-31 22:18:48,166 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:18:48,171 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-31 22:18:48,172 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:48,203 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-31 22:18:48,204 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 22:18:48,206 INFO L87 Difference]: Start difference. First operand has 32 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-31 22:18:48,381 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:48,381 INFO L93 Difference]: Finished difference Result 77 states and 133 transitions. [2024-10-31 22:18:48,383 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-31 22:18:48,384 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2024-10-31 22:18:48,385 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:48,394 INFO L225 Difference]: With dead ends: 77 [2024-10-31 22:18:48,394 INFO L226 Difference]: Without dead ends: 42 [2024-10-31 22:18:48,398 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-31 22:18:48,405 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:48,406 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 136 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:48,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-10-31 22:18:48,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2024-10-31 22:18:48,467 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 20 states have (on average 1.25) internal successors, (25), 22 states have internal predecessors, (25), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-31 22:18:48,469 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 58 transitions. [2024-10-31 22:18:48,473 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 58 transitions. Word has length 29 [2024-10-31 22:18:48,474 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:48,475 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 58 transitions. [2024-10-31 22:18:48,475 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-31 22:18:48,476 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 58 transitions. [2024-10-31 22:18:48,477 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-10-31 22:18:48,479 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:48,480 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:48,501 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-31 22:18:48,680 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-10-31 22:18:48,681 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:48,684 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:48,684 INFO L85 PathProgramCache]: Analyzing trace with hash -1017640517, now seen corresponding path program 1 times [2024-10-31 22:18:48,684 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:48,688 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [182903392] [2024-10-31 22:18:48,688 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:48,689 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:48,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-31 22:18:48,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1346623634] [2024-10-31 22:18:48,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:48,799 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:48,799 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:48,804 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:48,813 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-31 22:18:48,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:48,901 INFO L255 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-31 22:18:48,904 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:49,023 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-31 22:18:49,023 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-31 22:18:49,024 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:49,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [182903392] [2024-10-31 22:18:49,024 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-31 22:18:49,024 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1346623634] [2024-10-31 22:18:49,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1346623634] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:18:49,026 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 22:18:49,026 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 22:18:49,027 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [553406356] [2024-10-31 22:18:49,027 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:18:49,030 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-31 22:18:49,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:49,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-31 22:18:49,032 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 22:18:49,032 INFO L87 Difference]: Start difference. First operand 41 states and 58 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-31 22:18:49,149 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:49,149 INFO L93 Difference]: Finished difference Result 66 states and 98 transitions. [2024-10-31 22:18:49,154 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-31 22:18:49,155 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2024-10-31 22:18:49,155 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:49,160 INFO L225 Difference]: With dead ends: 66 [2024-10-31 22:18:49,161 INFO L226 Difference]: Without dead ends: 64 [2024-10-31 22:18:49,161 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-31 22:18:49,163 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:49,163 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 123 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:49,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-10-31 22:18:49,186 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 57. [2024-10-31 22:18:49,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 29 states have (on average 1.3103448275862069) internal successors, (38), 31 states have internal predecessors, (38), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-31 22:18:49,191 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 83 transitions. [2024-10-31 22:18:49,194 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 83 transitions. Word has length 34 [2024-10-31 22:18:49,194 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:49,195 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 83 transitions. [2024-10-31 22:18:49,195 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-31 22:18:49,196 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 83 transitions. [2024-10-31 22:18:49,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-10-31 22:18:49,200 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:49,200 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:49,220 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-10-31 22:18:49,401 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:49,403 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:49,404 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:49,405 INFO L85 PathProgramCache]: Analyzing trace with hash 1133401081, now seen corresponding path program 1 times [2024-10-31 22:18:49,405 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:49,405 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1296386435] [2024-10-31 22:18:49,405 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:49,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:49,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-31 22:18:49,442 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [119758542] [2024-10-31 22:18:49,442 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:49,443 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:49,446 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:49,448 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:49,450 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-31 22:18:49,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:49,518 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-31 22:18:49,520 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:49,633 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-31 22:18:49,633 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-31 22:18:49,633 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:49,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1296386435] [2024-10-31 22:18:49,634 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-31 22:18:49,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [119758542] [2024-10-31 22:18:49,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [119758542] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:18:49,634 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 22:18:49,634 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 22:18:49,635 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1786072706] [2024-10-31 22:18:49,635 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:18:49,635 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-31 22:18:49,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:49,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-31 22:18:49,636 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 22:18:49,637 INFO L87 Difference]: Start difference. First operand 57 states and 83 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-31 22:18:49,727 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:49,727 INFO L93 Difference]: Finished difference Result 64 states and 89 transitions. [2024-10-31 22:18:49,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-31 22:18:49,728 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2024-10-31 22:18:49,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:49,729 INFO L225 Difference]: With dead ends: 64 [2024-10-31 22:18:49,729 INFO L226 Difference]: Without dead ends: 60 [2024-10-31 22:18:49,730 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-31 22:18:49,731 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:49,732 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 122 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:49,732 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-10-31 22:18:49,746 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2024-10-31 22:18:49,747 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 32 states have (on average 1.28125) internal successors, (41), 34 states have internal predecessors, (41), 22 states have call successors, (22), 5 states have call predecessors, (22), 5 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-10-31 22:18:49,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 83 transitions. [2024-10-31 22:18:49,748 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 83 transitions. Word has length 39 [2024-10-31 22:18:49,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:49,749 INFO L471 AbstractCegarLoop]: Abstraction has 60 states and 83 transitions. [2024-10-31 22:18:49,749 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-31 22:18:49,749 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 83 transitions. [2024-10-31 22:18:49,751 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-10-31 22:18:49,751 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:49,751 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:49,771 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-31 22:18:49,955 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:49,955 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:49,956 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:49,956 INFO L85 PathProgramCache]: Analyzing trace with hash -1954831506, now seen corresponding path program 1 times [2024-10-31 22:18:49,956 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:49,956 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1647993676] [2024-10-31 22:18:49,957 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:49,957 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:50,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,325 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 22:18:50,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,332 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-31 22:18:50,333 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,336 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-31 22:18:50,338 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,342 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-10-31 22:18:50,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,350 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-31 22:18:50,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,358 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-31 22:18:50,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-31 22:18:50,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,367 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-10-31 22:18:50,367 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:50,368 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1647993676] [2024-10-31 22:18:50,370 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1647993676] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:18:50,371 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 22:18:50,371 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 22:18:50,371 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1223022103] [2024-10-31 22:18:50,371 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:18:50,372 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-31 22:18:50,372 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:50,372 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-31 22:18:50,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 22:18:50,373 INFO L87 Difference]: Start difference. First operand 60 states and 83 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2024-10-31 22:18:50,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:50,450 INFO L93 Difference]: Finished difference Result 66 states and 88 transitions. [2024-10-31 22:18:50,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-31 22:18:50,451 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2024-10-31 22:18:50,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:50,455 INFO L225 Difference]: With dead ends: 66 [2024-10-31 22:18:50,455 INFO L226 Difference]: Without dead ends: 64 [2024-10-31 22:18:50,455 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-31 22:18:50,456 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 3 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:50,460 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 132 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:50,461 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-10-31 22:18:50,483 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 64. [2024-10-31 22:18:50,484 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 37 states have internal predecessors, (44), 22 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-10-31 22:18:50,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 86 transitions. [2024-10-31 22:18:50,488 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 86 transitions. Word has length 45 [2024-10-31 22:18:50,488 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:50,489 INFO L471 AbstractCegarLoop]: Abstraction has 64 states and 86 transitions. [2024-10-31 22:18:50,489 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2024-10-31 22:18:50,489 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 86 transitions. [2024-10-31 22:18:50,490 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-10-31 22:18:50,490 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:50,490 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:50,491 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-10-31 22:18:50,495 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:50,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:50,496 INFO L85 PathProgramCache]: Analyzing trace with hash -1265228631, now seen corresponding path program 1 times [2024-10-31 22:18:50,497 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:50,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [993356607] [2024-10-31 22:18:50,497 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:50,497 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:50,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-31 22:18:50,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [824528170] [2024-10-31 22:18:50,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:50,536 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:50,536 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:50,538 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:50,540 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-31 22:18:50,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:50,629 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-31 22:18:50,634 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:50,750 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2024-10-31 22:18:50,750 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-31 22:18:50,751 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:50,751 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [993356607] [2024-10-31 22:18:50,752 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-31 22:18:50,752 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [824528170] [2024-10-31 22:18:50,752 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [824528170] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:18:50,752 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 22:18:50,752 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 22:18:50,752 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [41903575] [2024-10-31 22:18:50,752 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:18:50,753 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-31 22:18:50,753 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:50,754 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-31 22:18:50,754 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-31 22:18:50,754 INFO L87 Difference]: Start difference. First operand 64 states and 86 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-31 22:18:50,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:50,843 INFO L93 Difference]: Finished difference Result 80 states and 104 transitions. [2024-10-31 22:18:50,843 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-31 22:18:50,844 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2024-10-31 22:18:50,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:50,846 INFO L225 Difference]: With dead ends: 80 [2024-10-31 22:18:50,846 INFO L226 Difference]: Without dead ends: 78 [2024-10-31 22:18:50,847 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-31 22:18:50,848 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 4 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:50,850 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 121 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:50,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2024-10-31 22:18:50,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 75. [2024-10-31 22:18:50,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 44 states have internal predecessors, (50), 25 states have call successors, (25), 8 states have call predecessors, (25), 8 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-10-31 22:18:50,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 98 transitions. [2024-10-31 22:18:50,867 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 98 transitions. Word has length 47 [2024-10-31 22:18:50,867 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:50,867 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 98 transitions. [2024-10-31 22:18:50,867 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-31 22:18:50,868 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 98 transitions. [2024-10-31 22:18:50,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-10-31 22:18:50,869 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:50,869 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:50,891 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-10-31 22:18:51,073 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:51,073 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:51,074 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:51,074 INFO L85 PathProgramCache]: Analyzing trace with hash 1617953190, now seen corresponding path program 1 times [2024-10-31 22:18:51,074 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:51,074 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [908084563] [2024-10-31 22:18:51,074 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:51,074 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:51,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,406 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 22:18:51,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,411 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-31 22:18:51,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,415 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-31 22:18:51,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,419 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-10-31 22:18:51,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,426 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-31 22:18:51,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,432 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-31 22:18:51,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,484 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-31 22:18:51,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,510 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-10-31 22:18:51,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,519 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-31 22:18:51,519 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:51,520 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [908084563] [2024-10-31 22:18:51,520 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [908084563] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:18:51,520 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1838994721] [2024-10-31 22:18:51,520 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:51,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:51,521 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:51,523 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:51,524 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-31 22:18:51,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:51,591 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-31 22:18:51,593 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:51,743 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-31 22:18:51,744 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-31 22:18:51,745 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1838994721] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:18:51,745 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-31 22:18:51,745 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2024-10-31 22:18:51,745 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [535553421] [2024-10-31 22:18:51,746 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:18:51,746 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-31 22:18:51,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:51,748 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-31 22:18:51,748 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-10-31 22:18:51,748 INFO L87 Difference]: Start difference. First operand 75 states and 98 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-31 22:18:51,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:51,887 INFO L93 Difference]: Finished difference Result 88 states and 110 transitions. [2024-10-31 22:18:51,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-31 22:18:51,887 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2024-10-31 22:18:51,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:51,889 INFO L225 Difference]: With dead ends: 88 [2024-10-31 22:18:51,892 INFO L226 Difference]: Without dead ends: 84 [2024-10-31 22:18:51,892 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2024-10-31 22:18:51,893 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:51,894 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 147 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:51,894 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2024-10-31 22:18:51,917 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 83. [2024-10-31 22:18:51,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 47 states have (on average 1.1702127659574468) internal successors, (55), 50 states have internal predecessors, (55), 25 states have call successors, (25), 10 states have call predecessors, (25), 10 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-10-31 22:18:51,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 103 transitions. [2024-10-31 22:18:51,922 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 103 transitions. Word has length 50 [2024-10-31 22:18:51,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:51,923 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 103 transitions. [2024-10-31 22:18:51,923 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-31 22:18:51,925 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 103 transitions. [2024-10-31 22:18:51,926 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2024-10-31 22:18:51,926 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:51,927 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:51,942 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-10-31 22:18:52,127 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:52,128 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:52,128 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:52,128 INFO L85 PathProgramCache]: Analyzing trace with hash 860577929, now seen corresponding path program 1 times [2024-10-31 22:18:52,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:52,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [870281869] [2024-10-31 22:18:52,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:52,128 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:52,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-31 22:18:52,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [432078474] [2024-10-31 22:18:52,149 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:52,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:52,153 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:52,154 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:52,157 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-31 22:18:52,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:52,249 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-10-31 22:18:52,275 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:52,566 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-31 22:18:52,566 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:18:52,891 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-31 22:18:52,891 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:52,891 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [870281869] [2024-10-31 22:18:52,891 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-31 22:18:52,891 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [432078474] [2024-10-31 22:18:52,891 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [432078474] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:18:52,891 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-31 22:18:52,891 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-10-31 22:18:52,892 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1786230138] [2024-10-31 22:18:52,892 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-31 22:18:52,894 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-10-31 22:18:52,894 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:52,895 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-10-31 22:18:52,895 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2024-10-31 22:18:52,898 INFO L87 Difference]: Start difference. First operand 83 states and 103 transitions. Second operand has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-10-31 22:18:53,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:53,905 INFO L93 Difference]: Finished difference Result 107 states and 140 transitions. [2024-10-31 22:18:53,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-31 22:18:53,906 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) Word has length 52 [2024-10-31 22:18:53,906 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:53,907 INFO L225 Difference]: With dead ends: 107 [2024-10-31 22:18:53,908 INFO L226 Difference]: Without dead ends: 92 [2024-10-31 22:18:53,909 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2024-10-31 22:18:53,910 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 16 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 162 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 211 SdHoareTripleChecker+Invalid, 206 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 162 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:53,912 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 211 Invalid, 206 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 162 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-10-31 22:18:53,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-10-31 22:18:53,972 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 75. [2024-10-31 22:18:53,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 44 states have (on average 1.1590909090909092) internal successors, (51), 46 states have internal predecessors, (51), 21 states have call successors, (21), 9 states have call predecessors, (21), 9 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2024-10-31 22:18:53,975 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 91 transitions. [2024-10-31 22:18:53,976 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 91 transitions. Word has length 52 [2024-10-31 22:18:53,976 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:53,976 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 91 transitions. [2024-10-31 22:18:53,976 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-10-31 22:18:53,976 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 91 transitions. [2024-10-31 22:18:53,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-10-31 22:18:53,984 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:53,984 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 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 22:18:54,032 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-10-31 22:18:54,187 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:54,187 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:54,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:54,188 INFO L85 PathProgramCache]: Analyzing trace with hash 1236716699, now seen corresponding path program 1 times [2024-10-31 22:18:54,188 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:54,188 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1205302867] [2024-10-31 22:18:54,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:54,188 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:54,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,527 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 22:18:54,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,562 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-31 22:18:54,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,568 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-31 22:18:54,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,575 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-10-31 22:18:54,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,582 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-31 22:18:54,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,588 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-31 22:18:54,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,595 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-31 22:18:54,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,602 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-31 22:18:54,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,610 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-10-31 22:18:54,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,617 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-31 22:18:54,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,622 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 16 proven. 15 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-31 22:18:54,623 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:54,623 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1205302867] [2024-10-31 22:18:54,623 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1205302867] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:18:54,623 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [971819071] [2024-10-31 22:18:54,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:54,623 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:54,624 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:54,626 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:54,627 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-31 22:18:54,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:54,692 INFO L255 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-31 22:18:54,694 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:54,859 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 16 proven. 15 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-31 22:18:54,859 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:18:55,029 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 16 proven. 15 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-31 22:18:55,030 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [971819071] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:18:55,030 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 22:18:55,030 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 14 [2024-10-31 22:18:55,030 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1375335316] [2024-10-31 22:18:55,030 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 22:18:55,031 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-10-31 22:18:55,031 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:55,032 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-10-31 22:18:55,033 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-10-31 22:18:55,034 INFO L87 Difference]: Start difference. First operand 75 states and 91 transitions. Second operand has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (23), 7 states have call predecessors, (23), 8 states have call successors, (23) [2024-10-31 22:18:55,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:55,260 INFO L93 Difference]: Finished difference Result 98 states and 118 transitions. [2024-10-31 22:18:55,261 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-31 22:18:55,261 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (23), 7 states have call predecessors, (23), 8 states have call successors, (23) Word has length 65 [2024-10-31 22:18:55,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:55,262 INFO L225 Difference]: With dead ends: 98 [2024-10-31 22:18:55,262 INFO L226 Difference]: Without dead ends: 75 [2024-10-31 22:18:55,263 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 141 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=66, Invalid=206, Unknown=0, NotChecked=0, Total=272 [2024-10-31 22:18:55,263 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 9 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 123 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:55,264 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 199 Invalid, 123 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:55,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2024-10-31 22:18:55,288 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 75. [2024-10-31 22:18:55,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 44 states have (on average 1.1136363636363635) internal successors, (49), 46 states have internal predecessors, (49), 21 states have call successors, (21), 9 states have call predecessors, (21), 9 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2024-10-31 22:18:55,290 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 89 transitions. [2024-10-31 22:18:55,290 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 89 transitions. Word has length 65 [2024-10-31 22:18:55,291 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:55,291 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 89 transitions. [2024-10-31 22:18:55,291 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.5714285714285716) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (23), 7 states have call predecessors, (23), 8 states have call successors, (23) [2024-10-31 22:18:55,291 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 89 transitions. [2024-10-31 22:18:55,292 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-10-31 22:18:55,293 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:55,293 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 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 22:18:55,315 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-10-31 22:18:55,497 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:55,498 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:55,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:55,499 INFO L85 PathProgramCache]: Analyzing trace with hash 1045444891, now seen corresponding path program 2 times [2024-10-31 22:18:55,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:55,499 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [588938635] [2024-10-31 22:18:55,499 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:55,499 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:55,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,705 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 22:18:55,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,708 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-31 22:18:55,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,766 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-31 22:18:55,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,771 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-10-31 22:18:55,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,780 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-31 22:18:55,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,792 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-31 22:18:55,794 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,803 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-31 22:18:55,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,816 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-31 22:18:55,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,824 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-10-31 22:18:55,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,834 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-31 22:18:55,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:55,842 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 19 proven. 12 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-31 22:18:55,846 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:55,846 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [588938635] [2024-10-31 22:18:55,846 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [588938635] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:18:55,846 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2016613532] [2024-10-31 22:18:55,847 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-31 22:18:55,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:55,847 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:55,854 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:55,855 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-31 22:18:55,923 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-31 22:18:55,923 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-31 22:18:55,925 INFO L255 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-31 22:18:55,931 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:56,073 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 19 proven. 12 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-31 22:18:56,073 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:18:56,258 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 19 proven. 12 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-10-31 22:18:56,258 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2016613532] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:18:56,258 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 22:18:56,259 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 15 [2024-10-31 22:18:56,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [304298901] [2024-10-31 22:18:56,259 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 22:18:56,260 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-10-31 22:18:56,260 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:56,261 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-10-31 22:18:56,261 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2024-10-31 22:18:56,261 INFO L87 Difference]: Start difference. First operand 75 states and 89 transitions. Second operand has 15 states, 15 states have (on average 2.4) internal successors, (36), 13 states have internal predecessors, (36), 9 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-10-31 22:18:56,524 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:56,525 INFO L93 Difference]: Finished difference Result 89 states and 100 transitions. [2024-10-31 22:18:56,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-10-31 22:18:56,526 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 13 states have internal predecessors, (36), 9 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 65 [2024-10-31 22:18:56,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:56,527 INFO L225 Difference]: With dead ends: 89 [2024-10-31 22:18:56,527 INFO L226 Difference]: Without dead ends: 54 [2024-10-31 22:18:56,528 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 142 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2024-10-31 22:18:56,529 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 8 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 130 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 130 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:56,529 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 216 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 130 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-10-31 22:18:56,530 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-10-31 22:18:56,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2024-10-31 22:18:56,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 33 states have (on average 1.0303030303030303) internal successors, (34), 33 states have internal predecessors, (34), 12 states have call successors, (12), 8 states have call predecessors, (12), 7 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-31 22:18:56,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 57 transitions. [2024-10-31 22:18:56,543 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 57 transitions. Word has length 65 [2024-10-31 22:18:56,543 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:56,544 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 57 transitions. [2024-10-31 22:18:56,544 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.4) internal successors, (36), 13 states have internal predecessors, (36), 9 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-10-31 22:18:56,544 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 57 transitions. [2024-10-31 22:18:56,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-10-31 22:18:56,545 INFO L207 NwaCegarLoop]: Found error trace [2024-10-31 22:18:56,545 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:56,568 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-10-31 22:18:56,750 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:56,750 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-31 22:18:56,751 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:18:56,751 INFO L85 PathProgramCache]: Analyzing trace with hash -2086142860, now seen corresponding path program 1 times [2024-10-31 22:18:56,751 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:18:56,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1008486560] [2024-10-31 22:18:56,752 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:56,752 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:18:56,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,953 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-10-31 22:18:56,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,957 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-10-31 22:18:56,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,960 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-10-31 22:18:56,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,962 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-10-31 22:18:56,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,965 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 25 [2024-10-31 22:18:56,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,968 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-31 22:18:56,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,971 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-10-31 22:18:56,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,974 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-10-31 22:18:56,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:56,977 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 48 [2024-10-31 22:18:56,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:57,005 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 53 [2024-10-31 22:18:57,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:57,017 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-10-31 22:18:57,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:57,021 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-10-31 22:18:57,022 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:18:57,022 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1008486560] [2024-10-31 22:18:57,022 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1008486560] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:18:57,022 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1090933348] [2024-10-31 22:18:57,022 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:18:57,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:57,023 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:18:57,025 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:18:57,026 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-10-31 22:18:57,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:18:57,090 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-31 22:18:57,095 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:18:57,194 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-10-31 22:18:57,195 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:18:57,310 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-10-31 22:18:57,310 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1090933348] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:18:57,311 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 22:18:57,311 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 11 [2024-10-31 22:18:57,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1471554063] [2024-10-31 22:18:57,311 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 22:18:57,312 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-31 22:18:57,312 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:18:57,313 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-31 22:18:57,313 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-10-31 22:18:57,313 INFO L87 Difference]: Start difference. First operand 53 states and 57 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-31 22:18:57,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:18:57,452 INFO L93 Difference]: Finished difference Result 53 states and 57 transitions. [2024-10-31 22:18:57,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-31 22:18:57,453 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 68 [2024-10-31 22:18:57,453 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-31 22:18:57,453 INFO L225 Difference]: With dead ends: 53 [2024-10-31 22:18:57,453 INFO L226 Difference]: Without dead ends: 0 [2024-10-31 22:18:57,454 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 153 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-10-31 22:18:57,454 INFO L432 NwaCegarLoop]: 24 mSDtfsCounter, 8 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 143 SdHoareTripleChecker+Invalid, 85 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-31 22:18:57,455 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 143 Invalid, 85 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-31 22:18:57,455 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-10-31 22:18:57,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-10-31 22:18:57,456 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-31 22:18:57,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-10-31 22:18:57,456 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 68 [2024-10-31 22:18:57,457 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-31 22:18:57,457 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-31 22:18:57,457 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-31 22:18:57,457 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-10-31 22:18:57,457 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-10-31 22:18:57,460 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-10-31 22:18:57,482 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-10-31 22:18:57,665 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:18:57,668 INFO L407 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:18:57,670 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-10-31 22:18:59,905 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-10-31 22:18:59,938 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 31.10 10:18:59 BoogieIcfgContainer [2024-10-31 22:18:59,939 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-10-31 22:18:59,939 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-31 22:18:59,939 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-31 22:18:59,940 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-31 22:18:59,940 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 10:18:47" (3/4) ... [2024-10-31 22:18:59,943 INFO L142 WitnessPrinter]: Generating witness for correct program [2024-10-31 22:18:59,947 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-10-31 22:18:59,947 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-10-31 22:18:59,953 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2024-10-31 22:18:59,954 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-10-31 22:18:59,954 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-10-31 22:18:59,954 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-10-31 22:19:00,057 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/witness.graphml [2024-10-31 22:19:00,057 INFO L149 WitnessManager]: Wrote witness to /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/bin/uautomizer-verify-4GaUIPS5ZU/witness.yml [2024-10-31 22:19:00,057 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-31 22:19:00,058 INFO L158 Benchmark]: Toolchain (without parser) took 13169.31ms. Allocated memory was 144.7MB in the beginning and 239.1MB in the end (delta: 94.4MB). Free memory was 108.7MB in the beginning and 77.4MB in the end (delta: 31.3MB). Peak memory consumption was 126.2MB. Max. memory is 16.1GB. [2024-10-31 22:19:00,058 INFO L158 Benchmark]: CDTParser took 0.33ms. Allocated memory is still 144.7MB. Free memory is still 87.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-31 22:19:00,059 INFO L158 Benchmark]: CACSL2BoogieTranslator took 308.15ms. Allocated memory is still 144.7MB. Free memory was 108.2MB in the beginning and 95.6MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-10-31 22:19:00,059 INFO L158 Benchmark]: Boogie Procedure Inliner took 36.64ms. Allocated memory is still 144.7MB. Free memory was 95.6MB in the beginning and 94.0MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-31 22:19:00,059 INFO L158 Benchmark]: Boogie Preprocessor took 33.56ms. Allocated memory is still 144.7MB. Free memory was 94.0MB in the beginning and 92.4MB in the end (delta: 1.6MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-31 22:19:00,060 INFO L158 Benchmark]: RCFGBuilder took 288.46ms. Allocated memory is still 144.7MB. Free memory was 92.4MB in the beginning and 80.9MB in the end (delta: 11.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-10-31 22:19:00,060 INFO L158 Benchmark]: TraceAbstraction took 12377.40ms. Allocated memory was 144.7MB in the beginning and 239.1MB in the end (delta: 94.4MB). Free memory was 79.9MB in the beginning and 82.6MB in the end (delta: -2.7MB). Peak memory consumption was 94.7MB. Max. memory is 16.1GB. [2024-10-31 22:19:00,061 INFO L158 Benchmark]: Witness Printer took 118.14ms. Allocated memory is still 239.1MB. Free memory was 81.6MB in the beginning and 77.4MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-10-31 22:19:00,062 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.33ms. Allocated memory is still 144.7MB. Free memory is still 87.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 308.15ms. Allocated memory is still 144.7MB. Free memory was 108.2MB in the beginning and 95.6MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 36.64ms. Allocated memory is still 144.7MB. Free memory was 95.6MB in the beginning and 94.0MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 33.56ms. Allocated memory is still 144.7MB. Free memory was 94.0MB in the beginning and 92.4MB in the end (delta: 1.6MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 288.46ms. Allocated memory is still 144.7MB. Free memory was 92.4MB in the beginning and 80.9MB in the end (delta: 11.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 12377.40ms. Allocated memory was 144.7MB in the beginning and 239.1MB in the end (delta: 94.4MB). Free memory was 79.9MB in the beginning and 82.6MB in the end (delta: -2.7MB). Peak memory consumption was 94.7MB. Max. memory is 16.1GB. * Witness Printer took 118.14ms. Allocated memory is still 239.1MB. Free memory was 81.6MB in the beginning and 77.4MB in the end (delta: 4.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 - PositiveResult [Line: 13]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 32 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 10.0s, OverallIterations: 10, TraceHistogramMax: 8, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 2.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 95 SdHoareTripleChecker+Valid, 1.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 72 mSDsluCounter, 1550 SdHoareTripleChecker+Invalid, 1.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1225 mSDsCounter, 88 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 688 IncrementalHoareTripleChecker+Invalid, 776 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 88 mSolverCounterUnsat, 325 mSDtfsCounter, 688 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 836 GetRequests, 741 SyntacticMatches, 6 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 189 ImplicationChecksByTransitivity, 1.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=83occurred in iteration=6, InterpolantAutomatonStates: 67, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 10 MinimizatonAttempts, 30 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 4.0s InterpolantComputationTime, 943 NumberOfCodeBlocks, 943 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 974 ConstructedInterpolants, 0 QuantifiedInterpolants, 2447 SizeOfPredicates, 18 NumberOfNonLiveVariables, 1111 ConjunctsInSsa, 111 ConjunctsInUnsatCore, 18 InterpolantComputations, 6 PerfectInterpolantSequences, 1286/1415 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 - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 35]: Loop Invariant Derived loop invariant: ((((((((((((0 <= x) && (p == 1)) && (b <= 1)) && (0 <= y)) && (((__int128) a + y) == ((((__int128) r * y) + b) + x))) && ((((__int128) r * y) + x) == a)) && (q == 0)) && (1 <= a)) && (x <= 2)) && (s == 1)) || ((((((((((0 <= x) && (p == 1)) && (b == y)) && (0 <= y)) && (b <= 2)) && (r == 0)) && (q == 0)) && (a == x)) && (x <= 2)) && (s == 1))) || ((((((((((0 <= x) && (p == 1)) && (y <= 2)) && (a <= 1)) && (0 <= y)) && ((((__int128) a + y) + ((__int128) q * x)) == ((__int128) b + x))) && (1 <= b)) && (r == 0)) && (a == x)) && (s == 1))) - ProcedureContractResult [Line: 7]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not. Ensures: (cond != 0) - ProcedureContractResult [Line: 10]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= cond) Ensures: (1 <= cond) RESULT: Ultimate proved your program to be correct! [2024-10-31 22:19:00,083 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_cd52c9b4-2ad2-4fa9-83b7-e08688de7c96/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 Result: TRUE