./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c --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_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/config/AutomizerReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1 --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 f5697d76d3e5ae232d0e056ee307ac88ca38e983a94c4765bc5d51f77e79d2f7 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-d790fec [2024-12-02 06:22:05,148 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-12-02 06:22:05,200 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-12-02 06:22:05,203 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-12-02 06:22:05,203 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-12-02 06:22:05,222 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-12-02 06:22:05,222 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-12-02 06:22:05,222 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-12-02 06:22:05,223 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-12-02 06:22:05,223 INFO L153 SettingsManager]: * Use memory slicer=true [2024-12-02 06:22:05,223 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-12-02 06:22:05,223 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-12-02 06:22:05,223 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-12-02 06:22:05,223 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * Use SBE=true [2024-12-02 06:22:05,224 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * sizeof long=4 [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-12-02 06:22:05,224 INFO L153 SettingsManager]: * sizeof long double=12 [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * Use constant arrays=true [2024-12-02 06:22:05,225 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-12-02 06:22:05,225 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-12-02 06:22:05,225 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-12-02 06:22:05,226 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Compute procedure contracts=false [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-12-02 06:22:05,226 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-12-02 06:22:05,227 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-12-02 06:22:05,227 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-12-02 06:22:05,227 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_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1 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 -> f5697d76d3e5ae232d0e056ee307ac88ca38e983a94c4765bc5d51f77e79d2f7 [2024-12-02 06:22:05,420 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-12-02 06:22:05,427 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-12-02 06:22:05,429 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-12-02 06:22:05,430 INFO L270 PluginConnector]: Initializing CDTParser... [2024-12-02 06:22:05,430 INFO L274 PluginConnector]: CDTParser initialized [2024-12-02 06:22:05,432 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c [2024-12-02 06:22:08,088 INFO L533 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/data/6f86efd5e/f5574a168fe844e9a51c191ff5654a3f/FLAG0ca09596a [2024-12-02 06:22:08,284 INFO L384 CDTParser]: Found 1 translation units. [2024-12-02 06:22:08,285 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c [2024-12-02 06:22:08,292 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/data/6f86efd5e/f5574a168fe844e9a51c191ff5654a3f/FLAG0ca09596a [2024-12-02 06:22:08,673 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/data/6f86efd5e/f5574a168fe844e9a51c191ff5654a3f [2024-12-02 06:22:08,675 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-12-02 06:22:08,676 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-12-02 06:22:08,677 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-12-02 06:22:08,677 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-12-02 06:22:08,680 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-12-02 06:22:08,681 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,681 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6968d821 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08, skipping insertion in model container [2024-12-02 06:22:08,681 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,691 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-12-02 06:22:08,791 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_ca047d8e-c910-43a7-a003-76e96eca98f5/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c[490,503] [2024-12-02 06:22:08,810 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-12-02 06:22:08,817 INFO L200 MainTranslator]: Completed pre-run [2024-12-02 06:22:08,825 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_ca047d8e-c910-43a7-a003-76e96eca98f5/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_valuebound100.c[490,503] [2024-12-02 06:22:08,835 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-12-02 06:22:08,847 INFO L204 MainTranslator]: Completed translation [2024-12-02 06:22:08,847 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08 WrapperNode [2024-12-02 06:22:08,847 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-12-02 06:22:08,848 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-12-02 06:22:08,848 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-12-02 06:22:08,848 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-12-02 06:22:08,853 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,858 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,870 INFO L138 Inliner]: procedures = 14, calls = 19, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 77 [2024-12-02 06:22:08,871 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-12-02 06:22:08,871 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-12-02 06:22:08,871 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-12-02 06:22:08,872 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-12-02 06:22:08,878 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,878 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,880 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,889 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-12-02 06:22:08,890 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,890 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,893 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,893 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,897 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,898 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,898 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,900 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-12-02 06:22:08,901 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-12-02 06:22:08,901 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-12-02 06:22:08,901 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-12-02 06:22:08,902 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (1/1) ... [2024-12-02 06:22:08,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-12-02 06:22:08,916 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:08,926 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-12-02 06:22:08,928 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-12-02 06:22:08,947 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-12-02 06:22:08,947 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-12-02 06:22:08,947 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-12-02 06:22:08,947 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-12-02 06:22:08,948 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-12-02 06:22:08,948 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-12-02 06:22:08,948 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-12-02 06:22:08,948 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-12-02 06:22:08,991 INFO L234 CfgBuilder]: Building ICFG [2024-12-02 06:22:08,993 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2024-12-02 06:22:09,138 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-12-02 06:22:09,138 INFO L283 CfgBuilder]: Performing block encoding [2024-12-02 06:22:09,147 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-12-02 06:22:09,147 INFO L312 CfgBuilder]: Removed 4 assume(true) statements. [2024-12-02 06:22:09,148 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:22:09 BoogieIcfgContainer [2024-12-02 06:22:09,148 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-12-02 06:22:09,149 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-12-02 06:22:09,149 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-12-02 06:22:09,153 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-12-02 06:22:09,153 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.12 06:22:08" (1/3) ... [2024-12-02 06:22:09,154 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c11aaa5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 06:22:09, skipping insertion in model container [2024-12-02 06:22:09,154 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.12 06:22:08" (2/3) ... [2024-12-02 06:22:09,154 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3c11aaa5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.12 06:22:09, skipping insertion in model container [2024-12-02 06:22:09,154 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.12 06:22:09" (3/3) ... [2024-12-02 06:22:09,155 INFO L128 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound100.c [2024-12-02 06:22:09,166 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-12-02 06:22:09,167 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG egcd2-ll_valuebound100.c that has 3 procedures, 33 locations, 1 initial locations, 2 loop locations, and 1 error locations. [2024-12-02 06:22:09,207 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-12-02 06:22:09,217 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;@555a02c0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-12-02 06:22:09,217 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-12-02 06:22:09,220 INFO L276 IsEmpty]: Start isEmpty. Operand has 33 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-12-02 06:22:09,226 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-12-02 06:22:09,226 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:09,226 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:09,227 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:09,231 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:09,231 INFO L85 PathProgramCache]: Analyzing trace with hash 1694190779, now seen corresponding path program 1 times [2024-12-02 06:22:09,237 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:09,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [504848601] [2024-12-02 06:22:09,238 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:09,238 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:09,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:09,363 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-12-02 06:22:09,363 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:09,363 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [504848601] [2024-12-02 06:22:09,364 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [504848601] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:09,364 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1192474507] [2024-12-02 06:22:09,364 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:09,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:09,365 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:09,369 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:09,370 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-12-02 06:22:09,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:09,441 INFO L256 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-12-02 06:22:09,445 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:09,457 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-12-02 06:22:09,457 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-12-02 06:22:09,457 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1192474507] provided 1 perfect and 0 imperfect interpolant sequences [2024-12-02 06:22:09,457 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:22:09,458 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-12-02 06:22:09,459 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1354262895] [2024-12-02 06:22:09,459 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-12-02 06:22:09,462 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-12-02 06:22:09,462 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:09,476 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-12-02 06:22:09,476 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-12-02 06:22:09,478 INFO L87 Difference]: Start difference. First operand has 33 states, 18 states have (on average 1.4444444444444444) internal successors, (26), 19 states have internal predecessors, (26), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-12-02 06:22:09,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:09,494 INFO L93 Difference]: Finished difference Result 63 states and 108 transitions. [2024-12-02 06:22:09,495 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-12-02 06:22:09,496 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2024-12-02 06:22:09,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:09,501 INFO L225 Difference]: With dead ends: 63 [2024-12-02 06:22:09,501 INFO L226 Difference]: Without dead ends: 29 [2024-12-02 06:22:09,503 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-12-02 06:22:09,505 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:09,506 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-12-02 06:22:09,516 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-12-02 06:22:09,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-12-02 06:22:09,529 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 16 states have internal predecessors, (17), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-12-02 06:22:09,532 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 40 transitions. [2024-12-02 06:22:09,534 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 40 transitions. Word has length 39 [2024-12-02 06:22:09,534 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:09,534 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 40 transitions. [2024-12-02 06:22:09,534 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.5) internal successors, (13), 2 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 2 states have call successors, (6) [2024-12-02 06:22:09,535 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 40 transitions. [2024-12-02 06:22:09,536 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-12-02 06:22:09,536 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:09,536 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:09,546 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-12-02 06:22:09,736 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-12-02 06:22:09,737 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:09,737 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:09,737 INFO L85 PathProgramCache]: Analyzing trace with hash -979027133, now seen corresponding path program 1 times [2024-12-02 06:22:09,737 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:09,738 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1086330745] [2024-12-02 06:22:09,738 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:09,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:09,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:09,984 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-12-02 06:22:09,984 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:09,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1086330745] [2024-12-02 06:22:09,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1086330745] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:09,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1028554122] [2024-12-02 06:22:09,985 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:09,985 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:09,985 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:09,987 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:09,990 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-12-02 06:22:10,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:10,048 INFO L256 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-12-02 06:22:10,051 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:10,246 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 3 proven. 12 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-12-02 06:22:10,246 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:10,377 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1028554122] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:10,378 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-12-02 06:22:10,378 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9] total 11 [2024-12-02 06:22:10,378 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1665479025] [2024-12-02 06:22:10,378 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:10,378 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-12-02 06:22:10,378 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:10,379 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-12-02 06:22:10,379 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2024-12-02 06:22:10,380 INFO L87 Difference]: Start difference. First operand 29 states and 40 transitions. Second operand has 11 states, 10 states have (on average 1.8) internal successors, (18), 8 states have internal predecessors, (18), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-12-02 06:22:10,599 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:10,599 INFO L93 Difference]: Finished difference Result 48 states and 65 transitions. [2024-12-02 06:22:10,599 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-12-02 06:22:10,600 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.8) internal successors, (18), 8 states have internal predecessors, (18), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 39 [2024-12-02 06:22:10,600 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:10,601 INFO L225 Difference]: With dead ends: 48 [2024-12-02 06:22:10,601 INFO L226 Difference]: Without dead ends: 40 [2024-12-02 06:22:10,601 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=251, Unknown=0, NotChecked=0, Total=306 [2024-12-02 06:22:10,602 INFO L435 NwaCegarLoop]: 28 mSDtfsCounter, 24 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 155 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 178 SdHoareTripleChecker+Invalid, 178 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 155 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:10,602 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 178 Invalid, 178 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:10,603 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2024-12-02 06:22:10,613 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2024-12-02 06:22:10,613 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 16 states have call successors, (16), 3 states have call predecessors, (16), 3 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-12-02 06:22:10,614 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 54 transitions. [2024-12-02 06:22:10,614 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 54 transitions. Word has length 39 [2024-12-02 06:22:10,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:10,615 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 54 transitions. [2024-12-02 06:22:10,615 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.8) internal successors, (18), 8 states have internal predecessors, (18), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-12-02 06:22:10,615 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 54 transitions. [2024-12-02 06:22:10,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-12-02 06:22:10,616 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:10,616 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:10,624 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-12-02 06:22:10,816 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:10,816 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:10,817 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:10,817 INFO L85 PathProgramCache]: Analyzing trace with hash -977418419, now seen corresponding path program 1 times [2024-12-02 06:22:10,817 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:10,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [371118667] [2024-12-02 06:22:10,817 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:10,817 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:10,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:22:10,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2095900653] [2024-12-02 06:22:10,842 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:10,842 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:10,842 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:10,844 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:10,845 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-12-02 06:22:10,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:10,911 INFO L256 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-12-02 06:22:10,913 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:10,944 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-12-02 06:22:10,944 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-12-02 06:22:10,944 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:10,944 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [371118667] [2024-12-02 06:22:10,945 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:10,945 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2095900653] [2024-12-02 06:22:10,945 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2095900653] provided 1 perfect and 0 imperfect interpolant sequences [2024-12-02 06:22:10,945 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-12-02 06:22:10,945 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-12-02 06:22:10,945 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1140310692] [2024-12-02 06:22:10,946 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-12-02 06:22:10,946 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-12-02 06:22:10,946 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:10,946 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-12-02 06:22:10,946 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-12-02 06:22:10,947 INFO L87 Difference]: Start difference. First operand 39 states and 54 transitions. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-12-02 06:22:10,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:10,999 INFO L93 Difference]: Finished difference Result 56 states and 80 transitions. [2024-12-02 06:22:11,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-12-02 06:22:11,000 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 39 [2024-12-02 06:22:11,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:11,001 INFO L225 Difference]: With dead ends: 56 [2024-12-02 06:22:11,001 INFO L226 Difference]: Without dead ends: 54 [2024-12-02 06:22:11,002 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-12-02 06:22:11,002 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 4 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:11,003 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 128 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-12-02 06:22:11,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-12-02 06:22:11,013 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 45. [2024-12-02 06:22:11,013 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 25 states have internal predecessors, (26), 18 states have call successors, (18), 4 states have call predecessors, (18), 4 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-12-02 06:22:11,014 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 61 transitions. [2024-12-02 06:22:11,014 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 61 transitions. Word has length 39 [2024-12-02 06:22:11,014 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:11,015 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 61 transitions. [2024-12-02 06:22:11,015 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-12-02 06:22:11,015 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 61 transitions. [2024-12-02 06:22:11,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-12-02 06:22:11,016 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:11,016 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:11,024 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-12-02 06:22:11,216 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:11,216 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:11,217 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:11,217 INFO L85 PathProgramCache]: Analyzing trace with hash 1981253298, now seen corresponding path program 1 times [2024-12-02 06:22:11,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:11,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [855530988] [2024-12-02 06:22:11,217 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:11,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:11,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:22:11,239 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1689139675] [2024-12-02 06:22:11,239 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:11,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:11,239 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:11,241 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:11,242 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-12-02 06:22:11,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:11,290 INFO L256 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-12-02 06:22:11,292 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:11,360 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-12-02 06:22:11,360 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-12-02 06:22:11,360 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:11,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [855530988] [2024-12-02 06:22:11,360 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:11,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1689139675] [2024-12-02 06:22:11,360 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1689139675] provided 1 perfect and 0 imperfect interpolant sequences [2024-12-02 06:22:11,360 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-12-02 06:22:11,360 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-12-02 06:22:11,360 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [507248643] [2024-12-02 06:22:11,360 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-12-02 06:22:11,361 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-12-02 06:22:11,361 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:11,361 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-12-02 06:22:11,361 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-12-02 06:22:11,362 INFO L87 Difference]: Start difference. First operand 45 states and 61 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-12-02 06:22:11,417 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:11,417 INFO L93 Difference]: Finished difference Result 52 states and 67 transitions. [2024-12-02 06:22:11,418 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-12-02 06:22:11,418 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2024-12-02 06:22:11,418 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:11,420 INFO L225 Difference]: With dead ends: 52 [2024-12-02 06:22:11,420 INFO L226 Difference]: Without dead ends: 50 [2024-12-02 06:22:11,420 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-12-02 06:22:11,421 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:11,421 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 138 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-12-02 06:22:11,422 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-12-02 06:22:11,431 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 49. [2024-12-02 06:22:11,431 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 25 states have (on average 1.16) internal successors, (29), 28 states have internal predecessors, (29), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-12-02 06:22:11,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 64 transitions. [2024-12-02 06:22:11,433 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 64 transitions. Word has length 44 [2024-12-02 06:22:11,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:11,433 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 64 transitions. [2024-12-02 06:22:11,433 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-12-02 06:22:11,433 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 64 transitions. [2024-12-02 06:22:11,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-12-02 06:22:11,434 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:11,434 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:11,440 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-12-02 06:22:11,635 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:11,635 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:11,635 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:11,635 INFO L85 PathProgramCache]: Analyzing trace with hash -178384046, now seen corresponding path program 1 times [2024-12-02 06:22:11,635 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:11,635 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [455989591] [2024-12-02 06:22:11,635 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:11,636 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:11,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:22:11,660 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1826628984] [2024-12-02 06:22:11,660 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:11,660 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:11,660 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:11,662 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:11,665 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-12-02 06:22:11,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:11,720 INFO L256 TraceCheckSpWp]: Trace formula consists of 140 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-12-02 06:22:11,723 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:11,848 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-12-02 06:22:11,848 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-12-02 06:22:11,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:11,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [455989591] [2024-12-02 06:22:11,849 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:11,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1826628984] [2024-12-02 06:22:11,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1826628984] provided 1 perfect and 0 imperfect interpolant sequences [2024-12-02 06:22:11,849 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-12-02 06:22:11,849 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-12-02 06:22:11,849 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [619500512] [2024-12-02 06:22:11,849 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-12-02 06:22:11,850 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-12-02 06:22:11,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:11,850 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-12-02 06:22:11,850 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-12-02 06:22:11,851 INFO L87 Difference]: Start difference. First operand 49 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-12-02 06:22:11,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:11,928 INFO L93 Difference]: Finished difference Result 56 states and 70 transitions. [2024-12-02 06:22:11,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-12-02 06:22:11,929 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 54 [2024-12-02 06:22:11,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:11,930 INFO L225 Difference]: With dead ends: 56 [2024-12-02 06:22:11,930 INFO L226 Difference]: Without dead ends: 54 [2024-12-02 06:22:11,930 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-12-02 06:22:11,931 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 5 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:11,931 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 125 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:11,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-12-02 06:22:11,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2024-12-02 06:22:11,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 31 states have internal predecessors, (32), 18 states have call successors, (18), 6 states have call predecessors, (18), 6 states have return successors, (17), 15 states have call predecessors, (17), 17 states have call successors, (17) [2024-12-02 06:22:11,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 67 transitions. [2024-12-02 06:22:11,943 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 67 transitions. Word has length 54 [2024-12-02 06:22:11,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:11,944 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 67 transitions. [2024-12-02 06:22:11,944 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2024-12-02 06:22:11,944 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 67 transitions. [2024-12-02 06:22:11,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-12-02 06:22:11,944 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:11,945 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:11,953 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-12-02 06:22:12,145 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:12,145 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:12,146 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:12,146 INFO L85 PathProgramCache]: Analyzing trace with hash -1371475927, now seen corresponding path program 1 times [2024-12-02 06:22:12,146 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:12,146 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [439169851] [2024-12-02 06:22:12,146 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:12,146 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:12,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:22:12,167 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [354747091] [2024-12-02 06:22:12,167 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:12,167 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:12,167 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:12,169 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:12,170 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-12-02 06:22:12,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:12,224 INFO L256 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-12-02 06:22:12,225 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:12,296 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-12-02 06:22:12,296 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:12,406 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 8 proven. 1 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-12-02 06:22:12,406 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:12,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [439169851] [2024-12-02 06:22:12,406 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:12,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [354747091] [2024-12-02 06:22:12,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [354747091] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:22:12,406 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-12-02 06:22:12,406 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2024-12-02 06:22:12,406 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1795724853] [2024-12-02 06:22:12,406 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:12,407 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-12-02 06:22:12,407 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:12,407 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-12-02 06:22:12,407 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-12-02 06:22:12,408 INFO L87 Difference]: Start difference. First operand 53 states and 67 transitions. Second operand has 7 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-12-02 06:22:12,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:12,519 INFO L93 Difference]: Finished difference Result 79 states and 110 transitions. [2024-12-02 06:22:12,519 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-12-02 06:22:12,519 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 60 [2024-12-02 06:22:12,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:12,521 INFO L225 Difference]: With dead ends: 79 [2024-12-02 06:22:12,521 INFO L226 Difference]: Without dead ends: 77 [2024-12-02 06:22:12,521 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 110 SyntacticMatches, 3 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-12-02 06:22:12,522 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:12,522 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 144 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:12,523 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2024-12-02 06:22:12,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 51. [2024-12-02 06:22:12,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 29 states have internal predecessors, (32), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-12-02 06:22:12,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 63 transitions. [2024-12-02 06:22:12,542 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 63 transitions. Word has length 60 [2024-12-02 06:22:12,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:12,542 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 63 transitions. [2024-12-02 06:22:12,542 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 5 states have (on average 3.2) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-12-02 06:22:12,542 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 63 transitions. [2024-12-02 06:22:12,543 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-12-02 06:22:12,544 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:12,544 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:12,552 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-12-02 06:22:12,744 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:12,744 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:12,745 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:12,745 INFO L85 PathProgramCache]: Analyzing trace with hash 1875725832, now seen corresponding path program 1 times [2024-12-02 06:22:12,745 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:12,745 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1630756393] [2024-12-02 06:22:12,745 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:12,745 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:12,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:12,959 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-12-02 06:22:12,959 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:12,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1630756393] [2024-12-02 06:22:12,959 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1630756393] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:12,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [276962619] [2024-12-02 06:22:12,959 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:12,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:12,960 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:12,961 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:12,963 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-12-02 06:22:13,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:13,016 INFO L256 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-12-02 06:22:13,019 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:13,076 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-12-02 06:22:13,076 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:13,171 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 14 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-12-02 06:22:13,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [276962619] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:22:13,171 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-12-02 06:22:13,171 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 12 [2024-12-02 06:22:13,171 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [529203139] [2024-12-02 06:22:13,171 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:13,172 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-12-02 06:22:13,172 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:13,172 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-12-02 06:22:13,172 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2024-12-02 06:22:13,173 INFO L87 Difference]: Start difference. First operand 51 states and 63 transitions. Second operand has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-12-02 06:22:13,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:13,357 INFO L93 Difference]: Finished difference Result 91 states and 131 transitions. [2024-12-02 06:22:13,357 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-12-02 06:22:13,358 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 62 [2024-12-02 06:22:13,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:13,359 INFO L225 Difference]: With dead ends: 91 [2024-12-02 06:22:13,359 INFO L226 Difference]: Without dead ends: 83 [2024-12-02 06:22:13,359 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 116 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=54, Invalid=156, Unknown=0, NotChecked=0, Total=210 [2024-12-02 06:22:13,360 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 20 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 138 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 298 SdHoareTripleChecker+Invalid, 162 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 138 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:13,360 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 298 Invalid, 162 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 138 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:13,361 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2024-12-02 06:22:13,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 75. [2024-12-02 06:22:13,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 36 states have (on average 1.25) internal successors, (45), 37 states have internal predecessors, (45), 32 states have call successors, (32), 6 states have call predecessors, (32), 6 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2024-12-02 06:22:13,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 108 transitions. [2024-12-02 06:22:13,384 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 108 transitions. Word has length 62 [2024-12-02 06:22:13,384 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:13,384 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 108 transitions. [2024-12-02 06:22:13,384 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.25) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-12-02 06:22:13,384 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 108 transitions. [2024-12-02 06:22:13,385 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-12-02 06:22:13,385 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:13,385 INFO L218 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:13,394 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-12-02 06:22:13,586 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-12-02 06:22:13,586 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:13,586 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:13,586 INFO L85 PathProgramCache]: Analyzing trace with hash -329947379, now seen corresponding path program 1 times [2024-12-02 06:22:13,586 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:13,587 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [689343748] [2024-12-02 06:22:13,587 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:13,587 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:13,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:22:13,606 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1015635252] [2024-12-02 06:22:13,606 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:13,606 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:13,606 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:13,608 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:13,609 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-12-02 06:22:13,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:13,665 INFO L256 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-12-02 06:22:13,667 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:13,771 INFO L134 CoverageAnalysis]: Checked inductivity of 113 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 100 trivial. 0 not checked. [2024-12-02 06:22:13,771 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:13,807 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:13,807 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [689343748] [2024-12-02 06:22:13,807 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:13,807 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1015635252] [2024-12-02 06:22:13,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1015635252] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:13,807 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:22:13,808 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2024-12-02 06:22:13,808 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [366194792] [2024-12-02 06:22:13,808 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:13,808 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-12-02 06:22:13,808 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:13,809 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-12-02 06:22:13,809 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2024-12-02 06:22:13,809 INFO L87 Difference]: Start difference. First operand 75 states and 108 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-12-02 06:22:13,919 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:13,919 INFO L93 Difference]: Finished difference Result 105 states and 154 transitions. [2024-12-02 06:22:13,919 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-12-02 06:22:13,920 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 67 [2024-12-02 06:22:13,920 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:13,921 INFO L225 Difference]: With dead ends: 105 [2024-12-02 06:22:13,921 INFO L226 Difference]: Without dead ends: 102 [2024-12-02 06:22:13,921 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 64 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-12-02 06:22:13,922 INFO L435 NwaCegarLoop]: 45 mSDtfsCounter, 7 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 69 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 182 SdHoareTripleChecker+Invalid, 71 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 69 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:13,922 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 182 Invalid, 71 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 69 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:13,923 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-12-02 06:22:13,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 99. [2024-12-02 06:22:13,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 46 states have (on average 1.2826086956521738) internal successors, (59), 48 states have internal predecessors, (59), 45 states have call successors, (45), 7 states have call predecessors, (45), 7 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-12-02 06:22:13,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 147 transitions. [2024-12-02 06:22:13,950 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 147 transitions. Word has length 67 [2024-12-02 06:22:13,950 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:13,951 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 147 transitions. [2024-12-02 06:22:13,951 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-12-02 06:22:13,951 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 147 transitions. [2024-12-02 06:22:13,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-12-02 06:22:13,952 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:13,952 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:13,960 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-12-02 06:22:14,152 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2024-12-02 06:22:14,153 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:14,153 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:14,153 INFO L85 PathProgramCache]: Analyzing trace with hash 1881855666, now seen corresponding path program 2 times [2024-12-02 06:22:14,153 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:14,153 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1605158531] [2024-12-02 06:22:14,153 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-12-02 06:22:14,153 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:14,171 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-12-02 06:22:14,171 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:22:14,172 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [770101093] [2024-12-02 06:22:14,172 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-12-02 06:22:14,172 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:14,172 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:14,174 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:14,175 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-12-02 06:22:14,233 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-12-02 06:22:14,233 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:22:14,234 INFO L256 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-12-02 06:22:14,237 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:14,393 INFO L134 CoverageAnalysis]: Checked inductivity of 136 backedges. 12 proven. 4 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-12-02 06:22:14,393 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:14,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:14,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1605158531] [2024-12-02 06:22:14,433 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:14,433 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [770101093] [2024-12-02 06:22:14,433 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [770101093] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:14,433 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:22:14,433 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2024-12-02 06:22:14,433 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1111609376] [2024-12-02 06:22:14,433 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:14,433 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-12-02 06:22:14,434 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:14,434 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-12-02 06:22:14,434 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-12-02 06:22:14,434 INFO L87 Difference]: Start difference. First operand 99 states and 147 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-12-02 06:22:14,578 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:14,579 INFO L93 Difference]: Finished difference Result 111 states and 157 transitions. [2024-12-02 06:22:14,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-12-02 06:22:14,579 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 72 [2024-12-02 06:22:14,579 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:14,580 INFO L225 Difference]: With dead ends: 111 [2024-12-02 06:22:14,580 INFO L226 Difference]: Without dead ends: 109 [2024-12-02 06:22:14,581 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 68 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-12-02 06:22:14,581 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 10 mSDsluCounter, 157 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:14,581 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 196 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:14,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2024-12-02 06:22:14,604 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 107. [2024-12-02 06:22:14,605 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 52 states have (on average 1.25) internal successors, (65), 54 states have internal predecessors, (65), 45 states have call successors, (45), 9 states have call predecessors, (45), 9 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-12-02 06:22:14,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 153 transitions. [2024-12-02 06:22:14,606 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 153 transitions. Word has length 72 [2024-12-02 06:22:14,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:14,607 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 153 transitions. [2024-12-02 06:22:14,607 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 4 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-12-02 06:22:14,607 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 153 transitions. [2024-12-02 06:22:14,608 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-12-02 06:22:14,608 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:14,608 INFO L218 NwaCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:14,615 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-12-02 06:22:14,808 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-12-02 06:22:14,809 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:14,809 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:14,809 INFO L85 PathProgramCache]: Analyzing trace with hash -1928364563, now seen corresponding path program 3 times [2024-12-02 06:22:14,809 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:14,809 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [814254461] [2024-12-02 06:22:14,809 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-12-02 06:22:14,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:14,844 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-12-02 06:22:14,844 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:22:14,845 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [955598538] [2024-12-02 06:22:14,845 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-12-02 06:22:14,845 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:14,845 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:14,847 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:14,848 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-12-02 06:22:14,904 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-12-02 06:22:14,904 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:22:14,906 INFO L256 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-12-02 06:22:14,909 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:15,474 INFO L134 CoverageAnalysis]: Checked inductivity of 163 backedges. 43 proven. 18 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2024-12-02 06:22:15,475 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:16,156 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:16,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [814254461] [2024-12-02 06:22:16,156 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:16,156 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [955598538] [2024-12-02 06:22:16,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [955598538] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:16,156 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:22:16,157 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-12-02 06:22:16,157 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1113501085] [2024-12-02 06:22:16,157 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:16,157 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-12-02 06:22:16,157 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:16,158 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-12-02 06:22:16,158 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=394, Unknown=0, NotChecked=0, Total=462 [2024-12-02 06:22:16,158 INFO L87 Difference]: Start difference. First operand 107 states and 153 transitions. Second operand has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-12-02 06:22:16,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:16,556 INFO L93 Difference]: Finished difference Result 115 states and 160 transitions. [2024-12-02 06:22:16,556 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-12-02 06:22:16,556 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 77 [2024-12-02 06:22:16,557 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:16,558 INFO L225 Difference]: With dead ends: 115 [2024-12-02 06:22:16,558 INFO L226 Difference]: Without dead ends: 113 [2024-12-02 06:22:16,558 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=94, Invalid=506, Unknown=0, NotChecked=0, Total=600 [2024-12-02 06:22:16,559 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 25 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 346 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 363 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 346 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:16,559 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 165 Invalid, 363 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 346 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-12-02 06:22:16,560 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2024-12-02 06:22:16,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 111. [2024-12-02 06:22:16,583 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 55 states have (on average 1.2363636363636363) internal successors, (68), 57 states have internal predecessors, (68), 45 states have call successors, (45), 10 states have call predecessors, (45), 10 states have return successors, (43), 43 states have call predecessors, (43), 43 states have call successors, (43) [2024-12-02 06:22:16,584 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 156 transitions. [2024-12-02 06:22:16,584 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 156 transitions. Word has length 77 [2024-12-02 06:22:16,585 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:16,585 INFO L471 AbstractCegarLoop]: Abstraction has 111 states and 156 transitions. [2024-12-02 06:22:16,585 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.7692307692307692) internal successors, (23), 13 states have internal predecessors, (23), 5 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-12-02 06:22:16,585 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 156 transitions. [2024-12-02 06:22:16,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-12-02 06:22:16,586 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:16,586 INFO L218 NwaCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:16,594 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-12-02 06:22:16,786 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,11 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:16,787 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:16,787 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:16,787 INFO L85 PathProgramCache]: Analyzing trace with hash 1939074476, now seen corresponding path program 1 times [2024-12-02 06:22:16,787 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:16,787 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1722446297] [2024-12-02 06:22:16,787 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:16,787 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:16,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:22:16,806 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [474796732] [2024-12-02 06:22:16,806 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:16,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:16,806 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:16,808 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:16,809 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-12-02 06:22:16,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:16,865 INFO L256 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-12-02 06:22:16,867 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:17,288 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 22 proven. 15 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2024-12-02 06:22:17,288 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:17,623 INFO L134 CoverageAnalysis]: Checked inductivity of 194 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-12-02 06:22:17,623 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:17,623 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1722446297] [2024-12-02 06:22:17,623 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:17,623 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [474796732] [2024-12-02 06:22:17,624 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [474796732] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:22:17,624 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-12-02 06:22:17,624 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-12-02 06:22:17,624 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [793925547] [2024-12-02 06:22:17,624 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:17,624 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-12-02 06:22:17,624 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:17,625 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-12-02 06:22:17,625 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-12-02 06:22:17,625 INFO L87 Difference]: Start difference. First operand 111 states and 156 transitions. Second operand has 21 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-12-02 06:22:20,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:20,224 INFO L93 Difference]: Finished difference Result 195 states and 303 transitions. [2024-12-02 06:22:20,224 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-12-02 06:22:20,224 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) Word has length 83 [2024-12-02 06:22:20,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:20,226 INFO L225 Difference]: With dead ends: 195 [2024-12-02 06:22:20,226 INFO L226 Difference]: Without dead ends: 191 [2024-12-02 06:22:20,227 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 181 GetRequests, 145 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2024-12-02 06:22:20,227 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 55 mSDsluCounter, 437 mSDsCounter, 0 mSdLazyCounter, 581 mSolverCounterSat, 108 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 477 SdHoareTripleChecker+Invalid, 689 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 108 IncrementalHoareTripleChecker+Valid, 581 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:20,227 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 477 Invalid, 689 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [108 Valid, 581 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2024-12-02 06:22:20,228 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2024-12-02 06:22:20,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 188. [2024-12-02 06:22:20,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 81 states have (on average 1.3333333333333333) internal successors, (108), 84 states have internal predecessors, (108), 94 states have call successors, (94), 12 states have call predecessors, (94), 12 states have return successors, (92), 91 states have call predecessors, (92), 92 states have call successors, (92) [2024-12-02 06:22:20,321 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 294 transitions. [2024-12-02 06:22:20,321 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 294 transitions. Word has length 83 [2024-12-02 06:22:20,321 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:20,322 INFO L471 AbstractCegarLoop]: Abstraction has 188 states and 294 transitions. [2024-12-02 06:22:20,322 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 18 states have internal predecessors, (29), 10 states have call successors, (27), 3 states have call predecessors, (27), 2 states have return successors, (26), 8 states have call predecessors, (26), 8 states have call successors, (26) [2024-12-02 06:22:20,322 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 294 transitions. [2024-12-02 06:22:20,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 91 [2024-12-02 06:22:20,323 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:20,323 INFO L218 NwaCegarLoop]: trace histogram [10, 9, 9, 6, 6, 6, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:20,332 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-12-02 06:22:20,523 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,12 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:20,524 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:20,524 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:20,524 INFO L85 PathProgramCache]: Analyzing trace with hash -1291235246, now seen corresponding path program 4 times [2024-12-02 06:22:20,524 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:20,524 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1269168901] [2024-12-02 06:22:20,524 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-12-02 06:22:20,524 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:20,546 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-12-02 06:22:20,546 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:22:20,641 INFO L134 CoverageAnalysis]: Checked inductivity of 235 backedges. 31 proven. 0 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2024-12-02 06:22:20,642 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:20,642 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1269168901] [2024-12-02 06:22:20,642 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1269168901] provided 1 perfect and 0 imperfect interpolant sequences [2024-12-02 06:22:20,642 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-12-02 06:22:20,642 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-12-02 06:22:20,642 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1460094087] [2024-12-02 06:22:20,642 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-12-02 06:22:20,642 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-12-02 06:22:20,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:20,643 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-12-02 06:22:20,643 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-12-02 06:22:20,643 INFO L87 Difference]: Start difference. First operand 188 states and 294 transitions. Second operand has 5 states, 5 states have (on average 4.0) internal successors, (20), 5 states have internal predecessors, (20), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-12-02 06:22:20,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:20,790 INFO L93 Difference]: Finished difference Result 233 states and 362 transitions. [2024-12-02 06:22:20,791 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-12-02 06:22:20,791 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 5 states have internal predecessors, (20), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 90 [2024-12-02 06:22:20,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:20,794 INFO L225 Difference]: With dead ends: 233 [2024-12-02 06:22:20,794 INFO L226 Difference]: Without dead ends: 171 [2024-12-02 06:22:20,795 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2024-12-02 06:22:20,795 INFO L435 NwaCegarLoop]: 46 mSDtfsCounter, 4 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:20,796 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 157 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:20,796 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2024-12-02 06:22:20,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 162. [2024-12-02 06:22:20,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 162 states, 71 states have (on average 1.2394366197183098) internal successors, (88), 74 states have internal predecessors, (88), 78 states have call successors, (78), 12 states have call predecessors, (78), 12 states have return successors, (76), 75 states have call predecessors, (76), 76 states have call successors, (76) [2024-12-02 06:22:20,880 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 242 transitions. [2024-12-02 06:22:20,881 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 242 transitions. Word has length 90 [2024-12-02 06:22:20,881 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:20,881 INFO L471 AbstractCegarLoop]: Abstraction has 162 states and 242 transitions. [2024-12-02 06:22:20,882 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 5 states have internal predecessors, (20), 3 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-12-02 06:22:20,882 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 242 transitions. [2024-12-02 06:22:20,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-12-02 06:22:20,883 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:20,883 INFO L218 NwaCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:20,883 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11 [2024-12-02 06:22:20,883 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:20,884 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:20,884 INFO L85 PathProgramCache]: Analyzing trace with hash -557243959, now seen corresponding path program 1 times [2024-12-02 06:22:20,884 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:20,884 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [737406034] [2024-12-02 06:22:20,884 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:20,884 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:20,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:22:20,916 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1453382793] [2024-12-02 06:22:20,917 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:20,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:20,917 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:20,919 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:20,921 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-12-02 06:22:21,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:21,006 INFO L256 TraceCheckSpWp]: Trace formula consists of 235 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-12-02 06:22:21,008 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:21,795 INFO L134 CoverageAnalysis]: Checked inductivity of 316 backedges. 57 proven. 24 refuted. 0 times theorem prover too weak. 235 trivial. 0 not checked. [2024-12-02 06:22:21,795 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:23,039 INFO L134 CoverageAnalysis]: Checked inductivity of 316 backedges. 51 proven. 15 refuted. 0 times theorem prover too weak. 250 trivial. 0 not checked. [2024-12-02 06:22:23,039 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:23,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [737406034] [2024-12-02 06:22:23,039 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:23,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1453382793] [2024-12-02 06:22:23,040 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1453382793] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:22:23,040 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-12-02 06:22:23,040 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12] total 24 [2024-12-02 06:22:23,040 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [123451536] [2024-12-02 06:22:23,040 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:23,040 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-12-02 06:22:23,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:23,041 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-12-02 06:22:23,041 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=450, Unknown=0, NotChecked=0, Total=552 [2024-12-02 06:22:23,041 INFO L87 Difference]: Start difference. First operand 162 states and 242 transitions. Second operand has 24 states, 21 states have (on average 1.619047619047619) internal successors, (34), 21 states have internal predecessors, (34), 11 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) [2024-12-02 06:22:32,575 WARN L286 SmtUtils]: Spent 8.72s on a formula simplification that was a NOOP. DAG size: 73 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-12-02 06:22:41,089 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.42s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-12-02 06:22:42,878 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.23s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-12-02 06:22:47,464 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-12-02 06:22:51,442 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.47s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-12-02 06:22:53,319 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:53,319 INFO L93 Difference]: Finished difference Result 201 states and 302 transitions. [2024-12-02 06:22:53,320 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-12-02 06:22:53,320 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 21 states have (on average 1.619047619047619) internal successors, (34), 21 states have internal predecessors, (34), 11 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) Word has length 98 [2024-12-02 06:22:53,320 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:53,322 INFO L225 Difference]: With dead ends: 201 [2024-12-02 06:22:53,322 INFO L226 Difference]: Without dead ends: 199 [2024-12-02 06:22:53,323 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 172 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 326 ImplicationChecksByTransitivity, 20.2s TimeCoverageRelationStatistics Valid=394, Invalid=1246, Unknown=0, NotChecked=0, Total=1640 [2024-12-02 06:22:53,323 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 52 mSDsluCounter, 341 mSDsCounter, 0 mSdLazyCounter, 674 mSolverCounterSat, 89 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 370 SdHoareTripleChecker+Invalid, 764 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 89 IncrementalHoareTripleChecker+Valid, 674 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.6s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:53,323 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 370 Invalid, 764 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [89 Valid, 674 Invalid, 1 Unknown, 0 Unchecked, 10.6s Time] [2024-12-02 06:22:53,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 199 states. [2024-12-02 06:22:53,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 199 to 190. [2024-12-02 06:22:53,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 85 states have (on average 1.2470588235294118) internal successors, (106), 89 states have internal predecessors, (106), 90 states have call successors, (90), 14 states have call predecessors, (90), 14 states have return successors, (88), 86 states have call predecessors, (88), 88 states have call successors, (88) [2024-12-02 06:22:53,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 284 transitions. [2024-12-02 06:22:53,410 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 284 transitions. Word has length 98 [2024-12-02 06:22:53,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:53,410 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 284 transitions. [2024-12-02 06:22:53,410 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 21 states have (on average 1.619047619047619) internal successors, (34), 21 states have internal predecessors, (34), 11 states have call successors, (33), 3 states have call predecessors, (33), 3 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) [2024-12-02 06:22:53,410 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 284 transitions. [2024-12-02 06:22:53,412 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2024-12-02 06:22:53,412 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:53,412 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:53,421 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-12-02 06:22:53,612 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,13 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:53,612 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:53,613 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:53,613 INFO L85 PathProgramCache]: Analyzing trace with hash -389224818, now seen corresponding path program 1 times [2024-12-02 06:22:53,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:53,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [288427716] [2024-12-02 06:22:53,613 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:53,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:53,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:53,788 INFO L134 CoverageAnalysis]: Checked inductivity of 417 backedges. 38 proven. 7 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-12-02 06:22:53,788 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:53,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [288427716] [2024-12-02 06:22:53,788 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [288427716] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:53,788 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1141775369] [2024-12-02 06:22:53,788 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-12-02 06:22:53,788 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:53,788 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:53,790 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:53,792 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-12-02 06:22:53,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:22:53,860 INFO L256 TraceCheckSpWp]: Trace formula consists of 268 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-12-02 06:22:53,861 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:53,888 INFO L134 CoverageAnalysis]: Checked inductivity of 417 backedges. 84 proven. 7 refuted. 0 times theorem prover too weak. 326 trivial. 0 not checked. [2024-12-02 06:22:53,888 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:53,984 INFO L134 CoverageAnalysis]: Checked inductivity of 417 backedges. 38 proven. 7 refuted. 0 times theorem prover too weak. 372 trivial. 0 not checked. [2024-12-02 06:22:53,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1141775369] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:22:53,984 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-12-02 06:22:53,984 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 7 [2024-12-02 06:22:53,985 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [184267228] [2024-12-02 06:22:53,985 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:53,985 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-12-02 06:22:53,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:53,986 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-12-02 06:22:53,986 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-12-02 06:22:53,986 INFO L87 Difference]: Start difference. First operand 190 states and 284 transitions. Second operand has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-12-02 06:22:54,281 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:54,282 INFO L93 Difference]: Finished difference Result 223 states and 339 transitions. [2024-12-02 06:22:54,282 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-12-02 06:22:54,282 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) Word has length 111 [2024-12-02 06:22:54,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:54,284 INFO L225 Difference]: With dead ends: 223 [2024-12-02 06:22:54,284 INFO L226 Difference]: Without dead ends: 211 [2024-12-02 06:22:54,285 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 238 GetRequests, 219 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2024-12-02 06:22:54,285 INFO L435 NwaCegarLoop]: 62 mSDtfsCounter, 11 mSDsluCounter, 230 mSDsCounter, 0 mSdLazyCounter, 98 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 292 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 98 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:54,286 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 292 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 98 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:54,286 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2024-12-02 06:22:54,374 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 185. [2024-12-02 06:22:54,374 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 82 states have (on average 1.2195121951219512) internal successors, (100), 85 states have internal predecessors, (100), 89 states have call successors, (89), 13 states have call predecessors, (89), 13 states have return successors, (87), 86 states have call predecessors, (87), 87 states have call successors, (87) [2024-12-02 06:22:54,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 276 transitions. [2024-12-02 06:22:54,376 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 276 transitions. Word has length 111 [2024-12-02 06:22:54,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:54,376 INFO L471 AbstractCegarLoop]: Abstraction has 185 states and 276 transitions. [2024-12-02 06:22:54,376 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 3.2857142857142856) internal successors, (23), 7 states have internal predecessors, (23), 4 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 4 states have call predecessors, (20), 4 states have call successors, (20) [2024-12-02 06:22:54,376 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 276 transitions. [2024-12-02 06:22:54,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 112 [2024-12-02 06:22:54,377 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:54,378 INFO L218 NwaCegarLoop]: trace histogram [14, 13, 13, 6, 6, 6, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:54,387 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-12-02 06:22:54,578 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,14 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:54,578 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:54,578 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:54,579 INFO L85 PathProgramCache]: Analyzing trace with hash 784855492, now seen corresponding path program 2 times [2024-12-02 06:22:54,579 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:54,579 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [878092890] [2024-12-02 06:22:54,579 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-12-02 06:22:54,579 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:54,608 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-12-02 06:22:54,608 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:22:54,610 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [404728808] [2024-12-02 06:22:54,610 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-12-02 06:22:54,610 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:54,610 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:54,612 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:54,614 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-12-02 06:22:54,694 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-12-02 06:22:54,694 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:22:54,697 INFO L256 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-12-02 06:22:54,700 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:55,215 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 61 proven. 41 refuted. 0 times theorem prover too weak. 321 trivial. 0 not checked. [2024-12-02 06:22:55,215 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:55,380 INFO L134 CoverageAnalysis]: Checked inductivity of 423 backedges. 68 proven. 7 refuted. 0 times theorem prover too weak. 348 trivial. 0 not checked. [2024-12-02 06:22:55,380 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:55,380 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [878092890] [2024-12-02 06:22:55,381 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:55,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [404728808] [2024-12-02 06:22:55,381 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [404728808] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:22:55,381 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-12-02 06:22:55,381 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2024-12-02 06:22:55,381 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [149266141] [2024-12-02 06:22:55,381 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:55,381 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-12-02 06:22:55,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:55,382 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-12-02 06:22:55,382 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=396, Unknown=0, NotChecked=0, Total=462 [2024-12-02 06:22:55,382 INFO L87 Difference]: Start difference. First operand 185 states and 276 transitions. Second operand has 22 states, 22 states have (on average 1.7727272727272727) internal successors, (39), 19 states have internal predecessors, (39), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2024-12-02 06:22:56,655 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:56,655 INFO L93 Difference]: Finished difference Result 215 states and 318 transitions. [2024-12-02 06:22:56,656 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-12-02 06:22:56,656 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.7727272727272727) internal successors, (39), 19 states have internal predecessors, (39), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) Word has length 111 [2024-12-02 06:22:56,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:56,657 INFO L225 Difference]: With dead ends: 215 [2024-12-02 06:22:56,657 INFO L226 Difference]: Without dead ends: 212 [2024-12-02 06:22:56,658 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 201 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 170 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=173, Invalid=883, Unknown=0, NotChecked=0, Total=1056 [2024-12-02 06:22:56,658 INFO L435 NwaCegarLoop]: 35 mSDtfsCounter, 36 mSDsluCounter, 424 mSDsCounter, 0 mSdLazyCounter, 702 mSolverCounterSat, 77 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 459 SdHoareTripleChecker+Invalid, 779 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 77 IncrementalHoareTripleChecker+Valid, 702 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:56,658 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 459 Invalid, 779 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [77 Valid, 702 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-12-02 06:22:56,659 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 212 states. [2024-12-02 06:22:56,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 212 to 191. [2024-12-02 06:22:56,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 88 states have (on average 1.2045454545454546) internal successors, (106), 90 states have internal predecessors, (106), 87 states have call successors, (87), 15 states have call predecessors, (87), 15 states have return successors, (86), 85 states have call predecessors, (86), 86 states have call successors, (86) [2024-12-02 06:22:56,750 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 279 transitions. [2024-12-02 06:22:56,750 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 279 transitions. Word has length 111 [2024-12-02 06:22:56,751 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:56,751 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 279 transitions. [2024-12-02 06:22:56,751 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.7727272727272727) internal successors, (39), 19 states have internal predecessors, (39), 9 states have call successors, (30), 3 states have call predecessors, (30), 3 states have return successors, (30), 9 states have call predecessors, (30), 9 states have call successors, (30) [2024-12-02 06:22:56,751 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 279 transitions. [2024-12-02 06:22:56,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-12-02 06:22:56,752 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:56,752 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:56,758 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-12-02 06:22:56,952 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-12-02 06:22:56,953 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:56,953 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:56,953 INFO L85 PathProgramCache]: Analyzing trace with hash -1677220558, now seen corresponding path program 3 times [2024-12-02 06:22:56,953 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:56,953 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [186404454] [2024-12-02 06:22:56,953 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-12-02 06:22:56,953 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:56,992 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-12-02 06:22:56,993 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:22:56,994 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1467862146] [2024-12-02 06:22:56,994 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-12-02 06:22:56,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:56,994 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:56,996 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:56,997 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-12-02 06:22:57,066 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-12-02 06:22:57,066 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:22:57,068 INFO L256 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-12-02 06:22:57,071 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:57,388 INFO L134 CoverageAnalysis]: Checked inductivity of 477 backedges. 86 proven. 32 refuted. 0 times theorem prover too weak. 359 trivial. 0 not checked. [2024-12-02 06:22:57,388 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:57,459 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:57,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [186404454] [2024-12-02 06:22:57,459 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:57,459 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1467862146] [2024-12-02 06:22:57,459 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1467862146] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:57,460 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:22:57,460 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2024-12-02 06:22:57,460 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1956934021] [2024-12-02 06:22:57,460 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:57,460 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-12-02 06:22:57,460 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:57,461 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-12-02 06:22:57,461 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2024-12-02 06:22:57,461 INFO L87 Difference]: Start difference. First operand 191 states and 279 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-12-02 06:22:57,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:22:57,707 INFO L93 Difference]: Finished difference Result 207 states and 292 transitions. [2024-12-02 06:22:57,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-12-02 06:22:57,708 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 114 [2024-12-02 06:22:57,708 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:22:57,709 INFO L225 Difference]: With dead ends: 207 [2024-12-02 06:22:57,709 INFO L226 Difference]: Without dead ends: 205 [2024-12-02 06:22:57,710 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=141, Unknown=0, NotChecked=0, Total=182 [2024-12-02 06:22:57,710 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 6 mSDsluCounter, 172 mSDsCounter, 0 mSdLazyCounter, 171 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 203 SdHoareTripleChecker+Invalid, 176 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 171 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:22:57,710 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 203 Invalid, 176 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 171 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-12-02 06:22:57,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 205 states. [2024-12-02 06:22:57,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 205 to 203. [2024-12-02 06:22:57,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 97 states have (on average 1.1855670103092784) internal successors, (115), 99 states have internal predecessors, (115), 87 states have call successors, (87), 18 states have call predecessors, (87), 18 states have return successors, (86), 85 states have call predecessors, (86), 86 states have call successors, (86) [2024-12-02 06:22:57,803 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 288 transitions. [2024-12-02 06:22:57,803 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 288 transitions. Word has length 114 [2024-12-02 06:22:57,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:22:57,804 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 288 transitions. [2024-12-02 06:22:57,804 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-12-02 06:22:57,804 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 288 transitions. [2024-12-02 06:22:57,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-12-02 06:22:57,804 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:22:57,805 INFO L218 NwaCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:22:57,810 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-12-02 06:22:58,005 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-12-02 06:22:58,005 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:22:58,005 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:22:58,005 INFO L85 PathProgramCache]: Analyzing trace with hash -1710922149, now seen corresponding path program 4 times [2024-12-02 06:22:58,005 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:22:58,006 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1232120047] [2024-12-02 06:22:58,006 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-12-02 06:22:58,006 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:22:58,030 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-12-02 06:22:58,030 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:22:58,031 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1605788890] [2024-12-02 06:22:58,031 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-12-02 06:22:58,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:22:58,032 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:22:58,033 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:22:58,035 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-12-02 06:22:58,113 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-12-02 06:22:58,113 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:22:58,115 INFO L256 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-12-02 06:22:58,118 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:22:58,816 INFO L134 CoverageAnalysis]: Checked inductivity of 480 backedges. 57 proven. 38 refuted. 0 times theorem prover too weak. 385 trivial. 0 not checked. [2024-12-02 06:22:58,816 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:22:59,468 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:22:59,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1232120047] [2024-12-02 06:22:59,469 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:22:59,469 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1605788890] [2024-12-02 06:22:59,469 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1605788890] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:22:59,469 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:22:59,469 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-12-02 06:22:59,469 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [689619008] [2024-12-02 06:22:59,469 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:22:59,469 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-12-02 06:22:59,469 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:22:59,469 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-12-02 06:22:59,470 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=463, Unknown=0, NotChecked=0, Total=552 [2024-12-02 06:22:59,470 INFO L87 Difference]: Start difference. First operand 203 states and 288 transitions. Second operand has 15 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 13 states have internal predecessors, (24), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-12-02 06:23:00,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:23:00,195 INFO L93 Difference]: Finished difference Result 241 states and 336 transitions. [2024-12-02 06:23:00,196 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-12-02 06:23:00,196 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 13 states have internal predecessors, (24), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) Word has length 116 [2024-12-02 06:23:00,196 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:23:00,198 INFO L225 Difference]: With dead ends: 241 [2024-12-02 06:23:00,198 INFO L226 Difference]: Without dead ends: 239 [2024-12-02 06:23:00,198 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 153 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 113 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=159, Invalid=771, Unknown=0, NotChecked=0, Total=930 [2024-12-02 06:23:00,199 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 18 mSDsluCounter, 352 mSDsCounter, 0 mSdLazyCounter, 442 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 393 SdHoareTripleChecker+Invalid, 461 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 442 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-12-02 06:23:00,199 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 393 Invalid, 461 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 442 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-12-02 06:23:00,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2024-12-02 06:23:00,292 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 236. [2024-12-02 06:23:00,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 236 states, 114 states have (on average 1.1754385964912282) internal successors, (134), 116 states have internal predecessors, (134), 99 states have call successors, (99), 22 states have call predecessors, (99), 22 states have return successors, (98), 97 states have call predecessors, (98), 98 states have call successors, (98) [2024-12-02 06:23:00,294 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 236 states to 236 states and 331 transitions. [2024-12-02 06:23:00,294 INFO L78 Accepts]: Start accepts. Automaton has 236 states and 331 transitions. Word has length 116 [2024-12-02 06:23:00,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:23:00,294 INFO L471 AbstractCegarLoop]: Abstraction has 236 states and 331 transitions. [2024-12-02 06:23:00,294 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 13 states have internal predecessors, (24), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 7 states have call predecessors, (20), 7 states have call successors, (20) [2024-12-02 06:23:00,294 INFO L276 IsEmpty]: Start isEmpty. Operand 236 states and 331 transitions. [2024-12-02 06:23:00,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2024-12-02 06:23:00,295 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:23:00,295 INFO L218 NwaCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:23:00,303 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-12-02 06:23:00,496 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-12-02 06:23:00,496 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:23:00,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:23:00,496 INFO L85 PathProgramCache]: Analyzing trace with hash -853530013, now seen corresponding path program 2 times [2024-12-02 06:23:00,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:23:00,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1249384974] [2024-12-02 06:23:00,496 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-12-02 06:23:00,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:23:00,523 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-12-02 06:23:00,523 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:23:00,524 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1677123562] [2024-12-02 06:23:00,524 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-12-02 06:23:00,525 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:00,525 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:23:00,527 INFO L229 MonitoredProcess]: Starting monitored process 18 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:23:00,528 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-12-02 06:23:00,619 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-12-02 06:23:00,619 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:23:00,621 INFO L256 TraceCheckSpWp]: Trace formula consists of 300 conjuncts, 58 conjuncts are in the unsatisfiable core [2024-12-02 06:23:00,624 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:23:01,242 INFO L134 CoverageAnalysis]: Checked inductivity of 606 backedges. 73 proven. 38 refuted. 0 times theorem prover too weak. 495 trivial. 0 not checked. [2024-12-02 06:23:01,242 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:23:02,407 INFO L134 CoverageAnalysis]: Checked inductivity of 606 backedges. 73 proven. 38 refuted. 0 times theorem prover too weak. 495 trivial. 0 not checked. [2024-12-02 06:23:02,408 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:23:02,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1249384974] [2024-12-02 06:23:02,408 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:23:02,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1677123562] [2024-12-02 06:23:02,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1677123562] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:23:02,408 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-12-02 06:23:02,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 27 [2024-12-02 06:23:02,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [693386826] [2024-12-02 06:23:02,408 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-12-02 06:23:02,408 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-12-02 06:23:02,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:23:02,409 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-12-02 06:23:02,409 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=576, Unknown=0, NotChecked=0, Total=702 [2024-12-02 06:23:02,410 INFO L87 Difference]: Start difference. First operand 236 states and 331 transitions. Second operand has 27 states, 24 states have (on average 1.5416666666666667) internal successors, (37), 25 states have internal predecessors, (37), 14 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (40), 12 states have call predecessors, (40), 12 states have call successors, (40) [2024-12-02 06:23:05,824 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.29s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-12-02 06:23:09,067 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:23:09,067 INFO L93 Difference]: Finished difference Result 308 states and 448 transitions. [2024-12-02 06:23:09,067 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2024-12-02 06:23:09,068 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 24 states have (on average 1.5416666666666667) internal successors, (37), 25 states have internal predecessors, (37), 14 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (40), 12 states have call predecessors, (40), 12 states have call successors, (40) Word has length 127 [2024-12-02 06:23:09,068 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:23:09,069 INFO L225 Difference]: With dead ends: 308 [2024-12-02 06:23:09,069 INFO L226 Difference]: Without dead ends: 304 [2024-12-02 06:23:09,070 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 279 GetRequests, 225 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 448 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=572, Invalid=2290, Unknown=0, NotChecked=0, Total=2862 [2024-12-02 06:23:09,070 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 63 mSDsluCounter, 517 mSDsCounter, 0 mSdLazyCounter, 892 mSolverCounterSat, 172 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 63 SdHoareTripleChecker+Valid, 567 SdHoareTripleChecker+Invalid, 1064 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 172 IncrementalHoareTripleChecker+Valid, 892 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-12-02 06:23:09,071 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [63 Valid, 567 Invalid, 1064 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [172 Valid, 892 Invalid, 0 Unknown, 0 Unchecked, 4.1s Time] [2024-12-02 06:23:09,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 304 states. [2024-12-02 06:23:09,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 304 to 263. [2024-12-02 06:23:09,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 263 states, 123 states have (on average 1.1788617886178863) internal successors, (145), 126 states have internal predecessors, (145), 115 states have call successors, (115), 24 states have call predecessors, (115), 24 states have return successors, (114), 112 states have call predecessors, (114), 114 states have call successors, (114) [2024-12-02 06:23:09,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 263 states to 263 states and 374 transitions. [2024-12-02 06:23:09,231 INFO L78 Accepts]: Start accepts. Automaton has 263 states and 374 transitions. Word has length 127 [2024-12-02 06:23:09,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:23:09,231 INFO L471 AbstractCegarLoop]: Abstraction has 263 states and 374 transitions. [2024-12-02 06:23:09,232 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 24 states have (on average 1.5416666666666667) internal successors, (37), 25 states have internal predecessors, (37), 14 states have call successors, (42), 2 states have call predecessors, (42), 2 states have return successors, (40), 12 states have call predecessors, (40), 12 states have call successors, (40) [2024-12-02 06:23:09,232 INFO L276 IsEmpty]: Start isEmpty. Operand 263 states and 374 transitions. [2024-12-02 06:23:09,232 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 138 [2024-12-02 06:23:09,232 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:23:09,233 INFO L218 NwaCegarLoop]: trace histogram [19, 18, 18, 6, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:23:09,242 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-12-02 06:23:09,433 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-12-02 06:23:09,433 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:23:09,433 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:23:09,433 INFO L85 PathProgramCache]: Analyzing trace with hash 675635967, now seen corresponding path program 5 times [2024-12-02 06:23:09,434 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:23:09,434 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1963978939] [2024-12-02 06:23:09,434 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-12-02 06:23:09,434 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:23:09,482 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 11 check-sat command(s) [2024-12-02 06:23:09,482 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:23:09,483 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1475612466] [2024-12-02 06:23:09,484 INFO L95 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-12-02 06:23:09,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:09,484 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:23:09,486 INFO L229 MonitoredProcess]: Starting monitored process 19 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:23:09,488 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-12-02 06:23:09,627 INFO L229 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 11 check-sat command(s) [2024-12-02 06:23:09,627 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:23:09,629 INFO L256 TraceCheckSpWp]: Trace formula consists of 321 conjuncts, 64 conjuncts are in the unsatisfiable core [2024-12-02 06:23:09,632 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:23:10,438 INFO L134 CoverageAnalysis]: Checked inductivity of 754 backedges. 74 proven. 74 refuted. 0 times theorem prover too weak. 606 trivial. 0 not checked. [2024-12-02 06:23:10,438 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:23:11,437 INFO L134 CoverageAnalysis]: Checked inductivity of 754 backedges. 74 proven. 59 refuted. 0 times theorem prover too weak. 621 trivial. 0 not checked. [2024-12-02 06:23:11,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:23:11,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1963978939] [2024-12-02 06:23:11,437 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:23:11,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1475612466] [2024-12-02 06:23:11,437 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1475612466] provided 0 perfect and 2 imperfect interpolant sequences [2024-12-02 06:23:11,438 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-12-02 06:23:11,438 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 30 [2024-12-02 06:23:11,438 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1866866110] [2024-12-02 06:23:11,438 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-12-02 06:23:11,438 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-12-02 06:23:11,438 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:23:11,439 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-12-02 06:23:11,439 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=722, Unknown=0, NotChecked=0, Total=870 [2024-12-02 06:23:11,439 INFO L87 Difference]: Start difference. First operand 263 states and 374 transitions. Second operand has 30 states, 29 states have (on average 1.4482758620689655) internal successors, (42), 27 states have internal predecessors, (42), 14 states have call successors, (46), 3 states have call predecessors, (46), 3 states have return successors, (45), 15 states have call predecessors, (45), 14 states have call successors, (45) [2024-12-02 06:23:14,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:23:14,327 INFO L93 Difference]: Finished difference Result 312 states and 441 transitions. [2024-12-02 06:23:14,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-12-02 06:23:14,328 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 29 states have (on average 1.4482758620689655) internal successors, (42), 27 states have internal predecessors, (42), 14 states have call successors, (46), 3 states have call predecessors, (46), 3 states have return successors, (45), 15 states have call predecessors, (45), 14 states have call successors, (45) Word has length 137 [2024-12-02 06:23:14,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:23:14,330 INFO L225 Difference]: With dead ends: 312 [2024-12-02 06:23:14,330 INFO L226 Difference]: Without dead ends: 310 [2024-12-02 06:23:14,331 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 292 GetRequests, 244 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 449 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=497, Invalid=1953, Unknown=0, NotChecked=0, Total=2450 [2024-12-02 06:23:14,331 INFO L435 NwaCegarLoop]: 34 mSDtfsCounter, 48 mSDsluCounter, 459 mSDsCounter, 0 mSdLazyCounter, 897 mSolverCounterSat, 112 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 493 SdHoareTripleChecker+Invalid, 1009 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 112 IncrementalHoareTripleChecker+Valid, 897 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-12-02 06:23:14,331 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 493 Invalid, 1009 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [112 Valid, 897 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-12-02 06:23:14,331 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 310 states. [2024-12-02 06:23:14,556 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 310 to 284. [2024-12-02 06:23:14,557 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 284 states, 137 states have (on average 1.1605839416058394) internal successors, (159), 141 states have internal predecessors, (159), 118 states have call successors, (118), 28 states have call predecessors, (118), 28 states have return successors, (117), 114 states have call predecessors, (117), 117 states have call successors, (117) [2024-12-02 06:23:14,558 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 284 states to 284 states and 394 transitions. [2024-12-02 06:23:14,558 INFO L78 Accepts]: Start accepts. Automaton has 284 states and 394 transitions. Word has length 137 [2024-12-02 06:23:14,558 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:23:14,558 INFO L471 AbstractCegarLoop]: Abstraction has 284 states and 394 transitions. [2024-12-02 06:23:14,558 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 29 states have (on average 1.4482758620689655) internal successors, (42), 27 states have internal predecessors, (42), 14 states have call successors, (46), 3 states have call predecessors, (46), 3 states have return successors, (45), 15 states have call predecessors, (45), 14 states have call successors, (45) [2024-12-02 06:23:14,559 INFO L276 IsEmpty]: Start isEmpty. Operand 284 states and 394 transitions. [2024-12-02 06:23:14,559 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2024-12-02 06:23:14,559 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:23:14,559 INFO L218 NwaCegarLoop]: trace histogram [20, 19, 19, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:23:14,567 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2024-12-02 06:23:14,760 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:14,760 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:23:14,760 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:23:14,760 INFO L85 PathProgramCache]: Analyzing trace with hash 721616946, now seen corresponding path program 6 times [2024-12-02 06:23:14,760 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:23:14,760 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280614487] [2024-12-02 06:23:14,760 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-12-02 06:23:14,760 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:23:14,798 INFO L229 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 11 check-sat command(s) [2024-12-02 06:23:14,798 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:23:14,800 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [778619911] [2024-12-02 06:23:14,800 INFO L95 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-12-02 06:23:14,800 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:14,800 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:23:14,801 INFO L229 MonitoredProcess]: Starting monitored process 20 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:23:14,803 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-12-02 06:23:15,034 INFO L229 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2024-12-02 06:23:15,034 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:23:15,035 INFO L256 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 40 conjuncts are in the unsatisfiable core [2024-12-02 06:23:15,037 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:23:19,647 INFO L134 CoverageAnalysis]: Checked inductivity of 832 backedges. 132 proven. 66 refuted. 2 times theorem prover too weak. 632 trivial. 0 not checked. [2024-12-02 06:23:19,647 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:23:19,861 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:23:19,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280614487] [2024-12-02 06:23:19,861 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:23:19,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [778619911] [2024-12-02 06:23:19,861 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [778619911] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:23:19,861 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:23:19,861 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2024-12-02 06:23:19,861 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1708174569] [2024-12-02 06:23:19,861 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:23:19,861 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-12-02 06:23:19,861 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:23:19,861 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-12-02 06:23:19,862 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=281, Unknown=1, NotChecked=0, Total=342 [2024-12-02 06:23:19,862 INFO L87 Difference]: Start difference. First operand 284 states and 394 transitions. Second operand has 16 states, 14 states have (on average 2.0) internal successors, (28), 14 states have internal predecessors, (28), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) [2024-12-02 06:23:21,210 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.06s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-12-02 06:23:25,864 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-12-02 06:23:27,522 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.34s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [0] [2024-12-02 06:23:27,676 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:23:27,676 INFO L93 Difference]: Finished difference Result 291 states and 400 transitions. [2024-12-02 06:23:27,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-12-02 06:23:27,676 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.0) internal successors, (28), 14 states have internal predecessors, (28), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) Word has length 142 [2024-12-02 06:23:27,677 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:23:27,678 INFO L225 Difference]: With dead ends: 291 [2024-12-02 06:23:27,678 INFO L226 Difference]: Without dead ends: 289 [2024-12-02 06:23:27,678 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=128, Invalid=521, Unknown=1, NotChecked=0, Total=650 [2024-12-02 06:23:27,679 INFO L435 NwaCegarLoop]: 33 mSDtfsCounter, 12 mSDsluCounter, 245 mSDsCounter, 0 mSdLazyCounter, 500 mSolverCounterSat, 12 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 278 SdHoareTripleChecker+Invalid, 513 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 500 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.3s IncrementalHoareTripleChecker+Time [2024-12-02 06:23:27,679 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 278 Invalid, 513 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 500 Invalid, 1 Unknown, 0 Unchecked, 7.3s Time] [2024-12-02 06:23:27,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 289 states. [2024-12-02 06:23:27,889 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 289 to 288. [2024-12-02 06:23:27,890 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 288 states, 140 states have (on average 1.1571428571428573) internal successors, (162), 144 states have internal predecessors, (162), 118 states have call successors, (118), 29 states have call predecessors, (118), 29 states have return successors, (117), 114 states have call predecessors, (117), 117 states have call successors, (117) [2024-12-02 06:23:27,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 288 states to 288 states and 397 transitions. [2024-12-02 06:23:27,891 INFO L78 Accepts]: Start accepts. Automaton has 288 states and 397 transitions. Word has length 142 [2024-12-02 06:23:27,892 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:23:27,892 INFO L471 AbstractCegarLoop]: Abstraction has 288 states and 397 transitions. [2024-12-02 06:23:27,892 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.0) internal successors, (28), 14 states have internal predecessors, (28), 8 states have call successors, (22), 2 states have call predecessors, (22), 3 states have return successors, (22), 7 states have call predecessors, (22), 7 states have call successors, (22) [2024-12-02 06:23:27,892 INFO L276 IsEmpty]: Start isEmpty. Operand 288 states and 397 transitions. [2024-12-02 06:23:27,893 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 159 [2024-12-02 06:23:27,893 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:23:27,893 INFO L218 NwaCegarLoop]: trace histogram [23, 22, 22, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:23:27,899 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2024-12-02 06:23:28,094 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:28,094 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:23:28,094 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:23:28,094 INFO L85 PathProgramCache]: Analyzing trace with hash -1166962277, now seen corresponding path program 7 times [2024-12-02 06:23:28,094 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:23:28,094 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [379800844] [2024-12-02 06:23:28,094 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-12-02 06:23:28,094 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:23:28,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-12-02 06:23:28,116 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [509813632] [2024-12-02 06:23:28,116 INFO L95 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-12-02 06:23:28,116 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:28,116 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:23:28,118 INFO L229 MonitoredProcess]: Starting monitored process 21 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:23:28,119 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-12-02 06:23:28,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-12-02 06:23:28,208 INFO L256 TraceCheckSpWp]: Trace formula consists of 362 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-12-02 06:23:28,211 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:23:29,385 INFO L134 CoverageAnalysis]: Checked inductivity of 1097 backedges. 103 proven. 88 refuted. 0 times theorem prover too weak. 906 trivial. 0 not checked. [2024-12-02 06:23:29,386 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:23:30,730 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:23:30,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [379800844] [2024-12-02 06:23:30,730 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:23:30,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [509813632] [2024-12-02 06:23:30,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [509813632] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:23:30,730 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:23:30,730 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2024-12-02 06:23:30,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [701716494] [2024-12-02 06:23:30,730 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:23:30,730 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-12-02 06:23:30,730 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:23:30,731 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-12-02 06:23:30,731 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=858, Unknown=0, NotChecked=0, Total=992 [2024-12-02 06:23:30,731 INFO L87 Difference]: Start difference. First operand 288 states and 397 transitions. Second operand has 20 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 17 states have internal predecessors, (29), 10 states have call successors, (29), 2 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 10 states have call successors, (28) [2024-12-02 06:23:31,788 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:23:31,788 INFO L93 Difference]: Finished difference Result 333 states and 463 transitions. [2024-12-02 06:23:31,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-12-02 06:23:31,789 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 17 states have internal predecessors, (29), 10 states have call successors, (29), 2 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 10 states have call successors, (28) Word has length 158 [2024-12-02 06:23:31,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:23:31,791 INFO L225 Difference]: With dead ends: 333 [2024-12-02 06:23:31,791 INFO L226 Difference]: Without dead ends: 331 [2024-12-02 06:23:31,791 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 231 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 297 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=228, Invalid=1332, Unknown=0, NotChecked=0, Total=1560 [2024-12-02 06:23:31,791 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 32 mSDsluCounter, 325 mSDsCounter, 0 mSdLazyCounter, 904 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 938 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 904 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-12-02 06:23:31,792 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 364 Invalid, 938 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 904 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-12-02 06:23:31,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 331 states. [2024-12-02 06:23:31,999 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 331 to 297. [2024-12-02 06:23:32,000 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 297 states, 144 states have (on average 1.1597222222222223) internal successors, (167), 148 states have internal predecessors, (167), 122 states have call successors, (122), 30 states have call predecessors, (122), 30 states have return successors, (121), 118 states have call predecessors, (121), 121 states have call successors, (121) [2024-12-02 06:23:32,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 297 states to 297 states and 410 transitions. [2024-12-02 06:23:32,002 INFO L78 Accepts]: Start accepts. Automaton has 297 states and 410 transitions. Word has length 158 [2024-12-02 06:23:32,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:23:32,002 INFO L471 AbstractCegarLoop]: Abstraction has 297 states and 410 transitions. [2024-12-02 06:23:32,002 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 1.6111111111111112) internal successors, (29), 17 states have internal predecessors, (29), 10 states have call successors, (29), 2 states have call predecessors, (29), 3 states have return successors, (28), 10 states have call predecessors, (28), 10 states have call successors, (28) [2024-12-02 06:23:32,002 INFO L276 IsEmpty]: Start isEmpty. Operand 297 states and 410 transitions. [2024-12-02 06:23:32,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 170 [2024-12-02 06:23:32,003 INFO L210 NwaCegarLoop]: Found error trace [2024-12-02 06:23:32,003 INFO L218 NwaCegarLoop]: trace histogram [25, 24, 24, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:23:32,012 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-12-02 06:23:32,204 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20,21 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:32,204 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-12-02 06:23:32,204 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-12-02 06:23:32,204 INFO L85 PathProgramCache]: Analyzing trace with hash -1997515563, now seen corresponding path program 3 times [2024-12-02 06:23:32,204 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-12-02 06:23:32,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [28010670] [2024-12-02 06:23:32,204 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-12-02 06:23:32,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-12-02 06:23:32,236 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2024-12-02 06:23:32,236 INFO L230 tOrderPrioritization]: Conjunction of SSA is unknown [2024-12-02 06:23:32,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [753259968] [2024-12-02 06:23:32,237 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-12-02 06:23:32,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-12-02 06:23:32,238 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 [2024-12-02 06:23:32,239 INFO L229 MonitoredProcess]: Starting monitored process 22 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-12-02 06:23:32,240 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-12-02 06:23:32,399 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2024-12-02 06:23:32,400 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-12-02 06:23:32,401 INFO L256 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 39 conjuncts are in the unsatisfiable core [2024-12-02 06:23:32,403 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-12-02 06:23:32,947 INFO L134 CoverageAnalysis]: Checked inductivity of 1291 backedges. 259 proven. 30 refuted. 0 times theorem prover too weak. 1002 trivial. 0 not checked. [2024-12-02 06:23:32,947 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-12-02 06:23:33,743 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-12-02 06:23:33,743 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [28010670] [2024-12-02 06:23:33,743 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-12-02 06:23:33,743 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [753259968] [2024-12-02 06:23:33,743 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [753259968] provided 0 perfect and 1 imperfect interpolant sequences [2024-12-02 06:23:33,743 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-12-02 06:23:33,743 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-12-02 06:23:33,743 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [209293453] [2024-12-02 06:23:33,743 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-12-02 06:23:33,744 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-12-02 06:23:33,744 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-12-02 06:23:33,744 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-12-02 06:23:33,745 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2024-12-02 06:23:33,745 INFO L87 Difference]: Start difference. First operand 297 states and 410 transitions. Second operand has 17 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 8 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 5 states have call predecessors, (14), 7 states have call successors, (14) [2024-12-02 06:23:48,802 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-12-02 06:23:48,802 INFO L93 Difference]: Finished difference Result 330 states and 435 transitions. [2024-12-02 06:23:48,803 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-12-02 06:23:48,803 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 8 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 5 states have call predecessors, (14), 7 states have call successors, (14) Word has length 169 [2024-12-02 06:23:48,803 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-12-02 06:23:48,804 INFO L225 Difference]: With dead ends: 330 [2024-12-02 06:23:48,804 INFO L226 Difference]: Without dead ends: 0 [2024-12-02 06:23:48,805 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 159 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 14.3s TimeCoverageRelationStatistics Valid=169, Invalid=696, Unknown=5, NotChecked=0, Total=870 [2024-12-02 06:23:48,806 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 13 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 343 mSolverCounterSat, 30 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 374 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 343 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-12-02 06:23:48,806 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 155 Invalid, 374 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 343 Invalid, 1 Unknown, 0 Unchecked, 1.5s Time] [2024-12-02 06:23:48,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-12-02 06:23:48,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-12-02 06:23:48,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-12-02 06:23:48,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-12-02 06:23:48,807 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 169 [2024-12-02 06:23:48,807 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-12-02 06:23:48,807 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-12-02 06:23:48,807 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 13 states have (on average 2.076923076923077) internal successors, (27), 13 states have internal predecessors, (27), 8 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 5 states have call predecessors, (14), 7 states have call successors, (14) [2024-12-02 06:23:48,807 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-12-02 06:23:48,808 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-12-02 06:23:48,810 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-12-02 06:23:48,815 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Ended with exit code 0 [2024-12-02 06:23:49,010 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ca047d8e-c910-43a7-a003-76e96eca98f5/bin/uautomizer-verify-84ZbGMXZE1/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable21 [2024-12-02 06:23:49,013 INFO L422 BasicCegarLoop]: Path program histogram: [7, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2024-12-02 06:23:49,014 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-12-02 06:27:48,526 WARN L286 SmtUtils]: Spent 3.72m on a formula simplification. DAG size of input: 784 DAG size of output: 51 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2024-12-02 06:31:54,124 WARN L286 SmtUtils]: Spent 4.09m on a formula simplification. DAG size of input: 800 DAG size of output: 51 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2024-12-02 06:33:10,890 WARN L286 SmtUtils]: Spent 1.28m on a formula simplification. DAG size of input: 393 DAG size of output: 42 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2024-12-02 06:36:27,672 WARN L286 SmtUtils]: Spent 3.27m on a formula simplification. DAG size of input: 800 DAG size of output: 58 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter)