./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/loops-crafted-1/nested3-1_abstracted.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/loops-crafted-1/nested3-1_abstracted.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX --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 Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 898ef25fdb2ae04f56304d500631f410c196b9a77fbfba6f83248dcfc33b301f --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:52:53,700 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:52:53,777 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:52:53,783 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:52:53,784 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:52:53,820 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:52:53,822 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:52:53,823 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:52:53,825 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:52:53,830 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:52:53,831 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:52:53,831 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:52:53,832 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:52:53,834 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:52:53,834 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:52:53,835 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:52:53,835 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:52:53,836 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:52:53,836 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:52:53,837 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:52:53,838 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:52:53,838 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:52:53,840 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:52:53,840 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:52:53,841 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:52:53,841 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:52:53,842 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:52:53,842 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:52:53,843 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:52:53,843 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:52:53,845 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:52:53,845 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:52:53,845 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:52:53,845 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:52:53,846 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:52:53,846 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:52:53,846 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:52:53,847 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:52:53,847 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:52:53,847 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:52:53,848 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:52:53,848 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:52:53,848 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:52:53,849 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:52:53,849 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:52:53,850 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX 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 -> Taipan 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 -> 898ef25fdb2ae04f56304d500631f410c196b9a77fbfba6f83248dcfc33b301f [2023-11-12 00:52:54,188 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:52:54,253 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:52:54,256 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:52:54,257 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:52:54,258 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:52:54,260 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/loops-crafted-1/nested3-1_abstracted.c [2023-11-12 00:52:57,663 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:52:57,869 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:52:57,870 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/sv-benchmarks/c/loops-crafted-1/nested3-1_abstracted.c [2023-11-12 00:52:57,879 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/data/e7492febc/b81e2b3027304377b7e25c413d8c271b/FLAGf1736634b [2023-11-12 00:52:57,897 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/data/e7492febc/b81e2b3027304377b7e25c413d8c271b [2023-11-12 00:52:57,902 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:52:57,904 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:52:57,905 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:52:57,905 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:52:57,914 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:52:57,915 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:52:57" (1/1) ... [2023-11-12 00:52:57,916 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@229c1f5f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:57, skipping insertion in model container [2023-11-12 00:52:57,916 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:52:57" (1/1) ... [2023-11-12 00:52:57,947 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:52:58,173 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/sv-benchmarks/c/loops-crafted-1/nested3-1_abstracted.c[739,752] [2023-11-12 00:52:58,192 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:52:58,202 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:52:58,217 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/sv-benchmarks/c/loops-crafted-1/nested3-1_abstracted.c[739,752] [2023-11-12 00:52:58,224 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:52:58,242 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:52:58,243 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58 WrapperNode [2023-11-12 00:52:58,243 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:52:58,244 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:52:58,244 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:52:58,245 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:52:58,253 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,261 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,292 INFO L138 Inliner]: procedures = 20, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 46 [2023-11-12 00:52:58,293 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:52:58,293 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:52:58,294 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:52:58,294 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:52:58,305 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,305 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,307 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,307 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,311 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,315 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,316 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,317 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,319 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:52:58,320 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:52:58,320 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:52:58,321 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:52:58,321 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (1/1) ... [2023-11-12 00:52:58,328 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:52:58,345 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:52:58,367 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:52:58,391 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:52:58,412 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:52:58,412 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:52:58,413 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:52:58,413 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:52:58,413 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:52:58,413 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:52:58,506 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:52:58,509 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:52:58,782 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:52:58,888 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:52:58,888 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 00:52:58,891 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:52:58 BoogieIcfgContainer [2023-11-12 00:52:58,892 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:52:58,895 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:52:58,895 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:52:58,899 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:52:58,899 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:52:57" (1/3) ... [2023-11-12 00:52:58,900 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3949014a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:52:58, skipping insertion in model container [2023-11-12 00:52:58,901 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:52:58" (2/3) ... [2023-11-12 00:52:58,901 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3949014a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:52:58, skipping insertion in model container [2023-11-12 00:52:58,902 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:52:58" (3/3) ... [2023-11-12 00:52:58,903 INFO L112 eAbstractionObserver]: Analyzing ICFG nested3-1_abstracted.c [2023-11-12 00:52:58,928 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:52:58,928 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:52:58,977 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:52:58,984 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, 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;@37dccb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:52:58,984 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:52:58,988 INFO L276 IsEmpty]: Start isEmpty. Operand has 16 states, 10 states have (on average 1.4) internal successors, (14), 11 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-12 00:52:58,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-12 00:52:58,997 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:52:58,998 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-12 00:52:58,998 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:52:59,003 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:52:59,004 INFO L85 PathProgramCache]: Analyzing trace with hash -1091749507, now seen corresponding path program 1 times [2023-11-12 00:52:59,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:52:59,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1066564492] [2023-11-12 00:52:59,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:52:59,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:52:59,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:52:59,243 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:52:59,244 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:52:59,244 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1066564492] [2023-11-12 00:52:59,245 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1066564492] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:52:59,246 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:52:59,246 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-12 00:52:59,248 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1308282223] [2023-11-12 00:52:59,250 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:52:59,255 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:52:59,255 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:52:59,302 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:52:59,303 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 00:52:59,308 INFO L87 Difference]: Start difference. First operand has 16 states, 10 states have (on average 1.4) internal successors, (14), 11 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 3 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:52:59,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:52:59,462 INFO L93 Difference]: Finished difference Result 37 states and 54 transitions. [2023-11-12 00:52:59,464 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:52:59,465 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2023-11-12 00:52:59,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:52:59,474 INFO L225 Difference]: With dead ends: 37 [2023-11-12 00:52:59,474 INFO L226 Difference]: Without dead ends: 20 [2023-11-12 00:52:59,491 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 00:52:59,495 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 24 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:52:59,497 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 24 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:52:59,520 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-11-12 00:52:59,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 15. [2023-11-12 00:52:59,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 10 states have (on average 1.3) internal successors, (13), 11 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-12 00:52:59,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2023-11-12 00:52:59,546 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 6 [2023-11-12 00:52:59,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:52:59,546 INFO L495 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2023-11-12 00:52:59,547 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 1.6666666666666667) internal successors, (5), 2 states have internal predecessors, (5), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:52:59,547 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2023-11-12 00:52:59,549 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-12 00:52:59,549 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:52:59,549 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:52:59,550 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-12 00:52:59,550 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:52:59,551 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:52:59,551 INFO L85 PathProgramCache]: Analyzing trace with hash -1655309817, now seen corresponding path program 1 times [2023-11-12 00:52:59,552 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:52:59,552 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [161813195] [2023-11-12 00:52:59,552 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:52:59,553 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:52:59,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:52:59,639 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:52:59,639 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:52:59,639 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [161813195] [2023-11-12 00:52:59,640 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [161813195] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:52:59,640 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:52:59,640 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-12 00:52:59,641 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1105657712] [2023-11-12 00:52:59,641 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:52:59,642 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-12 00:52:59,643 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:52:59,643 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-12 00:52:59,644 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 00:52:59,644 INFO L87 Difference]: Start difference. First operand 15 states and 18 transitions. Second operand has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:52:59,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:52:59,674 INFO L93 Difference]: Finished difference Result 31 states and 39 transitions. [2023-11-12 00:52:59,675 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-12 00:52:59,675 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-12 00:52:59,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:52:59,676 INFO L225 Difference]: With dead ends: 31 [2023-11-12 00:52:59,677 INFO L226 Difference]: Without dead ends: 18 [2023-11-12 00:52:59,677 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-12 00:52:59,679 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 1 mSDsluCounter, 11 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 23 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:52:59,681 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 23 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:52:59,682 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2023-11-12 00:52:59,686 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 16. [2023-11-12 00:52:59,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-12 00:52:59,688 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2023-11-12 00:52:59,688 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 7 [2023-11-12 00:52:59,688 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:52:59,689 INFO L495 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2023-11-12 00:52:59,689 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:52:59,689 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2023-11-12 00:52:59,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-12 00:52:59,690 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:52:59,690 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:52:59,691 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-12 00:52:59,691 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:52:59,692 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:52:59,692 INFO L85 PathProgramCache]: Analyzing trace with hash -1647057710, now seen corresponding path program 1 times [2023-11-12 00:52:59,692 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:52:59,693 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [579235576] [2023-11-12 00:52:59,693 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:52:59,693 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:52:59,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:52:59,958 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:52:59,959 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:52:59,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [579235576] [2023-11-12 00:52:59,959 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [579235576] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:52:59,959 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:52:59,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-12 00:52:59,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1093224738] [2023-11-12 00:52:59,960 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:52:59,961 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:52:59,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:52:59,962 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:52:59,962 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:52:59,962 INFO L87 Difference]: Start difference. First operand 16 states and 19 transitions. Second operand has 5 states, 4 states have (on average 1.5) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:53:00,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:53:00,063 INFO L93 Difference]: Finished difference Result 23 states and 25 transitions. [2023-11-12 00:53:00,064 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:53:00,065 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.5) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2023-11-12 00:53:00,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:53:00,067 INFO L225 Difference]: With dead ends: 23 [2023-11-12 00:53:00,068 INFO L226 Difference]: Without dead ends: 21 [2023-11-12 00:53:00,070 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-11-12 00:53:00,073 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 10 mSDsluCounter, 26 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:53:00,077 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 37 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:53:00,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2023-11-12 00:53:00,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 20. [2023-11-12 00:53:00,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-12 00:53:00,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 22 transitions. [2023-11-12 00:53:00,094 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 22 transitions. Word has length 7 [2023-11-12 00:53:00,094 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:53:00,095 INFO L495 AbstractCegarLoop]: Abstraction has 20 states and 22 transitions. [2023-11-12 00:53:00,095 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.5) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-11-12 00:53:00,095 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 22 transitions. [2023-11-12 00:53:00,096 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-11-12 00:53:00,096 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:53:00,096 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:53:00,097 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-12 00:53:00,097 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:53:00,098 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:53:00,098 INFO L85 PathProgramCache]: Analyzing trace with hash -1577091667, now seen corresponding path program 1 times [2023-11-12 00:53:00,098 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:53:00,098 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [578521290] [2023-11-12 00:53:00,099 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:00,099 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:53:00,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:00,301 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:53:00,303 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:53:00,303 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [578521290] [2023-11-12 00:53:00,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [578521290] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:53:00,304 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2000451064] [2023-11-12 00:53:00,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:00,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:00,306 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:53:00,310 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:53:00,337 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:53:00,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:00,401 INFO L262 TraceCheckSpWp]: Trace formula consists of 57 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-12 00:53:00,408 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:53:00,511 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:53:00,511 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:53:00,594 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-12 00:53:00,595 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2000451064] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:53:00,595 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [889327914] [2023-11-12 00:53:00,623 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-12 00:53:00,623 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:53:00,630 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:53:00,638 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:53:00,639 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:53:02,001 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 83 for LOIs [2023-11-12 00:53:02,583 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:53:05,329 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '326#(and (exists ((|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12| Int) (|v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_9| Int)) (and (<= 1 |#StackHeapBarrier|) (= (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12| 2) 0) (= |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_9| 0) (<= 1 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12|) (= |v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_9| 0) (<= 268435455 (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12| 4294967296)))) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:53:05,330 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:53:05,330 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-12 00:53:05,330 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 6, 6] total 9 [2023-11-12 00:53:05,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [159820219] [2023-11-12 00:53:05,330 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-12 00:53:05,331 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-12 00:53:05,331 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:53:05,332 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-12 00:53:05,333 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=253, Unknown=0, NotChecked=0, Total=306 [2023-11-12 00:53:05,333 INFO L87 Difference]: Start difference. First operand 20 states and 22 transitions. Second operand has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-12 00:53:05,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:53:05,495 INFO L93 Difference]: Finished difference Result 54 states and 65 transitions. [2023-11-12 00:53:05,495 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-12 00:53:05,495 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 14 [2023-11-12 00:53:05,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:53:05,497 INFO L225 Difference]: With dead ends: 54 [2023-11-12 00:53:05,497 INFO L226 Difference]: Without dead ends: 36 [2023-11-12 00:53:05,498 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 27 SyntacticMatches, 2 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=58, Invalid=284, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:53:05,499 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 14 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:53:05,500 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 99 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:53:05,501 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2023-11-12 00:53:05,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 31. [2023-11-12 00:53:05,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-12 00:53:05,516 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 36 transitions. [2023-11-12 00:53:05,517 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 36 transitions. Word has length 14 [2023-11-12 00:53:05,517 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:53:05,517 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 36 transitions. [2023-11-12 00:53:05,518 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 5 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-12 00:53:05,518 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 36 transitions. [2023-11-12 00:53:05,519 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2023-11-12 00:53:05,519 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:53:05,519 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-11-12 00:53:05,528 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:53:05,726 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:05,727 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:53:05,727 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:53:05,727 INFO L85 PathProgramCache]: Analyzing trace with hash 1395635015, now seen corresponding path program 2 times [2023-11-12 00:53:05,727 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:53:05,727 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [149673894] [2023-11-12 00:53:05,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:05,728 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:53:05,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:05,866 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-12 00:53:05,866 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:53:05,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [149673894] [2023-11-12 00:53:05,867 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [149673894] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:53:05,867 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1438811056] [2023-11-12 00:53:05,867 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:53:05,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:05,868 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:53:05,869 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:53:05,893 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:53:05,935 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-12 00:53:05,935 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:53:05,936 INFO L262 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 13 conjunts are in the unsatisfiable core [2023-11-12 00:53:05,938 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:53:05,959 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-12 00:53:05,959 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:53:06,120 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-12 00:53:06,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1438811056] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:53:06,121 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1128862592] [2023-11-12 00:53:06,123 INFO L159 IcfgInterpreter]: Started Sifa with 12 locations of interest [2023-11-12 00:53:06,123 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:53:06,124 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:53:06,124 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:53:06,124 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:53:06,745 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 83 for LOIs [2023-11-12 00:53:07,213 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:53:11,925 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '595#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_27| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_19| Int) (|v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_19| Int)) (and (<= 268435455 (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_27| 4294967296)) (<= 1 |#StackHeapBarrier|) (<= 1 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_27|) (= |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_19| 0) (= (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_27| 2) 0) (= |v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_19| 0))))' at error location [2023-11-12 00:53:11,925 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:53:11,926 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-12 00:53:11,926 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 8] total 12 [2023-11-12 00:53:11,926 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1443004986] [2023-11-12 00:53:11,926 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-12 00:53:11,927 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-12 00:53:11,927 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:53:11,928 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-12 00:53:11,929 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=343, Unknown=1, NotChecked=0, Total=420 [2023-11-12 00:53:11,929 INFO L87 Difference]: Start difference. First operand 31 states and 36 transitions. Second operand has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 6 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-12 00:53:12,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:53:12,263 INFO L93 Difference]: Finished difference Result 78 states and 97 transitions. [2023-11-12 00:53:12,264 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:53:12,264 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 6 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 21 [2023-11-12 00:53:12,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:53:12,267 INFO L225 Difference]: With dead ends: 78 [2023-11-12 00:53:12,267 INFO L226 Difference]: Without dead ends: 47 [2023-11-12 00:53:12,269 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=99, Invalid=452, Unknown=1, NotChecked=0, Total=552 [2023-11-12 00:53:12,270 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 16 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:53:12,270 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 99 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:53:12,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-11-12 00:53:12,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 28. [2023-11-12 00:53:12,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 20 states have (on average 1.1) internal successors, (22), 20 states have internal predecessors, (22), 5 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-12 00:53:12,284 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 31 transitions. [2023-11-12 00:53:12,284 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 31 transitions. Word has length 21 [2023-11-12 00:53:12,285 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:53:12,285 INFO L495 AbstractCegarLoop]: Abstraction has 28 states and 31 transitions. [2023-11-12 00:53:12,285 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.090909090909091) internal successors, (23), 11 states have internal predecessors, (23), 6 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-12 00:53:12,286 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 31 transitions. [2023-11-12 00:53:12,287 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2023-11-12 00:53:12,287 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:53:12,287 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:53:12,307 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 00:53:12,494 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:12,494 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:53:12,495 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:53:12,495 INFO L85 PathProgramCache]: Analyzing trace with hash -1221652332, now seen corresponding path program 1 times [2023-11-12 00:53:12,495 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:53:12,495 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [913122077] [2023-11-12 00:53:12,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:12,495 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:53:12,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:12,631 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 9 proven. 12 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-12 00:53:12,632 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:53:12,632 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [913122077] [2023-11-12 00:53:12,632 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [913122077] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:53:12,632 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1250079763] [2023-11-12 00:53:12,633 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:12,633 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:12,633 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:53:12,634 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:53:12,660 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:53:12,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:12,717 INFO L262 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 10 conjunts are in the unsatisfiable core [2023-11-12 00:53:12,721 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:53:12,801 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2023-11-12 00:53:12,802 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:53:12,957 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 16 proven. 2 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2023-11-12 00:53:12,957 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1250079763] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:53:12,957 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1561204974] [2023-11-12 00:53:12,960 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:53:12,961 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:53:12,961 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:53:12,962 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:53:12,962 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:53:15,224 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:53:15,228 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:53:15,462 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '988#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:53:15,462 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:53:15,462 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-12 00:53:15,462 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 14 [2023-11-12 00:53:15,463 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [951614631] [2023-11-12 00:53:15,463 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-12 00:53:15,464 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-11-12 00:53:15,464 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:53:15,464 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-11-12 00:53:15,465 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2023-11-12 00:53:15,465 INFO L87 Difference]: Start difference. First operand 28 states and 31 transitions. Second operand has 14 states, 14 states have (on average 2.642857142857143) internal successors, (37), 14 states have internal predecessors, (37), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2023-11-12 00:53:16,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:53:16,137 INFO L93 Difference]: Finished difference Result 113 states and 149 transitions. [2023-11-12 00:53:16,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2023-11-12 00:53:16,138 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.642857142857143) internal successors, (37), 14 states have internal predecessors, (37), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) Word has length 35 [2023-11-12 00:53:16,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:53:16,140 INFO L225 Difference]: With dead ends: 113 [2023-11-12 00:53:16,140 INFO L226 Difference]: Without dead ends: 87 [2023-11-12 00:53:16,142 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 319 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=262, Invalid=1070, Unknown=0, NotChecked=0, Total=1332 [2023-11-12 00:53:16,143 INFO L413 NwaCegarLoop]: 22 mSDtfsCounter, 42 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 150 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 176 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 150 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-12 00:53:16,144 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 110 Invalid, 176 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 150 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-12 00:53:16,145 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2023-11-12 00:53:16,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 79. [2023-11-12 00:53:16,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 55 states have (on average 1.0909090909090908) internal successors, (60), 55 states have internal predecessors, (60), 21 states have call successors, (21), 3 states have call predecessors, (21), 2 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2023-11-12 00:53:16,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 101 transitions. [2023-11-12 00:53:16,184 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 101 transitions. Word has length 35 [2023-11-12 00:53:16,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:53:16,184 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 101 transitions. [2023-11-12 00:53:16,185 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.642857142857143) internal successors, (37), 14 states have internal predecessors, (37), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (10), 8 states have call predecessors, (10), 8 states have call successors, (10) [2023-11-12 00:53:16,185 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 101 transitions. [2023-11-12 00:53:16,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 151 [2023-11-12 00:53:16,192 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:53:16,193 INFO L195 NwaCegarLoop]: trace histogram [21, 20, 20, 16, 16, 16, 16, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2023-11-12 00:53:16,207 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-12 00:53:16,400 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:16,400 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:53:16,401 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:53:16,401 INFO L85 PathProgramCache]: Analyzing trace with hash 1930047857, now seen corresponding path program 2 times [2023-11-12 00:53:16,401 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:53:16,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [471114752] [2023-11-12 00:53:16,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:16,401 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:53:16,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:16,951 INFO L134 CoverageAnalysis]: Checked inductivity of 1252 backedges. 215 proven. 22 refuted. 0 times theorem prover too weak. 1015 trivial. 0 not checked. [2023-11-12 00:53:16,951 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:53:16,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [471114752] [2023-11-12 00:53:16,951 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [471114752] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:53:16,952 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1289958829] [2023-11-12 00:53:16,952 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-12 00:53:16,952 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:16,952 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:53:16,954 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:53:16,988 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:53:17,426 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2023-11-12 00:53:17,427 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:53:17,430 INFO L262 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 15 conjunts are in the unsatisfiable core [2023-11-12 00:53:17,439 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:53:17,514 INFO L134 CoverageAnalysis]: Checked inductivity of 1252 backedges. 278 proven. 22 refuted. 0 times theorem prover too weak. 952 trivial. 0 not checked. [2023-11-12 00:53:17,515 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:53:17,676 INFO L134 CoverageAnalysis]: Checked inductivity of 1252 backedges. 278 proven. 14 refuted. 0 times theorem prover too weak. 960 trivial. 0 not checked. [2023-11-12 00:53:17,676 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1289958829] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:53:17,676 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [271266428] [2023-11-12 00:53:17,680 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:53:17,680 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:53:17,681 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:53:17,681 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:53:17,681 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:53:19,433 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:53:19,437 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:53:19,658 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2241#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:53:19,658 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:53:19,658 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-12 00:53:19,659 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9, 6] total 13 [2023-11-12 00:53:19,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [12875181] [2023-11-12 00:53:19,659 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-12 00:53:19,661 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-11-12 00:53:19,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:53:19,662 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-11-12 00:53:19,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=285, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:53:19,663 INFO L87 Difference]: Start difference. First operand 79 states and 101 transitions. Second operand has 13 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 13 states have internal predecessors, (41), 9 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 8 states have call predecessors, (12), 9 states have call successors, (12) [2023-11-12 00:53:19,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:53:19,913 INFO L93 Difference]: Finished difference Result 181 states and 244 transitions. [2023-11-12 00:53:19,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:53:19,914 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 13 states have internal predecessors, (41), 9 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 8 states have call predecessors, (12), 9 states have call successors, (12) Word has length 150 [2023-11-12 00:53:19,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:53:19,916 INFO L225 Difference]: With dead ends: 181 [2023-11-12 00:53:19,916 INFO L226 Difference]: Without dead ends: 111 [2023-11-12 00:53:19,918 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 457 GetRequests, 439 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=57, Invalid=285, Unknown=0, NotChecked=0, Total=342 [2023-11-12 00:53:19,919 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 12 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 173 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 77 SdHoareTripleChecker+Invalid, 177 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 173 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:53:19,920 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 77 Invalid, 177 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 173 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:53:19,921 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-11-12 00:53:19,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 91. [2023-11-12 00:53:19,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 63 states have (on average 1.0793650793650793) internal successors, (68), 63 states have internal predecessors, (68), 25 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2023-11-12 00:53:19,962 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 117 transitions. [2023-11-12 00:53:19,963 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 117 transitions. Word has length 150 [2023-11-12 00:53:19,963 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:53:19,964 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 117 transitions. [2023-11-12 00:53:19,964 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 13 states have internal predecessors, (41), 9 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 8 states have call predecessors, (12), 9 states have call successors, (12) [2023-11-12 00:53:19,964 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 117 transitions. [2023-11-12 00:53:19,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 179 [2023-11-12 00:53:19,969 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:53:19,969 INFO L195 NwaCegarLoop]: trace histogram [25, 24, 24, 20, 20, 20, 20, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1] [2023-11-12 00:53:19,984 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 00:53:20,177 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:20,177 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:53:20,178 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:53:20,178 INFO L85 PathProgramCache]: Analyzing trace with hash -142712643, now seen corresponding path program 3 times [2023-11-12 00:53:20,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:53:20,178 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [923145766] [2023-11-12 00:53:20,179 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:20,179 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:53:20,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:20,770 INFO L134 CoverageAnalysis]: Checked inductivity of 1830 backedges. 310 proven. 35 refuted. 0 times theorem prover too weak. 1485 trivial. 0 not checked. [2023-11-12 00:53:20,774 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:53:20,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [923145766] [2023-11-12 00:53:20,775 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [923145766] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:53:20,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [868323279] [2023-11-12 00:53:20,776 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-12 00:53:20,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:20,776 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:53:20,789 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:53:20,832 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:53:20,988 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-12 00:53:20,989 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-12 00:53:20,992 INFO L262 TraceCheckSpWp]: Trace formula consists of 399 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-12 00:53:21,012 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:53:21,349 INFO L134 CoverageAnalysis]: Checked inductivity of 1830 backedges. 48 proven. 573 refuted. 0 times theorem prover too weak. 1209 trivial. 0 not checked. [2023-11-12 00:53:21,350 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:53:22,063 INFO L134 CoverageAnalysis]: Checked inductivity of 1830 backedges. 61 proven. 560 refuted. 0 times theorem prover too weak. 1209 trivial. 0 not checked. [2023-11-12 00:53:22,064 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [868323279] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:53:22,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [484726340] [2023-11-12 00:53:22,067 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:53:22,068 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:53:22,068 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:53:22,068 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:53:22,069 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:53:23,685 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:53:23,688 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:53:23,990 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3780#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:53:23,990 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:53:23,990 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-12 00:53:23,991 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 12, 12] total 28 [2023-11-12 00:53:23,991 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1912261393] [2023-11-12 00:53:23,991 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-12 00:53:23,992 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2023-11-12 00:53:23,993 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:53:23,994 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2023-11-12 00:53:23,995 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=200, Invalid=990, Unknown=0, NotChecked=0, Total=1190 [2023-11-12 00:53:23,996 INFO L87 Difference]: Start difference. First operand 91 states and 117 transitions. Second operand has 28 states, 28 states have (on average 3.0357142857142856) internal successors, (85), 28 states have internal predecessors, (85), 22 states have call successors, (32), 2 states have call predecessors, (32), 1 states have return successors, (31), 22 states have call predecessors, (31), 22 states have call successors, (31) [2023-11-12 00:53:30,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:53:30,855 INFO L93 Difference]: Finished difference Result 358 states and 492 transitions. [2023-11-12 00:53:30,855 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2023-11-12 00:53:30,855 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 3.0357142857142856) internal successors, (85), 28 states have internal predecessors, (85), 22 states have call successors, (32), 2 states have call predecessors, (32), 1 states have return successors, (31), 22 states have call predecessors, (31), 22 states have call successors, (31) Word has length 178 [2023-11-12 00:53:30,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:53:30,859 INFO L225 Difference]: With dead ends: 358 [2023-11-12 00:53:30,860 INFO L226 Difference]: Without dead ends: 285 [2023-11-12 00:53:30,867 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 604 GetRequests, 508 SyntacticMatches, 0 SemanticMatches, 96 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3072 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=1675, Invalid=7831, Unknown=0, NotChecked=0, Total=9506 [2023-11-12 00:53:30,868 INFO L413 NwaCegarLoop]: 66 mSDtfsCounter, 117 mSDsluCounter, 370 mSDsCounter, 0 mSdLazyCounter, 1208 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 121 SdHoareTripleChecker+Valid, 436 SdHoareTripleChecker+Invalid, 1279 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 1208 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:53:30,869 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [121 Valid, 436 Invalid, 1279 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 1208 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2023-11-12 00:53:30,870 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 285 states. [2023-11-12 00:53:30,977 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 285 to 265. [2023-11-12 00:53:30,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 265 states, 181 states have (on average 1.0607734806629834) internal successors, (192), 181 states have internal predecessors, (192), 81 states have call successors, (81), 3 states have call predecessors, (81), 2 states have return successors, (80), 80 states have call predecessors, (80), 80 states have call successors, (80) [2023-11-12 00:53:30,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 265 states to 265 states and 353 transitions. [2023-11-12 00:53:30,984 INFO L78 Accepts]: Start accepts. Automaton has 265 states and 353 transitions. Word has length 178 [2023-11-12 00:53:30,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:53:30,985 INFO L495 AbstractCegarLoop]: Abstraction has 265 states and 353 transitions. [2023-11-12 00:53:30,985 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 3.0357142857142856) internal successors, (85), 28 states have internal predecessors, (85), 22 states have call successors, (32), 2 states have call predecessors, (32), 1 states have return successors, (31), 22 states have call predecessors, (31), 22 states have call successors, (31) [2023-11-12 00:53:30,985 INFO L276 IsEmpty]: Start isEmpty. Operand 265 states and 353 transitions. [2023-11-12 00:53:31,004 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 577 [2023-11-12 00:53:31,005 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:53:31,005 INFO L195 NwaCegarLoop]: trace histogram [81, 80, 80, 70, 70, 70, 70, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1] [2023-11-12 00:53:31,022 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 00:53:31,218 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:31,218 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:53:31,218 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:53:31,219 INFO L85 PathProgramCache]: Analyzing trace with hash -1414406947, now seen corresponding path program 4 times [2023-11-12 00:53:31,219 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:53:31,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [738731545] [2023-11-12 00:53:31,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:53:31,219 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:53:31,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:33,224 INFO L134 CoverageAnalysis]: Checked inductivity of 20935 backedges. 1628 proven. 70 refuted. 0 times theorem prover too weak. 19237 trivial. 0 not checked. [2023-11-12 00:53:33,225 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:53:33,225 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [738731545] [2023-11-12 00:53:33,225 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [738731545] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:53:33,225 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1508301821] [2023-11-12 00:53:33,226 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-12 00:53:33,226 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:53:33,226 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:53:33,227 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:53:33,262 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_2f9b2233-1c5c-4bed-96e6-96a87748b264/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:53:33,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:53:33,653 INFO L262 TraceCheckSpWp]: Trace formula consists of 1239 conjuncts, 34 conjunts are in the unsatisfiable core [2023-11-12 00:53:33,675 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:53:33,973 INFO L134 CoverageAnalysis]: Checked inductivity of 20935 backedges. 3526 proven. 70 refuted. 0 times theorem prover too weak. 17339 trivial. 0 not checked. [2023-11-12 00:53:33,973 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:53:35,402 INFO L134 CoverageAnalysis]: Checked inductivity of 20935 backedges. 3635 proven. 3535 refuted. 0 times theorem prover too weak. 13765 trivial. 0 not checked. [2023-11-12 00:53:35,402 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1508301821] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:53:35,402 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2082603182] [2023-11-12 00:53:35,405 INFO L159 IcfgInterpreter]: Started Sifa with 14 locations of interest [2023-11-12 00:53:35,406 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:53:35,406 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:53:35,406 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:53:35,407 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:53:36,971 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-11-12 00:53:36,974 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:53:37,358 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '8426#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-12 00:53:37,358 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:53:37,358 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-12 00:53:37,359 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 18] total 35 [2023-11-12 00:53:37,359 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [226066125] [2023-11-12 00:53:37,360 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-12 00:53:37,362 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2023-11-12 00:53:37,362 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:53:37,364 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2023-11-12 00:53:37,365 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=254, Invalid=1468, Unknown=0, NotChecked=0, Total=1722 [2023-11-12 00:53:37,365 INFO L87 Difference]: Start difference. First operand 265 states and 353 transitions. Second operand has 35 states, 35 states have (on average 2.742857142857143) internal successors, (96), 35 states have internal predecessors, (96), 29 states have call successors, (39), 2 states have call predecessors, (39), 2 states have return successors, (38), 29 states have call predecessors, (38), 29 states have call successors, (38)