./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/loops-crafted-1/nested3-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/config/TaipanReach.xml -i ../../sv-benchmarks/c/loops-crafted-1/nested3-1.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91 --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 ed8e064f31e82b4c33cb383334d25637eef982ae8d5b8603579b97c7fdfe808e --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-11-24 23:59:06,935 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-24 23:59:07,035 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-24 23:59:07,042 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-24 23:59:07,042 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-24 23:59:07,081 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-24 23:59:07,082 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-24 23:59:07,082 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-24 23:59:07,084 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-24 23:59:07,089 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-24 23:59:07,090 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-24 23:59:07,090 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-24 23:59:07,091 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-24 23:59:07,093 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-24 23:59:07,094 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-24 23:59:07,094 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-24 23:59:07,095 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-24 23:59:07,095 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-24 23:59:07,096 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-24 23:59:07,096 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-24 23:59:07,097 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-24 23:59:07,097 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-24 23:59:07,098 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-24 23:59:07,099 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-24 23:59:07,099 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-24 23:59:07,100 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-24 23:59:07,100 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-24 23:59:07,101 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-24 23:59:07,101 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-24 23:59:07,101 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-24 23:59:07,102 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-24 23:59:07,102 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-24 23:59:07,103 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-24 23:59:07,103 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-24 23:59:07,103 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-24 23:59:07,104 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-24 23:59:07,104 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-24 23:59:07,104 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:59:07,104 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-24 23:59:07,105 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-24 23:59:07,105 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-24 23:59:07,105 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-24 23:59:07,106 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-24 23:59:07,106 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-24 23:59:07,106 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-24 23:59:07,106 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-24 23:59:07,107 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-24 23:59:07,107 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_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/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_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91 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 -> ed8e064f31e82b4c33cb383334d25637eef982ae8d5b8603579b97c7fdfe808e [2023-11-24 23:59:07,480 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-24 23:59:07,514 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-24 23:59:07,517 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-24 23:59:07,519 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-24 23:59:07,520 INFO L274 PluginConnector]: CDTParser initialized [2023-11-24 23:59:07,521 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/../../sv-benchmarks/c/loops-crafted-1/nested3-1.c [2023-11-24 23:59:10,783 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-24 23:59:11,018 INFO L384 CDTParser]: Found 1 translation units. [2023-11-24 23:59:11,019 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/sv-benchmarks/c/loops-crafted-1/nested3-1.c [2023-11-24 23:59:11,028 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/data/6ad019996/3bdf58abe40c474c9ea101a1604b8227/FLAG3f19eeec6 [2023-11-24 23:59:11,050 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/data/6ad019996/3bdf58abe40c474c9ea101a1604b8227 [2023-11-24 23:59:11,060 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-24 23:59:11,065 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-24 23:59:11,071 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-24 23:59:11,073 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-24 23:59:11,086 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-24 23:59:11,087 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,089 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@330d6f5f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11, skipping insertion in model container [2023-11-24 23:59:11,089 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,117 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-24 23:59:11,329 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_28e7bf20-23d7-4810-8592-dea2262d1e4c/sv-benchmarks/c/loops-crafted-1/nested3-1.c[321,334] [2023-11-24 23:59:11,356 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:59:11,368 INFO L202 MainTranslator]: Completed pre-run [2023-11-24 23:59:11,383 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_28e7bf20-23d7-4810-8592-dea2262d1e4c/sv-benchmarks/c/loops-crafted-1/nested3-1.c[321,334] [2023-11-24 23:59:11,398 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:59:11,414 INFO L206 MainTranslator]: Completed translation [2023-11-24 23:59:11,415 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11 WrapperNode [2023-11-24 23:59:11,415 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-24 23:59:11,416 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-24 23:59:11,417 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-24 23:59:11,417 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-24 23:59:11,426 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,433 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,457 INFO L138 Inliner]: procedures = 12, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 41 [2023-11-24 23:59:11,458 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-24 23:59:11,459 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-24 23:59:11,459 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-24 23:59:11,459 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-24 23:59:11,469 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,470 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,480 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,481 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,485 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,494 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,496 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,502 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,504 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-24 23:59:11,506 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-24 23:59:11,507 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-24 23:59:11,507 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-24 23:59:11,508 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (1/1) ... [2023-11-24 23:59:11,515 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:59:11,529 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:59:11,560 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-24 23:59:11,574 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-24 23:59:11,606 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-24 23:59:11,607 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-24 23:59:11,607 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-24 23:59:11,607 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-24 23:59:11,609 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-24 23:59:11,609 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-24 23:59:11,683 INFO L241 CfgBuilder]: Building ICFG [2023-11-24 23:59:11,686 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-24 23:59:11,902 INFO L282 CfgBuilder]: Performing block encoding [2023-11-24 23:59:11,955 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-24 23:59:11,955 INFO L309 CfgBuilder]: Removed 3 assume(true) statements. [2023-11-24 23:59:11,960 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:59:11 BoogieIcfgContainer [2023-11-24 23:59:11,960 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-24 23:59:11,964 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-24 23:59:11,964 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-24 23:59:11,968 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-24 23:59:11,968 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.11 11:59:11" (1/3) ... [2023-11-24 23:59:11,969 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@368f1561 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:59:11, skipping insertion in model container [2023-11-24 23:59:11,969 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:59:11" (2/3) ... [2023-11-24 23:59:11,971 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@368f1561 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:59:11, skipping insertion in model container [2023-11-24 23:59:11,971 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:59:11" (3/3) ... [2023-11-24 23:59:11,973 INFO L112 eAbstractionObserver]: Analyzing ICFG nested3-1.c [2023-11-24 23:59:11,995 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-24 23:59:11,996 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-24 23:59:12,061 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-24 23:59:12,072 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;@2a665c67, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-24 23:59:12,073 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-24 23:59:12,078 INFO L276 IsEmpty]: Start isEmpty. Operand has 17 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 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-24 23:59:12,086 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2023-11-24 23:59:12,087 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:12,087 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2023-11-24 23:59:12,088 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:12,094 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:12,094 INFO L85 PathProgramCache]: Analyzing trace with hash -1453215626, now seen corresponding path program 1 times [2023-11-24 23:59:12,106 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:12,106 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1330036511] [2023-11-24 23:59:12,107 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:12,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:12,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:12,410 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-24 23:59:12,411 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:12,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1330036511] [2023-11-24 23:59:12,413 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1330036511] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:59:12,413 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:59:12,413 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-24 23:59:12,415 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1865650547] [2023-11-24 23:59:12,416 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:59:12,421 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:59:12,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:12,454 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:59:12,455 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:59:12,457 INFO L87 Difference]: Start difference. First operand has 17 states, 11 states have (on average 1.4545454545454546) internal successors, (16), 12 states have internal predecessors, (16), 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-24 23:59:12,512 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:12,513 INFO L93 Difference]: Finished difference Result 40 states and 60 transitions. [2023-11-24 23:59:12,515 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:59:12,516 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-24 23:59:12,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:12,525 INFO L225 Difference]: With dead ends: 40 [2023-11-24 23:59:12,525 INFO L226 Difference]: Without dead ends: 22 [2023-11-24 23:59:12,529 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-24 23:59:12,533 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 6 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 28 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.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:59:12,534 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 28 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:59:12,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2023-11-24 23:59:12,574 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 16. [2023-11-24 23:59:12,575 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 11 states have (on average 1.3636363636363635) internal successors, (15), 12 states have internal predecessors, (15), 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-24 23:59:12,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 20 transitions. [2023-11-24 23:59:12,578 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 20 transitions. Word has length 6 [2023-11-24 23:59:12,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:12,579 INFO L495 AbstractCegarLoop]: Abstraction has 16 states and 20 transitions. [2023-11-24 23:59:12,579 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-24 23:59:12,579 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 20 transitions. [2023-11-24 23:59:12,580 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2023-11-24 23:59:12,580 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:12,580 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:12,581 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-24 23:59:12,581 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:12,582 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:12,582 INFO L85 PathProgramCache]: Analyzing trace with hash 569943281, now seen corresponding path program 1 times [2023-11-24 23:59:12,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:12,583 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1047361322] [2023-11-24 23:59:12,583 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:12,583 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:12,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:12,657 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-24 23:59:12,657 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:12,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1047361322] [2023-11-24 23:59:12,658 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1047361322] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:59:12,658 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:59:12,659 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-24 23:59:12,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1646484730] [2023-11-24 23:59:12,659 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:59:12,660 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:59:12,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:12,661 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:59:12,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:59:12,663 INFO L87 Difference]: Start difference. First operand 16 states and 20 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-24 23:59:12,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:12,705 INFO L93 Difference]: Finished difference Result 34 states and 45 transitions. [2023-11-24 23:59:12,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:59:12,705 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-24 23:59:12,706 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:12,707 INFO L225 Difference]: With dead ends: 34 [2023-11-24 23:59:12,707 INFO L226 Difference]: Without dead ends: 20 [2023-11-24 23:59:12,707 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-24 23:59:12,709 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 3 mSDsluCounter, 12 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 25 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:59:12,710 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 25 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:59:12,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2023-11-24 23:59:12,715 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 17. [2023-11-24 23:59:12,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 13 states have internal predecessors, (16), 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-24 23:59:12,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2023-11-24 23:59:12,717 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 7 [2023-11-24 23:59:12,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:12,718 INFO L495 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2023-11-24 23:59:12,718 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-24 23:59:12,718 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2023-11-24 23:59:12,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2023-11-24 23:59:12,719 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:12,719 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:12,719 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-24 23:59:12,720 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:12,720 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:12,721 INFO L85 PathProgramCache]: Analyzing trace with hash -935372046, now seen corresponding path program 1 times [2023-11-24 23:59:12,721 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:12,721 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [489223477] [2023-11-24 23:59:12,721 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:12,722 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:12,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:12,796 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-24 23:59:12,796 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:12,797 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [489223477] [2023-11-24 23:59:12,797 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [489223477] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:59:12,797 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:59:12,797 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-24 23:59:12,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [684243151] [2023-11-24 23:59:12,798 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:59:12,799 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-24 23:59:12,799 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:12,800 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-24 23:59:12,800 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-24 23:59:12,800 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 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-24 23:59:12,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:12,822 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2023-11-24 23:59:12,823 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-24 23:59:12,823 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 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 8 [2023-11-24 23:59:12,823 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:12,824 INFO L225 Difference]: With dead ends: 34 [2023-11-24 23:59:12,824 INFO L226 Difference]: Without dead ends: 19 [2023-11-24 23:59:12,825 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-24 23:59:12,827 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 1 mSDsluCounter, 13 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 27 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-24 23:59:12,828 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 27 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:59:12,829 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2023-11-24 23:59:12,834 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 18. [2023-11-24 23:59:12,834 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 14 states have internal predecessors, (17), 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-24 23:59:12,835 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 22 transitions. [2023-11-24 23:59:12,836 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 22 transitions. Word has length 8 [2023-11-24 23:59:12,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:12,836 INFO L495 AbstractCegarLoop]: Abstraction has 18 states and 22 transitions. [2023-11-24 23:59:12,837 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 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-24 23:59:12,837 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 22 transitions. [2023-11-24 23:59:12,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-11-24 23:59:12,838 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:12,838 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:12,838 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-24 23:59:12,838 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:12,839 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:12,839 INFO L85 PathProgramCache]: Analyzing trace with hash -67368375, now seen corresponding path program 1 times [2023-11-24 23:59:12,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:12,840 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2105139171] [2023-11-24 23:59:12,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:12,840 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:12,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:13,022 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:59:13,022 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:13,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2105139171] [2023-11-24 23:59:13,023 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2105139171] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:59:13,023 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1826430520] [2023-11-24 23:59:13,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:13,024 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:13,024 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:59:13,060 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:59:13,080 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-24 23:59:13,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:13,145 INFO L262 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-24 23:59:13,150 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:59:13,190 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:59:13,191 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:59:13,254 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:59:13,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1826430520] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:59:13,255 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [804670661] [2023-11-24 23:59:13,275 INFO L159 IcfgInterpreter]: Started Sifa with 9 locations of interest [2023-11-24 23:59:13,275 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:59:13,279 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:59:13,285 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:59:13,286 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:59:13,598 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 17 for LOIs [2023-11-24 23:59:13,627 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:59:13,928 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '326#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_1| Int)) (and (<= 268435455 (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_1| 4294967296)) (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_1|) (= (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_1| 4) 0))) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-24 23:59:13,928 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:59:13,928 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:59:13,928 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 4] total 7 [2023-11-24 23:59:13,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [471294242] [2023-11-24 23:59:13,929 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:59:13,929 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-24 23:59:13,930 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:13,930 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-24 23:59:13,931 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=116, Unknown=0, NotChecked=0, Total=156 [2023-11-24 23:59:13,931 INFO L87 Difference]: Start difference. First operand 18 states and 22 transitions. Second operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 7 states have internal predecessors, (13), 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-24 23:59:13,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:13,992 INFO L93 Difference]: Finished difference Result 38 states and 49 transitions. [2023-11-24 23:59:13,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-24 23:59:13,992 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 7 states have internal predecessors, (13), 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 9 [2023-11-24 23:59:13,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:13,993 INFO L225 Difference]: With dead ends: 38 [2023-11-24 23:59:13,994 INFO L226 Difference]: Without dead ends: 22 [2023-11-24 23:59:13,995 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=48, Invalid=134, Unknown=0, NotChecked=0, Total=182 [2023-11-24 23:59:13,996 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 4 mSDsluCounter, 27 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:59:13,997 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:59:13,998 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2023-11-24 23:59:14,003 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2023-11-24 23:59:14,004 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 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-24 23:59:14,005 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 25 transitions. [2023-11-24 23:59:14,005 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 25 transitions. Word has length 9 [2023-11-24 23:59:14,005 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:14,005 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 25 transitions. [2023-11-24 23:59:14,006 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 7 states have internal predecessors, (13), 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-24 23:59:14,006 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 25 transitions. [2023-11-24 23:59:14,006 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2023-11-24 23:59:14,006 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:14,007 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:14,024 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-24 23:59:14,214 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:14,214 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:14,215 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:14,215 INFO L85 PathProgramCache]: Analyzing trace with hash 698087602, now seen corresponding path program 2 times [2023-11-24 23:59:14,215 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:14,215 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [39468630] [2023-11-24 23:59:14,215 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:14,216 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:14,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:14,345 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:59:14,345 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:14,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [39468630] [2023-11-24 23:59:14,346 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [39468630] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:59:14,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1230910914] [2023-11-24 23:59:14,346 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-24 23:59:14,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:14,347 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:59:14,348 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:59:14,353 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-24 23:59:14,437 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-24 23:59:14,438 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:59:14,439 INFO L262 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 10 conjunts are in the unsatisfiable core [2023-11-24 23:59:14,440 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:59:14,683 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-24 23:59:14,684 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-24 23:59:14,684 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1230910914] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:59:14,684 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-24 23:59:14,684 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2023-11-24 23:59:14,685 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2075931790] [2023-11-24 23:59:14,685 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:59:14,685 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-24 23:59:14,686 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:14,686 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-24 23:59:14,687 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2023-11-24 23:59:14,687 INFO L87 Difference]: Start difference. First operand 21 states and 25 transitions. Second operand has 6 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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-24 23:59:14,855 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:14,855 INFO L93 Difference]: Finished difference Result 28 states and 31 transitions. [2023-11-24 23:59:14,856 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-24 23:59:14,856 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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 12 [2023-11-24 23:59:14,856 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:14,857 INFO L225 Difference]: With dead ends: 28 [2023-11-24 23:59:14,857 INFO L226 Difference]: Without dead ends: 26 [2023-11-24 23:59:14,858 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2023-11-24 23:59:14,859 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 10 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:59:14,859 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 53 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:59:14,860 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2023-11-24 23:59:14,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 25. [2023-11-24 23:59:14,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 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-24 23:59:14,867 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2023-11-24 23:59:14,868 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 12 [2023-11-24 23:59:14,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:14,868 INFO L495 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2023-11-24 23:59:14,869 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 1.8) internal successors, (9), 5 states have internal predecessors, (9), 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-24 23:59:14,869 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2023-11-24 23:59:14,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-11-24 23:59:14,870 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:14,870 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:14,880 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-24 23:59:15,077 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:15,077 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:15,078 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:15,078 INFO L85 PathProgramCache]: Analyzing trace with hash -792997565, now seen corresponding path program 1 times [2023-11-24 23:59:15,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:15,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [124938356] [2023-11-24 23:59:15,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:15,078 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:15,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:15,258 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 3 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:59:15,259 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:15,259 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [124938356] [2023-11-24 23:59:15,259 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [124938356] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:59:15,259 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1950789114] [2023-11-24 23:59:15,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:15,260 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:15,260 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:59:15,265 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:59:15,268 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-24 23:59:15,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:15,314 INFO L262 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 10 conjunts are in the unsatisfiable core [2023-11-24 23:59:15,316 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:59:15,390 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 8 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-24 23:59:15,390 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:59:15,525 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-24 23:59:15,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1950789114] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:59:15,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [364857793] [2023-11-24 23:59:15,530 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-24 23:59:15,531 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:59:15,531 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:59:15,532 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:59:15,532 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:59:16,627 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 76 for LOIs [2023-11-24 23:59:17,028 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:59:18,342 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '680#(and (or (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_10| Int) (|v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_10| Int) (|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_11| Int)) (and (<= 1 |#StackHeapBarrier|) (= |v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_10| 0) (= (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12| 2) 0) (= |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_10| 0) (<= 1 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12|) (<= 268435455 (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_12| 4294967296)) (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_11|))) (exists ((|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_13| Int) (|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_12| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11| Int) (|v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_11| Int)) (and (<= 1 |#StackHeapBarrier|) (= (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_12| 4) 0) (= |v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_11| 0) (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_12|) (= |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_11| 0) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_13|)))) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-24 23:59:18,343 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:59:18,343 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:59:18,343 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6, 6] total 15 [2023-11-24 23:59:18,343 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [938888136] [2023-11-24 23:59:18,343 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:59:18,344 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-24 23:59:18,344 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:18,346 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-24 23:59:18,346 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=450, Unknown=0, NotChecked=0, Total=552 [2023-11-24 23:59:18,346 INFO L87 Difference]: Start difference. First operand 25 states and 28 transitions. Second operand has 15 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 15 states have internal predecessors, (32), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-24 23:59:19,093 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:19,093 INFO L93 Difference]: Finished difference Result 77 states and 96 transitions. [2023-11-24 23:59:19,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2023-11-24 23:59:19,094 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 15 states have internal predecessors, (32), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 19 [2023-11-24 23:59:19,094 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:19,095 INFO L225 Difference]: With dead ends: 77 [2023-11-24 23:59:19,096 INFO L226 Difference]: Without dead ends: 54 [2023-11-24 23:59:19,097 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 468 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=366, Invalid=1526, Unknown=0, NotChecked=0, Total=1892 [2023-11-24 23:59:19,098 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 26 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-24 23:59:19,099 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 128 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-24 23:59:19,100 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2023-11-24 23:59:19,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2023-11-24 23:59:19,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 44 states have (on average 1.1590909090909092) internal successors, (51), 45 states have internal predecessors, (51), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-24 23:59:19,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 62 transitions. [2023-11-24 23:59:19,124 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 62 transitions. Word has length 19 [2023-11-24 23:59:19,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:19,124 INFO L495 AbstractCegarLoop]: Abstraction has 53 states and 62 transitions. [2023-11-24 23:59:19,125 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 15 states have internal predecessors, (32), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-24 23:59:19,125 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 62 transitions. [2023-11-24 23:59:19,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2023-11-24 23:59:19,127 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:19,128 INFO L195 NwaCegarLoop]: trace histogram [20, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:19,139 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-24 23:59:19,333 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:19,334 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:19,334 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:19,335 INFO L85 PathProgramCache]: Analyzing trace with hash -126110543, now seen corresponding path program 2 times [2023-11-24 23:59:19,335 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:19,335 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [778001198] [2023-11-24 23:59:19,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:19,336 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:19,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:19,584 INFO L134 CoverageAnalysis]: Checked inductivity of 330 backedges. 120 proven. 15 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2023-11-24 23:59:19,585 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:19,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [778001198] [2023-11-24 23:59:19,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [778001198] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:59:19,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [890392518] [2023-11-24 23:59:19,586 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-24 23:59:19,586 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:19,586 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:59:19,587 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:59:19,612 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-24 23:59:19,915 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2023-11-24 23:59:19,915 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:59:19,918 INFO L262 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 14 conjunts are in the unsatisfiable core [2023-11-24 23:59:19,921 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:59:19,950 INFO L134 CoverageAnalysis]: Checked inductivity of 330 backedges. 136 proven. 15 refuted. 0 times theorem prover too weak. 179 trivial. 0 not checked. [2023-11-24 23:59:19,951 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:59:20,334 INFO L134 CoverageAnalysis]: Checked inductivity of 330 backedges. 126 proven. 15 refuted. 0 times theorem prover too weak. 189 trivial. 0 not checked. [2023-11-24 23:59:20,335 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [890392518] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:59:20,335 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [663567089] [2023-11-24 23:59:20,337 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-24 23:59:20,337 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:59:20,338 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:59:20,338 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:59:20,338 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:59:20,723 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 41 for LOIs [2023-11-24 23:59:20,860 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:59:21,712 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1314#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (or (exists ((|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_19| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_18| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_20| Int) (|v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_18| Int)) (and (= |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_18| 0) (<= 1 |#StackHeapBarrier|) (= |v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_18| 0) (= (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_20| 2) 0) (<= 268435455 (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_20| 4294967296)) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_20|) (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_19|))) (and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_20| Int)) (and (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_20|) (= (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_20| 4) 0) (<= 268435455 (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_20| 4294967296)))))))' at error location [2023-11-24 23:59:21,713 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:59:21,713 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:59:21,713 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 15 [2023-11-24 23:59:21,713 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [794242419] [2023-11-24 23:59:21,714 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:59:21,714 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-24 23:59:21,714 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:21,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-24 23:59:21,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=433, Unknown=0, NotChecked=0, Total=552 [2023-11-24 23:59:21,716 INFO L87 Difference]: Start difference. First operand 53 states and 62 transitions. Second operand has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:59:22,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:22,895 INFO L93 Difference]: Finished difference Result 133 states and 179 transitions. [2023-11-24 23:59:22,900 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2023-11-24 23:59:22,901 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 59 [2023-11-24 23:59:22,901 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:22,903 INFO L225 Difference]: With dead ends: 133 [2023-11-24 23:59:22,903 INFO L226 Difference]: Without dead ends: 82 [2023-11-24 23:59:22,905 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 163 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 189 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=216, Invalid=654, Unknown=0, NotChecked=0, Total=870 [2023-11-24 23:59:22,906 INFO L413 NwaCegarLoop]: 14 mSDtfsCounter, 25 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 74 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 92 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 74 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-24 23:59:22,906 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 85 Invalid, 92 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 74 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-24 23:59:22,907 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2023-11-24 23:59:22,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 81. [2023-11-24 23:59:22,940 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 72 states have (on average 1.0972222222222223) internal successors, (79), 73 states have internal predecessors, (79), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-24 23:59:22,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 90 transitions. [2023-11-24 23:59:22,942 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 90 transitions. Word has length 59 [2023-11-24 23:59:22,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:22,943 INFO L495 AbstractCegarLoop]: Abstraction has 81 states and 90 transitions. [2023-11-24 23:59:22,943 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 15 states have internal predecessors, (35), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:59:22,943 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 90 transitions. [2023-11-24 23:59:22,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2023-11-24 23:59:22,948 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:22,948 INFO L195 NwaCegarLoop]: trace histogram [48, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:22,963 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-11-24 23:59:23,155 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:23,156 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:23,156 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:23,157 INFO L85 PathProgramCache]: Analyzing trace with hash 1855814201, now seen corresponding path program 3 times [2023-11-24 23:59:23,157 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:23,157 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [306600826] [2023-11-24 23:59:23,157 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:23,157 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:23,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:23,758 INFO L134 CoverageAnalysis]: Checked inductivity of 1380 backedges. 519 proven. 78 refuted. 0 times theorem prover too weak. 783 trivial. 0 not checked. [2023-11-24 23:59:23,758 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:23,759 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [306600826] [2023-11-24 23:59:23,759 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [306600826] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:59:23,759 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1642054197] [2023-11-24 23:59:23,759 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-24 23:59:23,760 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:23,760 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:59:23,761 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:59:23,788 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-24 23:59:23,896 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-24 23:59:23,896 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:59:23,898 INFO L262 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-24 23:59:23,903 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:59:24,302 INFO L134 CoverageAnalysis]: Checked inductivity of 1380 backedges. 8 proven. 1086 refuted. 0 times theorem prover too weak. 286 trivial. 0 not checked. [2023-11-24 23:59:24,303 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:59:24,978 INFO L134 CoverageAnalysis]: Checked inductivity of 1380 backedges. 48 proven. 1046 refuted. 0 times theorem prover too weak. 286 trivial. 0 not checked. [2023-11-24 23:59:24,978 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1642054197] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:59:24,979 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1476435031] [2023-11-24 23:59:24,982 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-24 23:59:24,982 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:59:24,982 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:59:24,982 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:59:24,983 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:59:25,359 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 41 for LOIs [2023-11-24 23:59:25,496 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:59:26,778 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2274#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (or (and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_30| Int)) (and (= (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_30| 4) 0) (<= 268435455 (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_30| 4294967296)) (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_30|)))) (exists ((|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_28| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| Int) (|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_29| Int) (|v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_28| Int)) (and (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_29|) (<= 1 |#StackHeapBarrier|) (= |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_28| 0) (= (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| 2) 0) (= |v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_28| 0) (<= 1 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38|) (<= 268435455 (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_38| 4294967296))))))' at error location [2023-11-24 23:59:26,778 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:59:26,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:59:26,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 12, 12] total 35 [2023-11-24 23:59:26,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [616101122] [2023-11-24 23:59:26,779 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:59:26,780 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2023-11-24 23:59:26,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:26,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2023-11-24 23:59:26,782 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=243, Invalid=1649, Unknown=0, NotChecked=0, Total=1892 [2023-11-24 23:59:26,783 INFO L87 Difference]: Start difference. First operand 81 states and 90 transitions. Second operand has 35 states, 35 states have (on average 2.085714285714286) internal successors, (73), 35 states have internal predecessors, (73), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-24 23:59:38,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:59:38,671 INFO L93 Difference]: Finished difference Result 267 states and 313 transitions. [2023-11-24 23:59:38,672 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 146 states. [2023-11-24 23:59:38,672 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 35 states have (on average 2.085714285714286) internal successors, (73), 35 states have internal predecessors, (73), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 87 [2023-11-24 23:59:38,673 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:59:38,674 INFO L225 Difference]: With dead ends: 267 [2023-11-24 23:59:38,674 INFO L226 Difference]: Without dead ends: 188 [2023-11-24 23:59:38,690 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 408 GetRequests, 233 SyntacticMatches, 0 SemanticMatches, 175 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11195 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=3480, Invalid=27672, Unknown=0, NotChecked=0, Total=31152 [2023-11-24 23:59:38,691 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 99 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 1436 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 100 SdHoareTripleChecker+Valid, 296 SdHoareTripleChecker+Invalid, 1457 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 1436 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:59:38,691 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [100 Valid, 296 Invalid, 1457 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 1436 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2023-11-24 23:59:38,692 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2023-11-24 23:59:38,753 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 187. [2023-11-24 23:59:38,754 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 172 states have (on average 1.0755813953488371) internal successors, (185), 173 states have internal predecessors, (185), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-24 23:59:38,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 208 transitions. [2023-11-24 23:59:38,757 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 208 transitions. Word has length 87 [2023-11-24 23:59:38,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:59:38,757 INFO L495 AbstractCegarLoop]: Abstraction has 187 states and 208 transitions. [2023-11-24 23:59:38,758 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 2.085714285714286) internal successors, (73), 35 states have internal predecessors, (73), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-24 23:59:38,758 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 208 transitions. [2023-11-24 23:59:38,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 218 [2023-11-24 23:59:38,763 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:59:38,763 INFO L195 NwaCegarLoop]: trace histogram [130, 11, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1] [2023-11-24 23:59:38,775 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-11-24 23:59:38,970 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:38,970 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:59:38,971 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:59:38,971 INFO L85 PathProgramCache]: Analyzing trace with hash -1480745135, now seen corresponding path program 4 times [2023-11-24 23:59:38,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:59:38,971 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1488946934] [2023-11-24 23:59:38,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:59:38,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:59:39,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:40,036 INFO L134 CoverageAnalysis]: Checked inductivity of 10075 backedges. 1794 proven. 91 refuted. 0 times theorem prover too weak. 8190 trivial. 0 not checked. [2023-11-24 23:59:40,037 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:59:40,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1488946934] [2023-11-24 23:59:40,037 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1488946934] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:59:40,038 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1258231285] [2023-11-24 23:59:40,038 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-24 23:59:40,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:59:40,038 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:59:40,039 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:59:40,051 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_28e7bf20-23d7-4810-8592-dea2262d1e4c/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-24 23:59:40,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:59:40,237 INFO L262 TraceCheckSpWp]: Trace formula consists of 582 conjuncts, 46 conjunts are in the unsatisfiable core [2023-11-24 23:59:40,248 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:59:41,013 INFO L134 CoverageAnalysis]: Checked inductivity of 10075 backedges. 20 proven. 9053 refuted. 0 times theorem prover too weak. 1002 trivial. 0 not checked. [2023-11-24 23:59:41,013 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:59:42,713 INFO L134 CoverageAnalysis]: Checked inductivity of 10075 backedges. 53 proven. 9020 refuted. 0 times theorem prover too weak. 1002 trivial. 0 not checked. [2023-11-24 23:59:42,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1258231285] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:59:42,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1191629982] [2023-11-24 23:59:42,716 INFO L159 IcfgInterpreter]: Started Sifa with 13 locations of interest [2023-11-24 23:59:42,716 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:59:42,717 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:59:42,717 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:59:42,717 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:59:43,042 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 41 for LOIs [2023-11-24 23:59:43,135 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:59:44,801 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4760#(and (or (exists ((|v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_38| Int) (|v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| Int) (|v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_38| Int) (|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_39| Int)) (and (<= 1 |#StackHeapBarrier|) (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_39|) (<= 268435455 (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| 4294967296)) (= |v_ULTIMATE.start_main_~x~0#1_BEFORE_CALL_38| 0) (= (mod |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68| 2) 0) (<= 0 |v_ULTIMATE.start_main_~y~0#1_BEFORE_CALL_68|) (= |v_ULTIMATE.start_main_~w~0#1_BEFORE_CALL_38| 0))) (and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_40| Int)) (and (= (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_40| 4) 0) (<= 0 |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_40|) (<= 268435455 (mod |v_ULTIMATE.start_main_~z~0#1_BEFORE_CALL_40| 4294967296)))))) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-11-24 23:59:44,801 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:59:44,802 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-24 23:59:44,802 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 24, 24] total 60 [2023-11-24 23:59:44,802 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [700613122] [2023-11-24 23:59:44,803 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-24 23:59:44,804 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 60 states [2023-11-24 23:59:44,805 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:59:44,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2023-11-24 23:59:44,811 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=714, Invalid=3978, Unknown=0, NotChecked=0, Total=4692 [2023-11-24 23:59:44,812 INFO L87 Difference]: Start difference. First operand 187 states and 208 transitions. Second operand has 60 states, 60 states have (on average 2.2333333333333334) internal successors, (134), 60 states have internal predecessors, (134), 21 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21)