./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/combinations/gcd_4+newton_3_1.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version d790fecc Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/config/AutomizerReach.xml -i ../../sv-benchmarks/c/combinations/gcd_4+newton_3_1.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ad6236f3b1535aee53ef497474ba76faac9143455d497d8d917066c0b5859668 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-d790fec [2024-11-28 03:24:32,423 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-28 03:24:32,520 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-28 03:24:32,529 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-28 03:24:32,529 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-28 03:24:32,570 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-28 03:24:32,571 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-28 03:24:32,571 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-28 03:24:32,571 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-28 03:24:32,571 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-28 03:24:32,571 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-28 03:24:32,572 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-28 03:24:32,572 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-28 03:24:32,572 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-28 03:24:32,572 INFO L153 SettingsManager]: * Use SBE=true [2024-11-28 03:24:32,572 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-28 03:24:32,572 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-28 03:24:32,572 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-28 03:24:32,572 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-28 03:24:32,573 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2024-11-28 03:24:32,574 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-28 03:24:32,575 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-28 03:24:32,576 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-28 03:24:32,576 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-28 03:24:32,576 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-28 03:24:32,576 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-28 03:24:32,576 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-28 03:24:32,576 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-28 03:24:32,576 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-28 03:24:32,576 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-28 03:24:32,577 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-28 03:24:32,577 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-28 03:24:32,577 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-28 03:24:32,577 INFO L153 SettingsManager]: * Compute procedure contracts=false [2024-11-28 03:24:32,577 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-28 03:24:32,577 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-28 03:24:32,577 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-28 03:24:32,578 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-28 03:24:32,578 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-28 03:24:32,578 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-28 03:24:32,578 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-28 03:24:32,579 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ad6236f3b1535aee53ef497474ba76faac9143455d497d8d917066c0b5859668 [2024-11-28 03:24:32,873 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-28 03:24:32,881 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-28 03:24:32,884 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-28 03:24:32,885 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-28 03:24:32,885 INFO L274 PluginConnector]: CDTParser initialized [2024-11-28 03:24:32,886 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/../../sv-benchmarks/c/combinations/gcd_4+newton_3_1.i [2024-11-28 03:24:35,801 INFO L533 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/dcf26f361/8aaed3f8bb624e1f805852fad764f22e/FLAG71d1a60ae [2024-11-28 03:24:36,047 INFO L384 CDTParser]: Found 1 translation units. [2024-11-28 03:24:36,051 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i [2024-11-28 03:24:36,060 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/dcf26f361/8aaed3f8bb624e1f805852fad764f22e/FLAG71d1a60ae [2024-11-28 03:24:36,075 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/dcf26f361/8aaed3f8bb624e1f805852fad764f22e [2024-11-28 03:24:36,078 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-28 03:24:36,079 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-28 03:24:36,081 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-28 03:24:36,081 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-28 03:24:36,085 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-28 03:24:36,086 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,087 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@ea8cf0f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36, skipping insertion in model container [2024-11-28 03:24:36,087 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,109 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-28 03:24:36,293 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[1224,1237] [2024-11-28 03:24:36,340 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[2848,2861] [2024-11-28 03:24:36,341 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-28 03:24:36,358 INFO L200 MainTranslator]: Completed pre-run [2024-11-28 03:24:36,372 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[1224,1237] [2024-11-28 03:24:36,391 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[2848,2861] [2024-11-28 03:24:36,392 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-28 03:24:36,412 INFO L204 MainTranslator]: Completed translation [2024-11-28 03:24:36,412 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36 WrapperNode [2024-11-28 03:24:36,414 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-28 03:24:36,415 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-28 03:24:36,416 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-28 03:24:36,416 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-28 03:24:36,424 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,432 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,455 INFO L138 Inliner]: procedures = 27, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 83 [2024-11-28 03:24:36,459 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-28 03:24:36,459 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-28 03:24:36,460 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-28 03:24:36,460 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-28 03:24:36,470 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,470 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,476 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,498 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-28 03:24:36,501 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,502 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,511 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,512 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,519 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,520 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,524 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,526 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-28 03:24:36,527 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-28 03:24:36,530 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-28 03:24:36,530 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-28 03:24:36,531 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (1/1) ... [2024-11-28 03:24:36,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-28 03:24:36,553 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:36,566 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-28 03:24:36,574 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-28 03:24:36,604 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-28 03:24:36,605 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2024-11-28 03:24:36,605 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2024-11-28 03:24:36,605 INFO L130 BoogieDeclarations]: Found specification of procedure f [2024-11-28 03:24:36,605 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2024-11-28 03:24:36,606 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-28 03:24:36,606 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-28 03:24:36,606 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-28 03:24:36,606 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-28 03:24:36,606 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-28 03:24:36,607 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-28 03:24:36,689 INFO L234 CfgBuilder]: Building ICFG [2024-11-28 03:24:36,690 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-28 03:24:36,943 INFO L? ?]: Removed 25 outVars from TransFormulas that were not future-live. [2024-11-28 03:24:36,943 INFO L283 CfgBuilder]: Performing block encoding [2024-11-28 03:24:36,954 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-28 03:24:36,954 INFO L312 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-28 03:24:36,955 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 03:24:36 BoogieIcfgContainer [2024-11-28 03:24:36,955 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-28 03:24:36,958 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-28 03:24:36,959 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-28 03:24:36,964 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-28 03:24:36,965 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.11 03:24:36" (1/3) ... [2024-11-28 03:24:36,966 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4090afc8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 03:24:36, skipping insertion in model container [2024-11-28 03:24:36,966 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:36" (2/3) ... [2024-11-28 03:24:36,966 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4090afc8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 03:24:36, skipping insertion in model container [2024-11-28 03:24:36,966 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 03:24:36" (3/3) ... [2024-11-28 03:24:36,967 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_1.i [2024-11-28 03:24:36,984 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-28 03:24:36,986 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_1.i that has 4 procedures, 46 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2024-11-28 03:24:37,039 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-28 03:24:37,053 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;@45c3bd8a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-28 03:24:37,053 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2024-11-28 03:24:37,057 INFO L276 IsEmpty]: Start isEmpty. Operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-28 03:24:37,064 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-28 03:24:37,064 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:37,065 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:37,066 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:37,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:37,071 INFO L85 PathProgramCache]: Analyzing trace with hash -1780387208, now seen corresponding path program 1 times [2024-11-28 03:24:37,079 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:37,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754787951] [2024-11-28 03:24:37,080 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:37,080 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:37,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:24:37,368 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:37,368 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:37,369 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [754787951] [2024-11-28 03:24:37,369 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [754787951] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-28 03:24:37,370 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-28 03:24:37,370 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-28 03:24:37,371 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1724585168] [2024-11-28 03:24:37,372 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-28 03:24:37,375 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-28 03:24:37,376 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:37,398 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-28 03:24:37,398 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:24:37,401 INFO L87 Difference]: Start difference. First operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:37,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:37,472 INFO L93 Difference]: Finished difference Result 90 states and 123 transitions. [2024-11-28 03:24:37,473 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-28 03:24:37,475 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-28 03:24:37,475 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:37,480 INFO L225 Difference]: With dead ends: 90 [2024-11-28 03:24:37,481 INFO L226 Difference]: Without dead ends: 42 [2024-11-28 03:24:37,484 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:24:37,487 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 7 mSDsluCounter, 45 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 95 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:37,488 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 95 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-28 03:24:37,502 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-28 03:24:37,517 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2024-11-28 03:24:37,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:24:37,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 47 transitions. [2024-11-28 03:24:37,524 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 47 transitions. Word has length 11 [2024-11-28 03:24:37,524 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:37,524 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 47 transitions. [2024-11-28 03:24:37,524 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:37,525 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 47 transitions. [2024-11-28 03:24:37,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-28 03:24:37,526 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:37,526 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:37,526 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-28 03:24:37,526 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:37,527 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:37,527 INFO L85 PathProgramCache]: Analyzing trace with hash 1301222473, now seen corresponding path program 1 times [2024-11-28 03:24:37,527 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:37,527 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [21984850] [2024-11-28 03:24:37,527 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:37,527 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:37,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:24:37,646 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:37,646 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:37,646 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [21984850] [2024-11-28 03:24:37,646 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [21984850] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-28 03:24:37,646 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-28 03:24:37,646 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-28 03:24:37,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [993773701] [2024-11-28 03:24:37,646 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-28 03:24:37,648 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-28 03:24:37,648 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:37,648 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-28 03:24:37,652 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:24:37,653 INFO L87 Difference]: Start difference. First operand 39 states and 47 transitions. Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:37,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:37,693 INFO L93 Difference]: Finished difference Result 55 states and 68 transitions. [2024-11-28 03:24:37,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-28 03:24:37,694 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2024-11-28 03:24:37,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:37,695 INFO L225 Difference]: With dead ends: 55 [2024-11-28 03:24:37,695 INFO L226 Difference]: Without dead ends: 41 [2024-11-28 03:24:37,695 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:24:37,696 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 4 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:37,696 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 79 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-28 03:24:37,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-28 03:24:37,701 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2024-11-28 03:24:37,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:24:37,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2024-11-28 03:24:37,703 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 13 [2024-11-28 03:24:37,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:37,703 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2024-11-28 03:24:37,704 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:37,704 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2024-11-28 03:24:37,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-28 03:24:37,705 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:37,705 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:37,705 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-28 03:24:37,706 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:37,706 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:37,706 INFO L85 PathProgramCache]: Analyzing trace with hash 299954435, now seen corresponding path program 1 times [2024-11-28 03:24:37,706 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:37,706 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1325699876] [2024-11-28 03:24:37,706 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:37,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:37,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:24:37,890 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:37,890 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:37,890 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1325699876] [2024-11-28 03:24:37,891 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1325699876] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-28 03:24:37,891 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-28 03:24:37,891 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-28 03:24:37,891 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1012828831] [2024-11-28 03:24:37,891 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-28 03:24:37,893 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-28 03:24:37,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:37,894 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-28 03:24:37,896 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:24:37,896 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:37,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:37,933 INFO L93 Difference]: Finished difference Result 56 states and 68 transitions. [2024-11-28 03:24:37,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-28 03:24:37,934 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2024-11-28 03:24:37,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:37,935 INFO L225 Difference]: With dead ends: 56 [2024-11-28 03:24:37,935 INFO L226 Difference]: Without dead ends: 43 [2024-11-28 03:24:37,935 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:24:37,936 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:37,937 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 77 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-28 03:24:37,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-28 03:24:37,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-28 03:24:37,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 31 states have internal predecessors, (34), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:24:37,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 51 transitions. [2024-11-28 03:24:37,944 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 51 transitions. Word has length 15 [2024-11-28 03:24:37,944 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:37,944 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 51 transitions. [2024-11-28 03:24:37,945 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:37,945 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 51 transitions. [2024-11-28 03:24:37,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-28 03:24:37,945 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:37,945 INFO L218 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:37,946 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-28 03:24:37,946 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:37,946 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:37,946 INFO L85 PathProgramCache]: Analyzing trace with hash -153993347, now seen corresponding path program 1 times [2024-11-28 03:24:37,946 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:37,947 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [658932859] [2024-11-28 03:24:37,947 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:37,947 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:37,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:24:38,170 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:38,170 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:38,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [658932859] [2024-11-28 03:24:38,170 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [658932859] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-28 03:24:38,170 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1144816428] [2024-11-28 03:24:38,170 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:38,170 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:38,170 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:38,173 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:24:38,178 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-28 03:24:38,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:24:38,245 INFO L256 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-28 03:24:38,250 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:24:38,378 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:38,379 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:24:38,463 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:38,464 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1144816428] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:24:38,464 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-28 03:24:38,464 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 4] total 9 [2024-11-28 03:24:38,464 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [637840743] [2024-11-28 03:24:38,464 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-28 03:24:38,464 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-28 03:24:38,465 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:38,465 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-28 03:24:38,465 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2024-11-28 03:24:38,466 INFO L87 Difference]: Start difference. First operand 43 states and 51 transitions. Second operand has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:38,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:38,550 INFO L93 Difference]: Finished difference Result 60 states and 73 transitions. [2024-11-28 03:24:38,550 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-28 03:24:38,551 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 17 [2024-11-28 03:24:38,551 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:38,552 INFO L225 Difference]: With dead ends: 60 [2024-11-28 03:24:38,552 INFO L226 Difference]: Without dead ends: 47 [2024-11-28 03:24:38,552 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2024-11-28 03:24:38,553 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 0 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:38,553 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 222 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-28 03:24:38,554 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-28 03:24:38,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2024-11-28 03:24:38,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 35 states have internal predecessors, (38), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:24:38,560 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 55 transitions. [2024-11-28 03:24:38,560 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 55 transitions. Word has length 17 [2024-11-28 03:24:38,560 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:38,560 INFO L471 AbstractCegarLoop]: Abstraction has 47 states and 55 transitions. [2024-11-28 03:24:38,561 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.6666666666666665) internal successors, (33), 9 states have internal predecessors, (33), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:38,561 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 55 transitions. [2024-11-28 03:24:38,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-28 03:24:38,561 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:38,562 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:38,571 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-28 03:24:38,762 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:38,762 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:38,763 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:38,763 INFO L85 PathProgramCache]: Analyzing trace with hash -1157932815, now seen corresponding path program 2 times [2024-11-28 03:24:38,763 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:38,763 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1795440304] [2024-11-28 03:24:38,763 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-28 03:24:38,763 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:38,796 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-28 03:24:38,796 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:24:39,022 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:39,022 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:39,022 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1795440304] [2024-11-28 03:24:39,023 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1795440304] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-28 03:24:39,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1769287211] [2024-11-28 03:24:39,023 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-28 03:24:39,023 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:39,024 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:39,026 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:24:39,029 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-28 03:24:39,099 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-28 03:24:39,099 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:24:39,101 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-28 03:24:39,103 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:24:39,278 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:39,278 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:24:39,414 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:39,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1769287211] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:24:39,414 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-28 03:24:39,414 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 17 [2024-11-28 03:24:39,414 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1557408694] [2024-11-28 03:24:39,416 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-28 03:24:39,417 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-28 03:24:39,417 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:39,417 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-28 03:24:39,418 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=172, Unknown=0, NotChecked=0, Total=272 [2024-11-28 03:24:39,418 INFO L87 Difference]: Start difference. First operand 47 states and 55 transitions. Second operand has 17 states, 17 states have (on average 2.7058823529411766) internal successors, (46), 17 states have internal predecessors, (46), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:39,587 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:39,591 INFO L93 Difference]: Finished difference Result 69 states and 88 transitions. [2024-11-28 03:24:39,592 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-28 03:24:39,592 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.7058823529411766) internal successors, (46), 17 states have internal predecessors, (46), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 21 [2024-11-28 03:24:39,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:39,593 INFO L225 Difference]: With dead ends: 69 [2024-11-28 03:24:39,593 INFO L226 Difference]: Without dead ends: 54 [2024-11-28 03:24:39,594 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=124, Invalid=218, Unknown=0, NotChecked=0, Total=342 [2024-11-28 03:24:39,594 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 7 mSDsluCounter, 217 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 257 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:39,595 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 257 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-28 03:24:39,599 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-11-28 03:24:39,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 52. [2024-11-28 03:24:39,609 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 38 states have (on average 1.131578947368421) internal successors, (43), 40 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:24:39,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 60 transitions. [2024-11-28 03:24:39,613 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 60 transitions. Word has length 21 [2024-11-28 03:24:39,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:39,614 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 60 transitions. [2024-11-28 03:24:39,614 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.7058823529411766) internal successors, (46), 17 states have internal predecessors, (46), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:39,614 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 60 transitions. [2024-11-28 03:24:39,615 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-28 03:24:39,615 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:39,615 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:39,629 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-28 03:24:39,815 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:39,816 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:39,816 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:39,816 INFO L85 PathProgramCache]: Analyzing trace with hash -1417329111, now seen corresponding path program 3 times [2024-11-28 03:24:39,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:39,816 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [972375302] [2024-11-28 03:24:39,816 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-28 03:24:39,816 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:39,844 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-28 03:24:39,844 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-28 03:24:39,846 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [324719646] [2024-11-28 03:24:39,846 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-28 03:24:39,846 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:39,846 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:39,848 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:24:39,852 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-28 03:24:39,910 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-28 03:24:39,910 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:24:39,911 INFO L256 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-28 03:24:39,914 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:24:40,160 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-28 03:24:40,161 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:24:40,654 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-28 03:24:40,655 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:40,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [972375302] [2024-11-28 03:24:40,655 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-28 03:24:40,655 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [324719646] [2024-11-28 03:24:40,655 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [324719646] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:24:40,655 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:24:40,656 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2024-11-28 03:24:40,656 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1871369563] [2024-11-28 03:24:40,656 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:24:40,656 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-28 03:24:40,656 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:40,657 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-28 03:24:40,657 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2024-11-28 03:24:40,657 INFO L87 Difference]: Start difference. First operand 52 states and 60 transitions. Second operand has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:41,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:41,103 INFO L93 Difference]: Finished difference Result 75 states and 91 transitions. [2024-11-28 03:24:41,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-28 03:24:41,104 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2024-11-28 03:24:41,104 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:41,106 INFO L225 Difference]: With dead ends: 75 [2024-11-28 03:24:41,106 INFO L226 Difference]: Without dead ends: 72 [2024-11-28 03:24:41,106 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=80, Invalid=426, Unknown=0, NotChecked=0, Total=506 [2024-11-28 03:24:41,107 INFO L435 NwaCegarLoop]: 36 mSDtfsCounter, 12 mSDsluCounter, 409 mSDsCounter, 0 mSdLazyCounter, 260 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 445 SdHoareTripleChecker+Invalid, 272 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 260 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:41,110 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 445 Invalid, 272 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 260 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-28 03:24:41,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-11-28 03:24:41,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2024-11-28 03:24:41,125 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 51 states have (on average 1.196078431372549) internal successors, (61), 55 states have internal predecessors, (61), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-28 03:24:41,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 83 transitions. [2024-11-28 03:24:41,126 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 83 transitions. Word has length 23 [2024-11-28 03:24:41,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:41,127 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 83 transitions. [2024-11-28 03:24:41,127 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 1.9375) internal successors, (31), 16 states have internal predecessors, (31), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:41,127 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 83 transitions. [2024-11-28 03:24:41,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-28 03:24:41,128 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:41,128 INFO L218 NwaCegarLoop]: trace histogram [6, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:41,138 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-28 03:24:41,329 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2024-11-28 03:24:41,329 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:41,329 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:41,330 INFO L85 PathProgramCache]: Analyzing trace with hash -1589066399, now seen corresponding path program 4 times [2024-11-28 03:24:41,330 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:41,330 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2027971992] [2024-11-28 03:24:41,330 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-28 03:24:41,330 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:41,346 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-28 03:24:41,346 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:24:41,527 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:41,527 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:41,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2027971992] [2024-11-28 03:24:41,527 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2027971992] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-28 03:24:41,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [481150651] [2024-11-28 03:24:41,528 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-28 03:24:41,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:41,528 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:41,530 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:24:41,534 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-28 03:24:41,593 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-28 03:24:41,593 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:24:41,595 INFO L256 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-28 03:24:41,597 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:24:41,810 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 2 proven. 34 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:41,810 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:24:42,002 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:42,003 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [481150651] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:24:42,003 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-28 03:24:42,003 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 22 [2024-11-28 03:24:42,003 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032866722] [2024-11-28 03:24:42,003 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-28 03:24:42,003 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-28 03:24:42,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:42,007 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-28 03:24:42,007 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=367, Unknown=0, NotChecked=0, Total=462 [2024-11-28 03:24:42,007 INFO L87 Difference]: Start difference. First operand 69 states and 83 transitions. Second operand has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:42,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:42,256 INFO L93 Difference]: Finished difference Result 90 states and 108 transitions. [2024-11-28 03:24:42,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-28 03:24:42,257 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 25 [2024-11-28 03:24:42,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:42,257 INFO L225 Difference]: With dead ends: 90 [2024-11-28 03:24:42,257 INFO L226 Difference]: Without dead ends: 61 [2024-11-28 03:24:42,258 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=174, Invalid=528, Unknown=0, NotChecked=0, Total=702 [2024-11-28 03:24:42,259 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 12 mSDsluCounter, 470 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 509 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:42,259 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 509 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-28 03:24:42,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-11-28 03:24:42,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2024-11-28 03:24:42,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 44 states have (on average 1.1136363636363635) internal successors, (49), 47 states have internal predecessors, (49), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-28 03:24:42,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 69 transitions. [2024-11-28 03:24:42,268 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 69 transitions. Word has length 25 [2024-11-28 03:24:42,268 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:42,268 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 69 transitions. [2024-11-28 03:24:42,268 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 2.590909090909091) internal successors, (57), 22 states have internal predecessors, (57), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:42,268 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 69 transitions. [2024-11-28 03:24:42,269 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-28 03:24:42,269 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:42,269 INFO L218 NwaCegarLoop]: trace histogram [7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:42,278 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-28 03:24:42,470 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:42,470 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:42,470 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:42,470 INFO L85 PathProgramCache]: Analyzing trace with hash 616958939, now seen corresponding path program 5 times [2024-11-28 03:24:42,470 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:42,470 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2112428264] [2024-11-28 03:24:42,470 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-28 03:24:42,471 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:42,483 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2024-11-28 03:24:42,483 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:24:42,583 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 25 proven. 20 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-28 03:24:42,583 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:42,583 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2112428264] [2024-11-28 03:24:42,583 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2112428264] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-28 03:24:42,583 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1687924766] [2024-11-28 03:24:42,583 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-28 03:24:42,583 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:42,584 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:42,586 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:24:42,590 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-28 03:24:42,645 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2024-11-28 03:24:42,645 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:24:42,646 INFO L256 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-28 03:24:42,648 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:24:42,855 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 12 proven. 37 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:42,855 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:24:43,054 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:24:43,054 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1687924766] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:24:43,054 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-28 03:24:43,054 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 10, 10] total 23 [2024-11-28 03:24:43,055 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [235415590] [2024-11-28 03:24:43,055 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-28 03:24:43,055 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-28 03:24:43,055 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:43,056 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-28 03:24:43,056 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=384, Unknown=0, NotChecked=0, Total=506 [2024-11-28 03:24:43,056 INFO L87 Difference]: Start difference. First operand 61 states and 69 transitions. Second operand has 23 states, 23 states have (on average 2.6956521739130435) internal successors, (62), 23 states have internal predecessors, (62), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:43,194 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:43,194 INFO L93 Difference]: Finished difference Result 67 states and 74 transitions. [2024-11-28 03:24:43,195 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-28 03:24:43,195 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.6956521739130435) internal successors, (62), 23 states have internal predecessors, (62), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2024-11-28 03:24:43,195 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:43,196 INFO L225 Difference]: With dead ends: 67 [2024-11-28 03:24:43,196 INFO L226 Difference]: Without dead ends: 49 [2024-11-28 03:24:43,197 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=142, Invalid=410, Unknown=0, NotChecked=0, Total=552 [2024-11-28 03:24:43,197 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 512 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 550 SdHoareTripleChecker+Invalid, 167 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:43,198 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 550 Invalid, 167 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-28 03:24:43,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-28 03:24:43,203 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 49. [2024-11-28 03:24:43,205 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 36 states have (on average 1.0277777777777777) internal successors, (37), 37 states have internal predecessors, (37), 8 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-28 03:24:43,205 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 52 transitions. [2024-11-28 03:24:43,206 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 52 transitions. Word has length 27 [2024-11-28 03:24:43,206 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:43,206 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 52 transitions. [2024-11-28 03:24:43,206 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.6956521739130435) internal successors, (62), 23 states have internal predecessors, (62), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:24:43,206 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 52 transitions. [2024-11-28 03:24:43,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-28 03:24:43,207 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:43,207 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:43,216 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-28 03:24:43,411 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:43,412 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:43,412 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:43,412 INFO L85 PathProgramCache]: Analyzing trace with hash -1889018642, now seen corresponding path program 1 times [2024-11-28 03:24:43,412 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:43,412 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [484314800] [2024-11-28 03:24:43,413 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:43,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:43,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-28 03:24:43,442 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [801039306] [2024-11-28 03:24:43,442 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:43,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:43,442 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:43,444 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:24:43,447 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-28 03:24:43,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:24:43,504 INFO L256 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-28 03:24:43,506 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:24:43,702 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-28 03:24:43,702 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:24:44,077 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-28 03:24:44,077 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-28 03:24:44,077 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [484314800] [2024-11-28 03:24:44,078 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-28 03:24:44,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [801039306] [2024-11-28 03:24:44,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [801039306] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:24:44,078 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:24:44,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2024-11-28 03:24:44,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1175151425] [2024-11-28 03:24:44,078 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:24:44,079 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-28 03:24:44,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-28 03:24:44,080 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-28 03:24:44,080 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=203, Unknown=0, NotChecked=0, Total=240 [2024-11-28 03:24:44,080 INFO L87 Difference]: Start difference. First operand 49 states and 52 transitions. Second operand has 16 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 15 states have internal predecessors, (38), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-28 03:24:44,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:24:44,311 INFO L93 Difference]: Finished difference Result 49 states and 52 transitions. [2024-11-28 03:24:44,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-28 03:24:44,311 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 15 states have internal predecessors, (38), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 28 [2024-11-28 03:24:44,312 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:24:44,312 INFO L225 Difference]: With dead ends: 49 [2024-11-28 03:24:44,312 INFO L226 Difference]: Without dead ends: 23 [2024-11-28 03:24:44,313 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 38 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2024-11-28 03:24:44,314 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 1 mSDsluCounter, 376 mSDsCounter, 0 mSdLazyCounter, 178 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 410 SdHoareTripleChecker+Invalid, 178 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 178 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-28 03:24:44,314 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 410 Invalid, 178 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 178 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-28 03:24:44,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-28 03:24:44,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-28 03:24:44,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 14 states have (on average 1.0) internal successors, (14), 14 states have internal predecessors, (14), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-28 03:24:44,317 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2024-11-28 03:24:44,317 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 28 [2024-11-28 03:24:44,317 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:24:44,318 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2024-11-28 03:24:44,318 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.7142857142857144) internal successors, (38), 15 states have internal predecessors, (38), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-28 03:24:44,318 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2024-11-28 03:24:44,318 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-28 03:24:44,319 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:24:44,319 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:24:44,330 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-28 03:24:44,522 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:24:44,523 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:24:44,523 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:24:44,524 INFO L85 PathProgramCache]: Analyzing trace with hash -21288017, now seen corresponding path program 1 times [2024-11-28 03:24:44,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-28 03:24:44,524 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [68211763] [2024-11-28 03:24:44,524 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:24:44,524 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-28 03:24:44,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-28 03:24:44,536 INFO L357 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-28 03:24:44,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-28 03:24:44,561 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-28 03:24:44,563 INFO L340 BasicCegarLoop]: Counterexample is feasible [2024-11-28 03:24:44,565 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (1 of 2 remaining) [2024-11-28 03:24:44,568 INFO L782 garLoopResultBuilder]: Registering result UNKNOWN for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 2 remaining) [2024-11-28 03:24:44,570 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-11-28 03:24:44,573 INFO L422 BasicCegarLoop]: Path program histogram: [5, 1, 1, 1, 1, 1] [2024-11-28 03:24:44,596 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-28 03:24:44,602 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.11 03:24:44 BoogieIcfgContainer [2024-11-28 03:24:44,602 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-28 03:24:44,603 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-28 03:24:44,603 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-28 03:24:44,603 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-28 03:24:44,604 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 03:24:36" (3/4) ... [2024-11-28 03:24:44,606 INFO L149 WitnessPrinter]: No result that supports witness generation found [2024-11-28 03:24:44,607 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-28 03:24:44,608 INFO L158 Benchmark]: Toolchain (without parser) took 8529.20ms. Allocated memory is still 117.4MB. Free memory was 93.2MB in the beginning and 33.2MB in the end (delta: 60.0MB). Peak memory consumption was 55.6MB. Max. memory is 16.1GB. [2024-11-28 03:24:44,609 INFO L158 Benchmark]: CDTParser took 0.34ms. Allocated memory is still 117.4MB. Free memory is still 73.8MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-28 03:24:44,609 INFO L158 Benchmark]: CACSL2BoogieTranslator took 333.78ms. Allocated memory is still 117.4MB. Free memory was 93.0MB in the beginning and 80.9MB in the end (delta: 12.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-28 03:24:44,610 INFO L158 Benchmark]: Boogie Procedure Inliner took 43.99ms. Allocated memory is still 117.4MB. Free memory was 80.9MB in the beginning and 79.5MB in the end (delta: 1.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-28 03:24:44,611 INFO L158 Benchmark]: Boogie Preprocessor took 66.55ms. Allocated memory is still 117.4MB. Free memory was 79.5MB in the beginning and 78.0MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-28 03:24:44,611 INFO L158 Benchmark]: RCFGBuilder took 428.66ms. Allocated memory is still 117.4MB. Free memory was 78.0MB in the beginning and 64.7MB in the end (delta: 13.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-28 03:24:44,611 INFO L158 Benchmark]: TraceAbstraction took 7643.64ms. Allocated memory is still 117.4MB. Free memory was 64.1MB in the beginning and 34.4MB in the end (delta: 29.7MB). Peak memory consumption was 30.4MB. Max. memory is 16.1GB. [2024-11-28 03:24:44,612 INFO L158 Benchmark]: Witness Printer took 4.72ms. Allocated memory is still 117.4MB. Free memory was 34.4MB in the beginning and 33.2MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-28 03:24:44,614 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.34ms. Allocated memory is still 117.4MB. Free memory is still 73.8MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 333.78ms. Allocated memory is still 117.4MB. Free memory was 93.0MB in the beginning and 80.9MB in the end (delta: 12.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 43.99ms. Allocated memory is still 117.4MB. Free memory was 80.9MB in the beginning and 79.5MB in the end (delta: 1.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 66.55ms. Allocated memory is still 117.4MB. Free memory was 79.5MB in the beginning and 78.0MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 428.66ms. Allocated memory is still 117.4MB. Free memory was 78.0MB in the beginning and 64.7MB in the end (delta: 13.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 7643.64ms. Allocated memory is still 117.4MB. Free memory was 64.1MB in the beginning and 34.4MB in the end (delta: 29.7MB). Peak memory consumption was 30.4MB. Max. memory is 16.1GB. * Witness Printer took 4.72ms. Allocated memory is still 117.4MB. Free memory was 34.4MB in the beginning and 33.2MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - UnprovableResult [Line: 109]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: overapproximation of someBinaryFLOATComparisonOperation at line 98, overapproximation of someBinaryDOUBLEComparisonOperation at line 108, overapproximation of someBinaryArithmeticFLOAToperation at line 100, overapproximation of someBinaryArithmeticFLOAToperation at line 92, overapproximation of someBinaryArithmeticFLOAToperation at line 104, overapproximation of someBinaryArithmeticFLOAToperation at line 87, overapproximation of someBinaryArithmeticFLOAToperation at line 102. Possible FailurePath: [L115] COND FALSE !(__VERIFIER_nondet_int()) [L118] CALL main2() [L97] float IN = __VERIFIER_nondet_float(); [L98] CALL assume_abort_if_not(IN > -0.2f && IN < 0.2f) [L82] COND FALSE !(!cond) [L98] RET assume_abort_if_not(IN > -0.2f && IN < 0.2f) [L100] CALL, EXPR f(IN) VAL [\old(x)=112] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=112] [L100] RET, EXPR f(IN) VAL [IN=112] [L100] CALL, EXPR fp(IN) VAL [\old(x)=112] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=112] [L100] RET, EXPR fp(IN) VAL [IN=112] [L100] float x = IN - f(IN)/fp(IN); [L102] CALL, EXPR f(x) VAL [\old(x)=110] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=110] [L102] RET, EXPR f(x) VAL [IN=112, x=110] [L102] CALL, EXPR fp(x) VAL [\old(x)=110] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=110] [L102] RET, EXPR fp(x) VAL [IN=112, x=110] [L102] x = x - f(x)/fp(x) [L104] CALL, EXPR f(x) VAL [\old(x)=111] [L87] return x - (x*x*x)/6.0f + (x*x*x*x*x)/120.0f + (x*x*x*x*x*x*x)/5040.0f; VAL [\old(x)=111] [L104] RET, EXPR f(x) VAL [IN=112, x=111] [L104] CALL, EXPR fp(x) VAL [\old(x)=111] [L92] return 1 - (x*x)/2.0f + (x*x*x*x)/24.0f + (x*x*x*x*x*x)/720.0f; VAL [\old(x)=111] [L104] RET, EXPR fp(x) VAL [IN=112, x=111] [L104] x = x - f(x)/fp(x) [L108] COND TRUE !(x < 0.1) VAL [IN=112] [L109] reach_error() VAL [IN=112] - UnprovableResult [Line: 27]: Unable to prove that a call to reach_error is unreachable Unable to prove that a call to reach_error is unreachable Reason: Not analyzed. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 46 locations, 2 error locations. Started 1 CEGAR loops. OverallTime: 7.6s, OverallIterations: 10, TraceHistogramMax: 7, PathProgramHistogramMax: 5, EmptinessCheckTime: 0.0s, AutomataDifference: 1.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 47 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 43 mSDsluCounter, 2644 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2283 mSDsCounter, 36 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 920 IncrementalHoareTripleChecker+Invalid, 956 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 36 mSolverCounterUnsat, 361 mSDtfsCounter, 920 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 323 GetRequests, 210 SyntacticMatches, 2 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 411 ImplicationChecksByTransitivity, 1.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=69occurred in iteration=6, InterpolantAutomatonStates: 71, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 8 StatesRemovedByMinimization, 3 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 3.8s InterpolantComputationTime, 355 NumberOfCodeBlocks, 351 NumberOfCodeBlocksAsserted, 42 NumberOfCheckSat, 392 ConstructedInterpolants, 0 QuantifiedInterpolants, 1983 SizeOfPredicates, 17 NumberOfNonLiveVariables, 549 ConjunctsInSsa, 95 ConjunctsInUnsatCore, 19 InterpolantComputations, 3 PerfectInterpolantSequences, 108/420 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available RESULT: Ultimate could not prove your program: unable to determine feasibility of some traces [2024-11-28 03:24:44,641 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/config/AutomizerReach.xml -i ../../sv-benchmarks/c/combinations/gcd_4+newton_3_1.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ad6236f3b1535aee53ef497474ba76faac9143455d497d8d917066c0b5859668 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-d790fec [2024-11-28 03:24:47,490 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-28 03:24:47,620 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2024-11-28 03:24:47,630 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-28 03:24:47,634 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-28 03:24:47,708 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-28 03:24:47,714 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-28 03:24:47,714 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-28 03:24:47,715 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-28 03:24:47,715 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-28 03:24:47,715 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-28 03:24:47,715 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-28 03:24:47,716 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-28 03:24:47,716 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-28 03:24:47,716 INFO L153 SettingsManager]: * Use SBE=true [2024-11-28 03:24:47,716 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-28 03:24:47,720 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-28 03:24:47,720 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-28 03:24:47,721 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2024-11-28 03:24:47,722 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-28 03:24:47,722 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-28 03:24:47,722 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-28 03:24:47,722 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-28 03:24:47,722 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-28 03:24:47,722 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-28 03:24:47,722 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-28 03:24:47,722 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-28 03:24:47,723 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Compute procedure contracts=false [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-28 03:24:47,723 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-28 03:24:47,724 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-28 03:24:47,724 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-28 03:24:47,724 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-28 03:24:47,724 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ad6236f3b1535aee53ef497474ba76faac9143455d497d8d917066c0b5859668 [2024-11-28 03:24:48,050 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-28 03:24:48,059 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-28 03:24:48,062 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-28 03:24:48,063 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-28 03:24:48,064 INFO L274 PluginConnector]: CDTParser initialized [2024-11-28 03:24:48,065 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/../../sv-benchmarks/c/combinations/gcd_4+newton_3_1.i [2024-11-28 03:24:51,061 INFO L533 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/a0c68574a/00d0d31df1404802b309bfdc78c962de/FLAG580ba527a [2024-11-28 03:24:51,293 INFO L384 CDTParser]: Found 1 translation units. [2024-11-28 03:24:51,295 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i [2024-11-28 03:24:51,312 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/a0c68574a/00d0d31df1404802b309bfdc78c962de/FLAG580ba527a [2024-11-28 03:24:51,337 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/data/a0c68574a/00d0d31df1404802b309bfdc78c962de [2024-11-28 03:24:51,340 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-28 03:24:51,341 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-28 03:24:51,343 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-28 03:24:51,343 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-28 03:24:51,348 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-28 03:24:51,349 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,350 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6b377161 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51, skipping insertion in model container [2024-11-28 03:24:51,350 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,378 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-28 03:24:51,579 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[1224,1237] [2024-11-28 03:24:51,624 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[2848,2861] [2024-11-28 03:24:51,625 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-28 03:24:51,639 INFO L200 MainTranslator]: Completed pre-run [2024-11-28 03:24:51,657 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[1224,1237] [2024-11-28 03:24:51,679 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/sv-benchmarks/c/combinations/gcd_4+newton_3_1.i[2848,2861] [2024-11-28 03:24:51,683 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-28 03:24:51,706 INFO L204 MainTranslator]: Completed translation [2024-11-28 03:24:51,706 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51 WrapperNode [2024-11-28 03:24:51,707 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-28 03:24:51,708 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-28 03:24:51,708 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-28 03:24:51,708 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-28 03:24:51,717 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,734 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,762 INFO L138 Inliner]: procedures = 28, calls = 28, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 80 [2024-11-28 03:24:51,764 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-28 03:24:51,764 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-28 03:24:51,765 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-28 03:24:51,765 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-28 03:24:51,775 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,775 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,779 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,796 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-28 03:24:51,796 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,796 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,810 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,811 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,817 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,819 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,823 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,826 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-28 03:24:51,830 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-28 03:24:51,830 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-28 03:24:51,830 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-28 03:24:51,831 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (1/1) ... [2024-11-28 03:24:51,841 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-28 03:24:51,855 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:24:51,866 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-28 03:24:51,869 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-28 03:24:51,894 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-28 03:24:51,894 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-28 03:24:51,894 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-28 03:24:51,894 INFO L130 BoogieDeclarations]: Found specification of procedure fp [2024-11-28 03:24:51,894 INFO L138 BoogieDeclarations]: Found implementation of procedure fp [2024-11-28 03:24:51,894 INFO L130 BoogieDeclarations]: Found specification of procedure f [2024-11-28 03:24:51,894 INFO L138 BoogieDeclarations]: Found implementation of procedure f [2024-11-28 03:24:51,894 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-28 03:24:51,895 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-28 03:24:51,895 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-28 03:24:51,895 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-28 03:24:51,962 INFO L234 CfgBuilder]: Building ICFG [2024-11-28 03:24:51,964 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-28 03:25:05,873 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2024-11-28 03:25:05,873 INFO L283 CfgBuilder]: Performing block encoding [2024-11-28 03:25:05,885 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-28 03:25:05,885 INFO L312 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-28 03:25:05,886 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 03:25:05 BoogieIcfgContainer [2024-11-28 03:25:05,886 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-28 03:25:05,888 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-28 03:25:05,889 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-28 03:25:05,893 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-28 03:25:05,893 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.11 03:24:51" (1/3) ... [2024-11-28 03:25:05,894 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@fc89ec1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 03:25:05, skipping insertion in model container [2024-11-28 03:25:05,894 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 03:24:51" (2/3) ... [2024-11-28 03:25:05,894 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@fc89ec1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.11 03:25:05, skipping insertion in model container [2024-11-28 03:25:05,894 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 03:25:05" (3/3) ... [2024-11-28 03:25:05,896 INFO L128 eAbstractionObserver]: Analyzing ICFG gcd_4+newton_3_1.i [2024-11-28 03:25:05,911 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-28 03:25:05,912 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG gcd_4+newton_3_1.i that has 4 procedures, 46 locations, 1 initial locations, 1 loop locations, and 2 error locations. [2024-11-28 03:25:05,963 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-28 03:25:05,977 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;@8989291, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-28 03:25:05,977 INFO L334 AbstractCegarLoop]: Starting to check reachability of 2 error locations. [2024-11-28 03:25:05,984 INFO L276 IsEmpty]: Start isEmpty. Operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-28 03:25:05,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-28 03:25:05,990 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:25:05,991 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:25:05,991 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:25:05,996 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:25:05,996 INFO L85 PathProgramCache]: Analyzing trace with hash -1780387208, now seen corresponding path program 1 times [2024-11-28 03:25:06,006 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:25:06,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [347156879] [2024-11-28 03:25:06,007 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:25:06,007 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:06,007 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:25:06,011 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:25:06,016 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-28 03:25:06,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:25:06,117 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-28 03:25:06,121 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:25:06,216 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:25:06,216 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-28 03:25:06,217 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:25:06,217 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [347156879] [2024-11-28 03:25:06,218 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [347156879] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-28 03:25:06,218 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-28 03:25:06,218 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-28 03:25:06,220 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [692941058] [2024-11-28 03:25:06,220 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-28 03:25:06,224 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-28 03:25:06,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:25:06,243 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-28 03:25:06,244 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:25:06,246 INFO L87 Difference]: Start difference. First operand has 46 states, 31 states have (on average 1.3870967741935485) internal successors, (43), 33 states have internal predecessors, (43), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:06,369 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:25:06,370 INFO L93 Difference]: Finished difference Result 90 states and 123 transitions. [2024-11-28 03:25:06,371 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-28 03:25:06,373 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2024-11-28 03:25:06,374 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:25:06,381 INFO L225 Difference]: With dead ends: 90 [2024-11-28 03:25:06,381 INFO L226 Difference]: Without dead ends: 42 [2024-11-28 03:25:06,397 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:25:06,405 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 7 mSDsluCounter, 46 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-28 03:25:06,406 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 96 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-28 03:25:06,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-28 03:25:06,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2024-11-28 03:25:06,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:25:06,450 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 47 transitions. [2024-11-28 03:25:06,452 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 47 transitions. Word has length 11 [2024-11-28 03:25:06,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:25:06,453 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 47 transitions. [2024-11-28 03:25:06,453 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:06,453 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 47 transitions. [2024-11-28 03:25:06,455 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-28 03:25:06,455 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:25:06,455 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:25:06,466 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-28 03:25:06,656 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:06,656 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:25:06,657 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:25:06,657 INFO L85 PathProgramCache]: Analyzing trace with hash 1301222473, now seen corresponding path program 1 times [2024-11-28 03:25:06,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:25:06,658 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [362520446] [2024-11-28 03:25:06,658 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:25:06,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:06,658 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:25:06,660 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:25:06,661 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-28 03:25:06,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:25:06,747 INFO L256 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-28 03:25:06,749 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:25:06,822 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:25:06,822 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-28 03:25:06,823 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:25:06,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [362520446] [2024-11-28 03:25:06,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [362520446] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-28 03:25:06,823 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-28 03:25:06,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-28 03:25:06,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2014866985] [2024-11-28 03:25:06,824 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-28 03:25:06,825 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-28 03:25:06,825 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:25:06,826 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-28 03:25:06,826 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:25:06,826 INFO L87 Difference]: Start difference. First operand 39 states and 47 transitions. Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:06,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:25:06,948 INFO L93 Difference]: Finished difference Result 55 states and 68 transitions. [2024-11-28 03:25:06,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-28 03:25:06,948 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2024-11-28 03:25:06,949 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:25:06,950 INFO L225 Difference]: With dead ends: 55 [2024-11-28 03:25:06,950 INFO L226 Difference]: Without dead ends: 41 [2024-11-28 03:25:06,950 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-28 03:25:06,951 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 4 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-28 03:25:06,952 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 79 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-28 03:25:06,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-28 03:25:06,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2024-11-28 03:25:06,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:25:06,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2024-11-28 03:25:06,960 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 13 [2024-11-28 03:25:06,960 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:25:06,961 INFO L471 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2024-11-28 03:25:06,961 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 3 states have internal predecessors, (12), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:06,961 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2024-11-28 03:25:06,961 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-28 03:25:06,961 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:25:06,962 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:25:06,970 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-28 03:25:07,162 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:07,162 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:25:07,163 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:25:07,163 INFO L85 PathProgramCache]: Analyzing trace with hash 299954435, now seen corresponding path program 1 times [2024-11-28 03:25:07,163 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:25:07,163 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [58296270] [2024-11-28 03:25:07,164 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:25:07,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:07,164 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:25:07,167 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:25:07,169 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-28 03:25:07,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:25:07,236 INFO L256 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-28 03:25:07,238 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:25:07,588 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:25:07,589 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:25:07,841 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:25:07,841 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:25:07,841 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [58296270] [2024-11-28 03:25:07,841 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [58296270] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:25:07,842 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:25:07,842 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2024-11-28 03:25:07,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [85508940] [2024-11-28 03:25:07,842 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:25:07,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-28 03:25:07,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:25:07,843 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-28 03:25:07,844 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-28 03:25:07,844 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 6 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:08,172 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:25:08,173 INFO L93 Difference]: Finished difference Result 59 states and 73 transitions. [2024-11-28 03:25:08,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-28 03:25:08,177 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2024-11-28 03:25:08,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:25:08,178 INFO L225 Difference]: With dead ends: 59 [2024-11-28 03:25:08,180 INFO L226 Difference]: Without dead ends: 46 [2024-11-28 03:25:08,180 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2024-11-28 03:25:08,181 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 5 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 113 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-28 03:25:08,183 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 113 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-28 03:25:08,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-28 03:25:08,197 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 44. [2024-11-28 03:25:08,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:25:08,199 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 52 transitions. [2024-11-28 03:25:08,199 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 52 transitions. Word has length 15 [2024-11-28 03:25:08,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:25:08,199 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 52 transitions. [2024-11-28 03:25:08,199 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.5) internal successors, (21), 6 states have internal predecessors, (21), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:08,200 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 52 transitions. [2024-11-28 03:25:08,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-28 03:25:08,200 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:25:08,200 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:25:08,215 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-28 03:25:08,401 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:08,401 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:25:08,401 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:25:08,402 INFO L85 PathProgramCache]: Analyzing trace with hash 1688852343, now seen corresponding path program 1 times [2024-11-28 03:25:08,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:25:08,402 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1048822251] [2024-11-28 03:25:08,402 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:25:08,402 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:08,403 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:25:08,404 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:25:08,409 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-28 03:25:08,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:25:08,477 INFO L256 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-28 03:25:08,479 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:25:09,080 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:25:09,081 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:25:09,661 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-28 03:25:09,662 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:25:09,662 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1048822251] [2024-11-28 03:25:09,662 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1048822251] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:25:09,662 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:25:09,662 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2024-11-28 03:25:09,662 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998023362] [2024-11-28 03:25:09,662 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:25:09,663 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-28 03:25:09,663 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:25:09,664 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-28 03:25:09,664 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2024-11-28 03:25:09,664 INFO L87 Difference]: Start difference. First operand 44 states and 52 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:10,595 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:25:10,595 INFO L93 Difference]: Finished difference Result 67 states and 83 transitions. [2024-11-28 03:25:10,597 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-28 03:25:10,597 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 19 [2024-11-28 03:25:10,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:25:10,598 INFO L225 Difference]: With dead ends: 67 [2024-11-28 03:25:10,599 INFO L226 Difference]: Without dead ends: 53 [2024-11-28 03:25:10,599 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=57, Invalid=99, Unknown=0, NotChecked=0, Total=156 [2024-11-28 03:25:10,600 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 7 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-28 03:25:10,602 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 185 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-28 03:25:10,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2024-11-28 03:25:10,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2024-11-28 03:25:10,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-28 03:25:10,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 62 transitions. [2024-11-28 03:25:10,625 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 62 transitions. Word has length 19 [2024-11-28 03:25:10,625 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:25:10,625 INFO L471 AbstractCegarLoop]: Abstraction has 52 states and 62 transitions. [2024-11-28 03:25:10,625 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:10,625 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 62 transitions. [2024-11-28 03:25:10,626 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-11-28 03:25:10,626 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:25:10,626 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:25:10,634 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-28 03:25:10,827 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:10,827 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:25:10,827 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:25:10,827 INFO L85 PathProgramCache]: Analyzing trace with hash -1417329111, now seen corresponding path program 2 times [2024-11-28 03:25:10,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:25:10,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1628744174] [2024-11-28 03:25:10,828 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-28 03:25:10,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:25:10,828 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:25:10,830 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:25:10,831 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-28 03:25:10,898 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-28 03:25:10,899 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:25:10,902 INFO L256 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-28 03:25:10,905 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:25:12,517 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-28 03:25:12,517 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:25:22,227 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-28 03:25:22,227 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:25:22,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1628744174] [2024-11-28 03:25:22,228 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1628744174] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:25:22,228 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:25:22,228 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 12] total 20 [2024-11-28 03:25:22,228 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [33835665] [2024-11-28 03:25:22,229 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:25:22,229 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-28 03:25:22,229 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:25:22,230 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-28 03:25:22,230 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=322, Unknown=0, NotChecked=0, Total=380 [2024-11-28 03:25:22,231 INFO L87 Difference]: Start difference. First operand 52 states and 62 transitions. Second operand has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:25:40,405 WARN L286 SmtUtils]: Spent 13.40s on a formula simplification that was a NOOP. DAG size: 30 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-28 03:25:44,893 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:25:48,902 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:25:52,909 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:10,045 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:15,469 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:19,156 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.69s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:23,163 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:27,170 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:33,083 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.25s for a HTC check with result INVALID. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:37,788 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, BitVec], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-28 03:26:40,238 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:26:40,238 INFO L93 Difference]: Finished difference Result 76 states and 94 transitions. [2024-11-28 03:26:40,242 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-28 03:26:40,243 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2024-11-28 03:26:40,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:26:40,244 INFO L225 Difference]: With dead ends: 76 [2024-11-28 03:26:40,244 INFO L226 Difference]: Without dead ends: 73 [2024-11-28 03:26:40,245 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 42.4s TimeCoverageRelationStatistics Valid=96, Invalid=503, Unknown=1, NotChecked=0, Total=600 [2024-11-28 03:26:40,246 INFO L435 NwaCegarLoop]: 37 mSDtfsCounter, 3 mSDsluCounter, 384 mSDsCounter, 0 mSdLazyCounter, 230 mSolverCounterSat, 6 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 43.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 421 SdHoareTripleChecker+Invalid, 244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 230 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 43.5s IncrementalHoareTripleChecker+Time [2024-11-28 03:26:40,247 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 421 Invalid, 244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 230 Invalid, 8 Unknown, 0 Unchecked, 43.5s Time] [2024-11-28 03:26:40,248 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-28 03:26:40,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2024-11-28 03:26:40,264 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 53 states have (on average 1.2264150943396226) internal successors, (65), 57 states have internal predecessors, (65), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-28 03:26:40,265 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 87 transitions. [2024-11-28 03:26:40,266 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 87 transitions. Word has length 23 [2024-11-28 03:26:40,266 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:26:40,266 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 87 transitions. [2024-11-28 03:26:40,266 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:26:40,266 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 87 transitions. [2024-11-28 03:26:40,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-28 03:26:40,268 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:26:40,268 INFO L218 NwaCegarLoop]: trace histogram [6, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:26:40,276 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-28 03:26:40,468 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:26:40,469 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:26:40,469 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:26:40,469 INFO L85 PathProgramCache]: Analyzing trace with hash -1196039389, now seen corresponding path program 3 times [2024-11-28 03:26:40,470 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:26:40,470 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [577570954] [2024-11-28 03:26:40,470 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-28 03:26:40,470 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:26:40,470 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:26:40,472 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:26:40,474 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-28 03:26:40,594 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-11-28 03:26:40,594 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:26:40,601 INFO L256 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-28 03:26:40,605 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:26:41,437 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 15 proven. 20 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-28 03:26:41,437 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:26:45,600 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 19 proven. 16 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-28 03:26:45,601 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:26:45,601 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [577570954] [2024-11-28 03:26:45,601 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [577570954] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:26:45,602 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:26:45,602 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 13 [2024-11-28 03:26:45,602 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [248087378] [2024-11-28 03:26:45,602 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:26:45,603 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-28 03:26:45,604 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:26:45,604 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-28 03:26:45,605 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=103, Unknown=0, NotChecked=0, Total=156 [2024-11-28 03:26:45,605 INFO L87 Difference]: Start difference. First operand 71 states and 87 transitions. Second operand has 13 states, 13 states have (on average 2.923076923076923) internal successors, (38), 13 states have internal predecessors, (38), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:26:49,243 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:26:49,244 INFO L93 Difference]: Finished difference Result 104 states and 132 transitions. [2024-11-28 03:26:49,246 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-28 03:26:49,247 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.923076923076923) internal successors, (38), 13 states have internal predecessors, (38), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 25 [2024-11-28 03:26:49,248 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:26:49,249 INFO L225 Difference]: With dead ends: 104 [2024-11-28 03:26:49,250 INFO L226 Difference]: Without dead ends: 74 [2024-11-28 03:26:49,251 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=96, Invalid=176, Unknown=0, NotChecked=0, Total=272 [2024-11-28 03:26:49,252 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 144 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-28 03:26:49,253 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 183 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2024-11-28 03:26:49,256 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-28 03:26:49,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 72. [2024-11-28 03:26:49,272 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 72 states, 55 states have (on average 1.2363636363636363) internal successors, (68), 58 states have internal predecessors, (68), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-28 03:26:49,275 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 72 states to 72 states and 88 transitions. [2024-11-28 03:26:49,276 INFO L78 Accepts]: Start accepts. Automaton has 72 states and 88 transitions. Word has length 25 [2024-11-28 03:26:49,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:26:49,276 INFO L471 AbstractCegarLoop]: Abstraction has 72 states and 88 transitions. [2024-11-28 03:26:49,277 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.923076923076923) internal successors, (38), 13 states have internal predecessors, (38), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:26:49,277 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 88 transitions. [2024-11-28 03:26:49,278 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-28 03:26:49,278 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:26:49,278 INFO L218 NwaCegarLoop]: trace histogram [5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:26:49,287 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-28 03:26:49,480 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:26:49,480 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:26:49,480 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:26:49,480 INFO L85 PathProgramCache]: Analyzing trace with hash -1889018642, now seen corresponding path program 1 times [2024-11-28 03:26:49,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:26:49,481 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1209881052] [2024-11-28 03:26:49,481 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:26:49,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:26:49,481 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:26:49,483 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:26:49,487 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-28 03:26:49,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-28 03:26:49,579 INFO L256 TraceCheckSpWp]: Trace formula consists of 63 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-28 03:26:49,582 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:26:52,163 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-28 03:26:52,164 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:27:19,913 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-28 03:27:19,913 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:27:19,913 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1209881052] [2024-11-28 03:27:19,913 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1209881052] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:27:19,913 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:27:19,914 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 24 [2024-11-28 03:27:19,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [952682802] [2024-11-28 03:27:19,914 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:27:19,914 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-28 03:27:19,914 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:27:19,915 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-28 03:27:19,916 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=472, Unknown=0, NotChecked=0, Total=552 [2024-11-28 03:27:19,916 INFO L87 Difference]: Start difference. First operand 72 states and 88 transitions. Second operand has 24 states, 20 states have (on average 2.1) internal successors, (42), 21 states have internal predecessors, (42), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-28 03:27:41,425 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:27:41,425 INFO L93 Difference]: Finished difference Result 91 states and 113 transitions. [2024-11-28 03:27:41,430 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-28 03:27:41,431 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 20 states have (on average 2.1) internal successors, (42), 21 states have internal predecessors, (42), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 28 [2024-11-28 03:27:41,431 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:27:41,434 INFO L225 Difference]: With dead ends: 91 [2024-11-28 03:27:41,434 INFO L226 Difference]: Without dead ends: 81 [2024-11-28 03:27:41,436 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 31.8s TimeCoverageRelationStatistics Valid=114, Invalid=642, Unknown=0, NotChecked=0, Total=756 [2024-11-28 03:27:41,437 INFO L435 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 460 mSDsCounter, 0 mSdLazyCounter, 343 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 492 SdHoareTripleChecker+Invalid, 352 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 343 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.6s IncrementalHoareTripleChecker+Time [2024-11-28 03:27:41,437 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 492 Invalid, 352 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 343 Invalid, 0 Unknown, 0 Unchecked, 12.6s Time] [2024-11-28 03:27:41,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-11-28 03:27:41,461 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 81. [2024-11-28 03:27:41,461 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 64 states have (on average 1.234375) internal successors, (79), 67 states have internal predecessors, (79), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-28 03:27:41,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 100 transitions. [2024-11-28 03:27:41,463 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 100 transitions. Word has length 28 [2024-11-28 03:27:41,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:27:41,463 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 100 transitions. [2024-11-28 03:27:41,464 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 20 states have (on average 2.1) internal successors, (42), 21 states have internal predecessors, (42), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-28 03:27:41,464 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 100 transitions. [2024-11-28 03:27:41,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-28 03:27:41,465 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:27:41,465 INFO L218 NwaCegarLoop]: trace histogram [7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:27:41,476 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-28 03:27:41,666 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:27:41,666 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:27:41,666 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:27:41,667 INFO L85 PathProgramCache]: Analyzing trace with hash 1268151387, now seen corresponding path program 4 times [2024-11-28 03:27:41,667 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:27:41,667 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [897054550] [2024-11-28 03:27:41,667 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-28 03:27:41,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:27:41,667 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 [2024-11-28 03:27:41,669 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-28 03:27:41,670 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-28 03:27:41,778 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-28 03:27:41,778 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-28 03:27:41,789 INFO L256 TraceCheckSpWp]: Trace formula consists of 62 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-28 03:27:41,794 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-28 03:27:42,772 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 22 proven. 25 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-28 03:27:42,772 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-28 03:27:47,247 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 25 proven. 22 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-28 03:27:47,247 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-28 03:27:47,247 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [897054550] [2024-11-28 03:27:47,248 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [897054550] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-28 03:27:47,248 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-28 03:27:47,248 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 15 [2024-11-28 03:27:47,248 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1336621221] [2024-11-28 03:27:47,248 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-28 03:27:47,248 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-28 03:27:47,248 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-28 03:27:47,249 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-28 03:27:47,249 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=141, Unknown=0, NotChecked=0, Total=210 [2024-11-28 03:27:47,249 INFO L87 Difference]: Start difference. First operand 81 states and 100 transitions. Second operand has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 15 states have internal predecessors, (40), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:27:47,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-28 03:27:47,946 INFO L93 Difference]: Finished difference Result 81 states and 100 transitions. [2024-11-28 03:27:47,946 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-28 03:27:47,946 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 15 states have internal predecessors, (40), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2024-11-28 03:27:47,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-28 03:27:47,947 INFO L225 Difference]: With dead ends: 81 [2024-11-28 03:27:47,947 INFO L226 Difference]: Without dead ends: 23 [2024-11-28 03:27:47,948 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=79, Invalid=161, Unknown=0, NotChecked=0, Total=240 [2024-11-28 03:27:47,948 INFO L435 NwaCegarLoop]: 27 mSDtfsCounter, 0 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 83 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 83 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-28 03:27:47,949 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 157 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 83 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-28 03:27:47,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-28 03:27:47,952 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2024-11-28 03:27:47,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 14 states have (on average 1.0) internal successors, (14), 14 states have internal predecessors, (14), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-28 03:27:47,953 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 26 transitions. [2024-11-28 03:27:47,953 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 26 transitions. Word has length 27 [2024-11-28 03:27:47,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-28 03:27:47,953 INFO L471 AbstractCegarLoop]: Abstraction has 23 states and 26 transitions. [2024-11-28 03:27:47,954 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.6666666666666665) internal successors, (40), 15 states have internal predecessors, (40), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-28 03:27:47,954 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 26 transitions. [2024-11-28 03:27:47,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-11-28 03:27:47,955 INFO L210 NwaCegarLoop]: Found error trace [2024-11-28 03:27:47,955 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-28 03:27:47,967 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-28 03:27:48,155 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-28 03:27:48,156 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-28 03:27:48,156 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-28 03:27:48,156 INFO L85 PathProgramCache]: Analyzing trace with hash -21288017, now seen corresponding path program 1 times [2024-11-28 03:27:48,157 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-28 03:27:48,157 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [722943616] [2024-11-28 03:27:48,157 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-28 03:27:48,157 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-28 03:27:48,157 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/mathsat [2024-11-28 03:27:48,159 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-28 03:27:48,161 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_faaffcb0-ebd4-44a9-8c9d-e5bb41db1019/bin/uautomizer-verify-aQ6SnzHsRB/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (10)] Waiting until timeout for monitored process