./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/array-patterns/array6_pattern.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 0e0057cc Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/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_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/config/TaipanReach.xml -i ../../sv-benchmarks/c/array-patterns/array6_pattern.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/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_47445840-c568-420d-bc16-c001d7cd5e9b/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 81db346fb66b40514998cf838e858b3f0793fe5c74d5812efa60193ab54d6833 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-0e0057c [2023-11-24 23:52:58,580 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-24 23:52:58,686 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-24 23:52:58,692 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-24 23:52:58,693 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-24 23:52:58,746 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-24 23:52:58,747 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-24 23:52:58,748 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-24 23:52:58,749 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-24 23:52:58,750 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-24 23:52:58,751 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-24 23:52:58,751 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-24 23:52:58,752 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-24 23:52:58,759 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-24 23:52:58,759 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-24 23:52:58,761 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-24 23:52:58,762 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-24 23:52:58,762 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-24 23:52:58,763 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-24 23:52:58,764 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-24 23:52:58,764 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-24 23:52:58,765 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-24 23:52:58,766 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-24 23:52:58,767 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-24 23:52:58,767 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-24 23:52:58,768 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-24 23:52:58,768 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-24 23:52:58,769 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-24 23:52:58,769 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-24 23:52:58,770 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-24 23:52:58,771 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-24 23:52:58,772 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-24 23:52:58,772 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-24 23:52:58,772 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-24 23:52:58,773 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-24 23:52:58,773 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-24 23:52:58,774 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-24 23:52:58,774 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:52:58,775 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-24 23:52:58,775 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-24 23:52:58,775 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-24 23:52:58,776 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-24 23:52:58,776 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-24 23:52:58,777 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-24 23:52:58,777 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-24 23:52:58,777 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-24 23:52:58,778 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-24 23:52:58,778 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_47445840-c568-420d-bc16-c001d7cd5e9b/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_47445840-c568-420d-bc16-c001d7cd5e9b/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 -> 81db346fb66b40514998cf838e858b3f0793fe5c74d5812efa60193ab54d6833 [2023-11-24 23:52:59,099 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-24 23:52:59,136 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-24 23:52:59,139 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-24 23:52:59,142 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-24 23:52:59,143 INFO L274 PluginConnector]: CDTParser initialized [2023-11-24 23:52:59,144 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/../../sv-benchmarks/c/array-patterns/array6_pattern.c [2023-11-24 23:53:02,745 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-24 23:53:03,068 INFO L384 CDTParser]: Found 1 translation units. [2023-11-24 23:53:03,069 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/sv-benchmarks/c/array-patterns/array6_pattern.c [2023-11-24 23:53:03,079 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/data/4be5d6e27/a5a13180ea7a43e48836528820b7a491/FLAG6fd031442 [2023-11-24 23:53:03,096 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/data/4be5d6e27/a5a13180ea7a43e48836528820b7a491 [2023-11-24 23:53:03,099 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-24 23:53:03,102 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-24 23:53:03,105 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-24 23:53:03,105 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-24 23:53:03,112 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-24 23:53:03,115 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,117 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2007d086 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03, skipping insertion in model container [2023-11-24 23:53:03,117 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,146 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-24 23:53:03,347 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_47445840-c568-420d-bc16-c001d7cd5e9b/sv-benchmarks/c/array-patterns/array6_pattern.c[1356,1369] [2023-11-24 23:53:03,379 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:53:03,392 INFO L202 MainTranslator]: Completed pre-run [2023-11-24 23:53:03,406 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_47445840-c568-420d-bc16-c001d7cd5e9b/sv-benchmarks/c/array-patterns/array6_pattern.c[1356,1369] [2023-11-24 23:53:03,420 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-24 23:53:03,440 INFO L206 MainTranslator]: Completed translation [2023-11-24 23:53:03,441 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03 WrapperNode [2023-11-24 23:53:03,441 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-24 23:53:03,443 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-24 23:53:03,443 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-24 23:53:03,443 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-24 23:53:03,453 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:53:03" (1/1) ... [2023-11-24 23:53:03,483 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:53:03" (1/1) ... [2023-11-24 23:53:03,526 INFO L138 Inliner]: procedures = 16, calls = 26, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 86 [2023-11-24 23:53:03,526 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-24 23:53:03,527 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-24 23:53:03,528 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-24 23:53:03,528 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-24 23:53:03,540 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,540 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,546 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,547 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,567 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,571 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,573 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,574 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,587 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-24 23:53:03,588 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-24 23:53:03,588 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-24 23:53:03,588 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-24 23:53:03,589 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (1/1) ... [2023-11-24 23:53:03,605 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-24 23:53:03,620 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:03,639 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/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:53:03,663 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/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:53:03,692 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-24 23:53:03,693 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-24 23:53:03,693 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-24 23:53:03,693 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-24 23:53:03,694 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-11-24 23:53:03,694 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-11-24 23:53:03,694 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-24 23:53:03,695 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-24 23:53:03,695 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-11-24 23:53:03,695 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-24 23:53:03,791 INFO L241 CfgBuilder]: Building ICFG [2023-11-24 23:53:03,794 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-24 23:53:03,995 INFO L282 CfgBuilder]: Performing block encoding [2023-11-24 23:53:04,053 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-24 23:53:04,054 INFO L309 CfgBuilder]: Removed 3 assume(true) statements. [2023-11-24 23:53:04,056 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:53:04 BoogieIcfgContainer [2023-11-24 23:53:04,056 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-24 23:53:04,060 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-24 23:53:04,061 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-24 23:53:04,065 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-24 23:53:04,066 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 24.11 11:53:03" (1/3) ... [2023-11-24 23:53:04,067 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@772251ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:53:04, skipping insertion in model container [2023-11-24 23:53:04,067 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 24.11 11:53:03" (2/3) ... [2023-11-24 23:53:04,068 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@772251ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.11 11:53:04, skipping insertion in model container [2023-11-24 23:53:04,068 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.11 11:53:04" (3/3) ... [2023-11-24 23:53:04,070 INFO L112 eAbstractionObserver]: Analyzing ICFG array6_pattern.c [2023-11-24 23:53:04,096 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-24 23:53:04,096 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-24 23:53:04,156 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-24 23:53:04,166 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;@4311f307, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-24 23:53:04,166 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-24 23:53:04,172 INFO L276 IsEmpty]: Start isEmpty. Operand has 17 states, 12 states have (on average 1.5) internal successors, (18), 13 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:04,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-11-24 23:53:04,180 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:04,181 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:04,181 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:04,187 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:04,187 INFO L85 PathProgramCache]: Analyzing trace with hash -1640465240, now seen corresponding path program 1 times [2023-11-24 23:53:04,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:04,200 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1537829276] [2023-11-24 23:53:04,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:04,201 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:04,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:53:04,535 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:53:04,536 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:04,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1537829276] [2023-11-24 23:53:04,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1537829276] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:53:04,537 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:53:04,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-24 23:53:04,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1667748311] [2023-11-24 23:53:04,541 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:53:04,547 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-24 23:53:04,549 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:04,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-24 23:53:04,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-24 23:53:04,603 INFO L87 Difference]: Start difference. First operand has 17 states, 12 states have (on average 1.5) internal successors, (18), 13 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-24 23:53:04,646 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:04,646 INFO L93 Difference]: Finished difference Result 24 states and 30 transitions. [2023-11-24 23:53:04,648 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-24 23:53:04,650 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2023-11-24 23:53:04,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:04,658 INFO L225 Difference]: With dead ends: 24 [2023-11-24 23:53:04,658 INFO L226 Difference]: Without dead ends: 15 [2023-11-24 23:53:04,661 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-24 23:53:04,666 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 13 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:04,667 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 13 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:53:04,687 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2023-11-24 23:53:04,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2023-11-24 23:53:04,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 11 states have internal predecessors, (14), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:04,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2023-11-24 23:53:04,708 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 18 transitions. Word has length 11 [2023-11-24 23:53:04,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:04,710 INFO L495 AbstractCegarLoop]: Abstraction has 15 states and 18 transitions. [2023-11-24 23:53:04,711 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.5) internal successors, (9), 2 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-11-24 23:53:04,711 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 18 transitions. [2023-11-24 23:53:04,712 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2023-11-24 23:53:04,712 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:04,713 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:04,713 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-24 23:53:04,714 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:04,714 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:04,715 INFO L85 PathProgramCache]: Analyzing trace with hash -1148567133, now seen corresponding path program 1 times [2023-11-24 23:53:04,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:04,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [166658936] [2023-11-24 23:53:04,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:04,716 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:04,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:53:05,064 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-24 23:53:05,064 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:05,065 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [166658936] [2023-11-24 23:53:05,065 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [166658936] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:53:05,065 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:53:05,066 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-24 23:53:05,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1577260496] [2023-11-24 23:53:05,066 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:53:05,068 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-24 23:53:05,068 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:05,069 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-24 23:53:05,070 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-24 23:53:05,070 INFO L87 Difference]: Start difference. First operand 15 states and 18 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:05,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:05,125 INFO L93 Difference]: Finished difference Result 19 states and 22 transitions. [2023-11-24 23:53:05,126 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-24 23:53:05,126 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2023-11-24 23:53:05,127 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:05,127 INFO L225 Difference]: With dead ends: 19 [2023-11-24 23:53:05,128 INFO L226 Difference]: Without dead ends: 16 [2023-11-24 23:53:05,128 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-24 23:53:05,130 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 3 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 28 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:05,131 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 28 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-24 23:53:05,133 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2023-11-24 23:53:05,137 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2023-11-24 23:53:05,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:05,139 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 19 transitions. [2023-11-24 23:53:05,139 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 19 transitions. Word has length 16 [2023-11-24 23:53:05,140 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:05,140 INFO L495 AbstractCegarLoop]: Abstraction has 16 states and 19 transitions. [2023-11-24 23:53:05,140 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:05,141 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 19 transitions. [2023-11-24 23:53:05,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-11-24 23:53:05,142 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:05,142 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:05,142 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-24 23:53:05,143 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:05,144 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:05,144 INFO L85 PathProgramCache]: Analyzing trace with hash -1246048416, now seen corresponding path program 1 times [2023-11-24 23:53:05,144 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:05,145 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1329569275] [2023-11-24 23:53:05,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:05,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:05,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:53:05,395 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-24 23:53:05,396 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:05,397 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1329569275] [2023-11-24 23:53:05,398 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1329569275] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-24 23:53:05,398 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-24 23:53:05,399 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-24 23:53:05,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1115567010] [2023-11-24 23:53:05,399 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-24 23:53:05,400 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-24 23:53:05,400 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:05,401 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-24 23:53:05,401 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-24 23:53:05,401 INFO L87 Difference]: Start difference. First operand 16 states and 19 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:05,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:05,498 INFO L93 Difference]: Finished difference Result 29 states and 34 transitions. [2023-11-24 23:53:05,501 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-24 23:53:05,501 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2023-11-24 23:53:05,502 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:05,502 INFO L225 Difference]: With dead ends: 29 [2023-11-24 23:53:05,503 INFO L226 Difference]: Without dead ends: 17 [2023-11-24 23:53:05,503 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2023-11-24 23:53:05,505 INFO L413 NwaCegarLoop]: 11 mSDtfsCounter, 11 mSDsluCounter, 18 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 29 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:05,506 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 29 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:53:05,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2023-11-24 23:53:05,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2023-11-24 23:53:05,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:05,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 20 transitions. [2023-11-24 23:53:05,513 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 20 transitions. Word has length 17 [2023-11-24 23:53:05,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:05,514 INFO L495 AbstractCegarLoop]: Abstraction has 17 states and 20 transitions. [2023-11-24 23:53:05,514 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:05,519 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 20 transitions. [2023-11-24 23:53:05,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2023-11-24 23:53:05,520 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:05,521 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:05,521 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-24 23:53:05,522 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:05,529 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:05,529 INFO L85 PathProgramCache]: Analyzing trace with hash 1748235468, now seen corresponding path program 1 times [2023-11-24 23:53:05,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:05,530 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [396006726] [2023-11-24 23:53:05,530 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:05,530 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:05,578 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:05,588 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [451214097] [2023-11-24 23:53:05,588 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:05,589 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:05,589 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:05,594 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:05,609 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-24 23:53:05,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:53:05,718 INFO L262 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-24 23:53:05,727 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:05,866 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-24 23:53:05,867 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:53:06,045 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-24 23:53:06,045 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:06,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [396006726] [2023-11-24 23:53:06,046 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:53:06,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [451214097] [2023-11-24 23:53:06,047 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [451214097] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:53:06,047 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [801382125] [2023-11-24 23:53:06,073 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-24 23:53:06,073 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:53:06,077 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:53:06,084 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:53:06,085 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:53:07,418 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-24 23:53:07,422 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:53:08,580 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '312#(and (= |ULTIMATE.start_main_~temp~0#1| 0) (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~#array2~0#1.offset| 0) (<= 3 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |ULTIMATE.start_main_~count~0#1|) (<= 2 |ULTIMATE.start_main_~#array1~0#1.base|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (not (= |ULTIMATE.start_main_~sum~0#1| 0)) (<= 2 |ULTIMATE.start_main_~#array2~0#1.base|) (= (+ |ULTIMATE.start_main_~num~0#1| 1) 0) (= |ULTIMATE.start_main_~#array1~0#1.offset| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~index~0#1| 32765) (<= ~ARR_SIZE~0 32767) (<= 1 |ULTIMATE.start_main_~index~0#1|))' at error location [2023-11-24 23:53:08,580 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:53:08,580 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-24 23:53:08,580 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2023-11-24 23:53:08,581 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [433065788] [2023-11-24 23:53:08,581 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-24 23:53:08,582 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-11-24 23:53:08,582 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:08,583 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-11-24 23:53:08,584 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=353, Unknown=0, NotChecked=0, Total=420 [2023-11-24 23:53:08,585 INFO L87 Difference]: Start difference. First operand 17 states and 20 transitions. Second operand has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 9 states have internal predecessors, (19), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-24 23:53:08,840 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:08,841 INFO L93 Difference]: Finished difference Result 49 states and 56 transitions. [2023-11-24 23:53:08,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-11-24 23:53:08,842 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 9 states have internal predecessors, (19), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 18 [2023-11-24 23:53:08,842 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:08,847 INFO L225 Difference]: With dead ends: 49 [2023-11-24 23:53:08,847 INFO L226 Difference]: Without dead ends: 29 [2023-11-24 23:53:08,849 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 32 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 194 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=123, Invalid=689, Unknown=0, NotChecked=0, Total=812 [2023-11-24 23:53:08,853 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 35 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 69 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 69 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:08,856 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 46 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 69 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:53:08,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2023-11-24 23:53:08,869 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 19. [2023-11-24 23:53:08,869 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:08,870 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 22 transitions. [2023-11-24 23:53:08,871 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 22 transitions. Word has length 18 [2023-11-24 23:53:08,871 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:08,871 INFO L495 AbstractCegarLoop]: Abstraction has 19 states and 22 transitions. [2023-11-24 23:53:08,872 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 9 states have internal predecessors, (19), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-24 23:53:08,872 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 22 transitions. [2023-11-24 23:53:08,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2023-11-24 23:53:08,873 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:08,873 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:08,883 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-11-24 23:53:09,080 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:09,080 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:09,081 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:09,081 INFO L85 PathProgramCache]: Analyzing trace with hash -39520436, now seen corresponding path program 2 times [2023-11-24 23:53:09,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:09,081 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [450586390] [2023-11-24 23:53:09,081 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:09,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:09,117 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:09,122 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1506301026] [2023-11-24 23:53:09,122 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-24 23:53:09,122 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:09,123 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:09,124 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:09,146 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-24 23:53:09,223 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-11-24 23:53:09,223 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:53:09,225 INFO L262 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 8 conjunts are in the unsatisfiable core [2023-11-24 23:53:09,227 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:09,280 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-24 23:53:09,280 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:53:09,381 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-24 23:53:09,381 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:09,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [450586390] [2023-11-24 23:53:09,382 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:53:09,382 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1506301026] [2023-11-24 23:53:09,382 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1506301026] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:53:09,384 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1902252594] [2023-11-24 23:53:09,389 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-24 23:53:09,390 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:53:09,390 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:53:09,390 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:53:09,391 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:53:10,119 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-24 23:53:10,121 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:53:11,140 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '567#(and (= |ULTIMATE.start_main_~temp~0#1| 0) (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~#array2~0#1.offset| 0) (<= 3 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |ULTIMATE.start_main_~count~0#1|) (<= 2 |ULTIMATE.start_main_~#array1~0#1.base|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (not (= |ULTIMATE.start_main_~sum~0#1| 0)) (<= 2 |ULTIMATE.start_main_~#array2~0#1.base|) (= (+ |ULTIMATE.start_main_~num~0#1| 1) 0) (= |ULTIMATE.start_main_~#array1~0#1.offset| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~index~0#1| 32765) (<= ~ARR_SIZE~0 32767) (<= 1 |ULTIMATE.start_main_~index~0#1|))' at error location [2023-11-24 23:53:11,140 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:53:11,141 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-24 23:53:11,141 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-11-24 23:53:11,141 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1088560199] [2023-11-24 23:53:11,142 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-24 23:53:11,142 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-24 23:53:11,142 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:11,143 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-24 23:53:11,144 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=371, Unknown=0, NotChecked=0, Total=462 [2023-11-24 23:53:11,144 INFO L87 Difference]: Start difference. First operand 19 states and 22 transitions. Second operand has 10 states, 8 states have (on average 2.5) internal successors, (20), 10 states have internal predecessors, (20), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-24 23:53:11,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:11,246 INFO L93 Difference]: Finished difference Result 28 states and 32 transitions. [2023-11-24 23:53:11,246 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-11-24 23:53:11,247 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 10 states have internal predecessors, (20), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) Word has length 20 [2023-11-24 23:53:11,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:11,248 INFO L225 Difference]: With dead ends: 28 [2023-11-24 23:53:11,248 INFO L226 Difference]: Without dead ends: 25 [2023-11-24 23:53:11,249 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 165 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=105, Invalid=447, Unknown=0, NotChecked=0, Total=552 [2023-11-24 23:53:11,250 INFO L413 NwaCegarLoop]: 12 mSDtfsCounter, 27 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:11,250 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 34 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:53:11,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2023-11-24 23:53:11,257 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2023-11-24 23:53:11,258 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-24 23:53:11,259 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2023-11-24 23:53:11,259 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 20 [2023-11-24 23:53:11,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:11,260 INFO L495 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2023-11-24 23:53:11,260 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.5) internal successors, (20), 10 states have internal predecessors, (20), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 3 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-24 23:53:11,260 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2023-11-24 23:53:11,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2023-11-24 23:53:11,261 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:11,262 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:11,272 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-24 23:53:11,472 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:11,472 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:11,473 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:11,473 INFO L85 PathProgramCache]: Analyzing trace with hash 668985516, now seen corresponding path program 3 times [2023-11-24 23:53:11,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:11,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1465827132] [2023-11-24 23:53:11,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:11,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:11,500 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:11,511 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1001694857] [2023-11-24 23:53:11,511 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-24 23:53:11,511 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:11,511 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:11,513 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:11,538 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-24 23:53:11,680 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-24 23:53:11,681 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:53:11,684 WARN L260 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 69 conjunts are in the unsatisfiable core [2023-11-24 23:53:11,692 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:11,747 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2023-11-24 23:53:11,813 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 15 [2023-11-24 23:53:11,893 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 37 [2023-11-24 23:53:12,026 INFO L349 Elim1Store]: treesize reduction 35, result has 16.7 percent of original size [2023-11-24 23:53:12,026 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 7 case distinctions, treesize of input 58 treesize of output 59 [2023-11-24 23:53:12,778 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:12,784 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:12,787 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-24 23:53:12,793 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-24 23:53:12,798 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-24 23:53:13,020 INFO L349 Elim1Store]: treesize reduction 385, result has 7.7 percent of original size [2023-11-24 23:53:13,021 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 16 select indices, 16 select index equivalence classes, 3 disjoint index pairs (out of 120 index pairs), introduced 16 new quantified variables, introduced 124 case distinctions, treesize of input 180 treesize of output 196 [2023-11-24 23:53:14,001 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:53:14,002 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:53:14,869 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:14,869 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1465827132] [2023-11-24 23:53:14,870 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:53:14,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1001694857] [2023-11-24 23:53:14,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1001694857] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:53:14,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1460781965] [2023-11-24 23:53:14,873 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-24 23:53:14,873 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:53:14,874 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:53:14,874 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:53:14,874 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:53:15,400 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-24 23:53:15,401 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:53:17,122 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '784#(and (= |ULTIMATE.start_main_~temp~0#1| 0) (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~#array2~0#1.offset| 0) (<= 3 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |ULTIMATE.start_main_~count~0#1|) (<= 2 |ULTIMATE.start_main_~#array1~0#1.base|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (not (= |ULTIMATE.start_main_~sum~0#1| 0)) (<= 2 |ULTIMATE.start_main_~#array2~0#1.base|) (= (+ |ULTIMATE.start_main_~num~0#1| 1) 0) (= |ULTIMATE.start_main_~#array1~0#1.offset| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~index~0#1| 32765) (<= ~ARR_SIZE~0 32767) (<= 1 |ULTIMATE.start_main_~index~0#1|))' at error location [2023-11-24 23:53:17,122 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:53:17,122 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-24 23:53:17,122 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2023-11-24 23:53:17,123 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [275406503] [2023-11-24 23:53:17,123 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-24 23:53:17,123 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-24 23:53:17,123 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:17,124 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-24 23:53:17,125 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=1164, Unknown=0, NotChecked=0, Total=1332 [2023-11-24 23:53:17,126 INFO L87 Difference]: Start difference. First operand 25 states and 28 transitions. Second operand has 18 states, 16 states have (on average 1.125) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:18,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:18,183 INFO L93 Difference]: Finished difference Result 45 states and 50 transitions. [2023-11-24 23:53:18,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-24 23:53:18,184 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 16 states have (on average 1.125) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 22 [2023-11-24 23:53:18,184 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:18,186 INFO L225 Difference]: With dead ends: 45 [2023-11-24 23:53:18,186 INFO L226 Difference]: Without dead ends: 42 [2023-11-24 23:53:18,190 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 467 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=226, Invalid=1496, Unknown=0, NotChecked=0, Total=1722 [2023-11-24 23:53:18,191 INFO L413 NwaCegarLoop]: 10 mSDtfsCounter, 31 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 228 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 73 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 228 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:18,192 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 73 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 228 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-24 23:53:18,194 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2023-11-24 23:53:18,219 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 32. [2023-11-24 23:53:18,223 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 25 states have (on average 1.2) internal successors, (30), 25 states have internal predecessors, (30), 3 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2023-11-24 23:53:18,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 36 transitions. [2023-11-24 23:53:18,225 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 36 transitions. Word has length 22 [2023-11-24 23:53:18,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:18,225 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 36 transitions. [2023-11-24 23:53:18,225 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 16 states have (on average 1.125) internal successors, (18), 15 states have internal predecessors, (18), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:18,226 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 36 transitions. [2023-11-24 23:53:18,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-11-24 23:53:18,228 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:18,228 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:18,238 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-11-24 23:53:18,435 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2023-11-24 23:53:18,435 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:18,436 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:18,436 INFO L85 PathProgramCache]: Analyzing trace with hash -190757184, now seen corresponding path program 4 times [2023-11-24 23:53:18,436 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:18,436 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1826563874] [2023-11-24 23:53:18,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:18,437 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:18,474 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:18,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [472679091] [2023-11-24 23:53:18,476 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-24 23:53:18,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:18,476 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:18,478 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:18,488 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-24 23:53:18,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:53:18,587 INFO L262 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 10 conjunts are in the unsatisfiable core [2023-11-24 23:53:18,593 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:18,716 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:53:18,717 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:53:18,847 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-24 23:53:18,847 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:18,847 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1826563874] [2023-11-24 23:53:18,847 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:53:18,848 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [472679091] [2023-11-24 23:53:18,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [472679091] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:53:18,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [371644003] [2023-11-24 23:53:18,854 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-24 23:53:18,855 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:53:18,855 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:53:18,855 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:53:18,856 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:53:19,305 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-24 23:53:19,307 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:53:20,234 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1074#(and (= |ULTIMATE.start_main_~temp~0#1| 0) (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~#array2~0#1.offset| 0) (<= 3 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |ULTIMATE.start_main_~count~0#1|) (<= 2 |ULTIMATE.start_main_~#array1~0#1.base|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (not (= |ULTIMATE.start_main_~sum~0#1| 0)) (<= 2 |ULTIMATE.start_main_~#array2~0#1.base|) (= (+ |ULTIMATE.start_main_~num~0#1| 1) 0) (= |ULTIMATE.start_main_~#array1~0#1.offset| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~index~0#1| 32765) (<= ~ARR_SIZE~0 32767) (<= 1 |ULTIMATE.start_main_~index~0#1|))' at error location [2023-11-24 23:53:20,235 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:53:20,235 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-24 23:53:20,235 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 15 [2023-11-24 23:53:20,235 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1611872410] [2023-11-24 23:53:20,236 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-24 23:53:20,236 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-24 23:53:20,236 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:20,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-24 23:53:20,238 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=579, Unknown=0, NotChecked=0, Total=702 [2023-11-24 23:53:20,238 INFO L87 Difference]: Start difference. First operand 32 states and 36 transitions. Second operand has 15 states, 15 states have (on average 1.6) internal successors, (24), 15 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:53:20,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:20,476 INFO L93 Difference]: Finished difference Result 53 states and 58 transitions. [2023-11-24 23:53:20,477 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-24 23:53:20,477 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.6) internal successors, (24), 15 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2023-11-24 23:53:20,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:20,481 INFO L225 Difference]: With dead ends: 53 [2023-11-24 23:53:20,481 INFO L226 Difference]: Without dead ends: 50 [2023-11-24 23:53:20,482 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 37 SyntacticMatches, 5 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=173, Invalid=819, Unknown=0, NotChecked=0, Total=992 [2023-11-24 23:53:20,483 INFO L413 NwaCegarLoop]: 18 mSDtfsCounter, 15 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 135 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 140 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 135 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:20,483 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 69 Invalid, 140 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:53:20,484 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2023-11-24 23:53:20,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 38. [2023-11-24 23:53:20,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 29 states have (on average 1.206896551724138) internal successors, (35), 29 states have internal predecessors, (35), 4 states have call successors, (4), 4 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-24 23:53:20,504 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 43 transitions. [2023-11-24 23:53:20,504 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 43 transitions. Word has length 23 [2023-11-24 23:53:20,505 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:20,505 INFO L495 AbstractCegarLoop]: Abstraction has 38 states and 43 transitions. [2023-11-24 23:53:20,505 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.6) internal successors, (24), 15 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:53:20,505 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 43 transitions. [2023-11-24 23:53:20,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-11-24 23:53:20,507 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:20,507 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:20,522 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-24 23:53:20,718 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:20,719 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:20,719 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:20,719 INFO L85 PathProgramCache]: Analyzing trace with hash -736491145, now seen corresponding path program 5 times [2023-11-24 23:53:20,719 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:20,720 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [644448890] [2023-11-24 23:53:20,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:20,720 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:20,747 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:20,747 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1364215667] [2023-11-24 23:53:20,748 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-24 23:53:20,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:20,748 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:20,749 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:20,770 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-24 23:53:20,915 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2023-11-24 23:53:20,916 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:53:20,918 INFO L262 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 10 conjunts are in the unsatisfiable core [2023-11-24 23:53:20,920 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:21,046 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:53:21,046 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:53:21,153 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-24 23:53:21,154 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:21,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [644448890] [2023-11-24 23:53:21,154 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:53:21,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1364215667] [2023-11-24 23:53:21,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1364215667] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:53:21,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [85607152] [2023-11-24 23:53:21,157 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-24 23:53:21,157 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:53:21,158 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:53:21,158 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:53:21,158 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:53:21,632 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-24 23:53:21,633 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:53:22,640 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1384#(and (= |ULTIMATE.start_main_~temp~0#1| 0) (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~#array2~0#1.offset| 0) (<= 3 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |ULTIMATE.start_main_~count~0#1|) (<= 2 |ULTIMATE.start_main_~#array1~0#1.base|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (not (= |ULTIMATE.start_main_~sum~0#1| 0)) (<= 2 |ULTIMATE.start_main_~#array2~0#1.base|) (= (+ |ULTIMATE.start_main_~num~0#1| 1) 0) (= |ULTIMATE.start_main_~#array1~0#1.offset| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~index~0#1| 32765) (<= ~ARR_SIZE~0 32767) (<= 1 |ULTIMATE.start_main_~index~0#1|))' at error location [2023-11-24 23:53:22,640 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:53:22,641 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-24 23:53:22,641 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 15 [2023-11-24 23:53:22,641 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [614303616] [2023-11-24 23:53:22,641 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-24 23:53:22,642 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2023-11-24 23:53:22,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:22,643 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2023-11-24 23:53:22,644 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=589, Unknown=0, NotChecked=0, Total=702 [2023-11-24 23:53:22,644 INFO L87 Difference]: Start difference. First operand 38 states and 43 transitions. Second operand has 15 states, 15 states have (on average 1.6) internal successors, (24), 15 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:53:22,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:22,841 INFO L93 Difference]: Finished difference Result 54 states and 59 transitions. [2023-11-24 23:53:22,842 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-24 23:53:22,842 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.6) internal successors, (24), 15 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2023-11-24 23:53:22,843 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:22,844 INFO L225 Difference]: With dead ends: 54 [2023-11-24 23:53:22,844 INFO L226 Difference]: Without dead ends: 45 [2023-11-24 23:53:22,845 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 37 SyntacticMatches, 5 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 292 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=164, Invalid=828, Unknown=0, NotChecked=0, Total=992 [2023-11-24 23:53:22,846 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 38 mSDsluCounter, 37 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 50 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:22,846 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 50 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-24 23:53:22,847 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2023-11-24 23:53:22,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 42. [2023-11-24 23:53:22,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 33 states have internal predecessors, (38), 4 states have call successors, (4), 4 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-24 23:53:22,867 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 46 transitions. [2023-11-24 23:53:22,868 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 46 transitions. Word has length 23 [2023-11-24 23:53:22,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:22,868 INFO L495 AbstractCegarLoop]: Abstraction has 42 states and 46 transitions. [2023-11-24 23:53:22,869 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.6) internal successors, (24), 15 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:53:22,869 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 46 transitions. [2023-11-24 23:53:22,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-11-24 23:53:22,870 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:22,870 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:22,882 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2023-11-24 23:53:23,077 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-11-24 23:53:23,077 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:23,078 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:23,078 INFO L85 PathProgramCache]: Analyzing trace with hash -1618711069, now seen corresponding path program 6 times [2023-11-24 23:53:23,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:23,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1638647754] [2023-11-24 23:53:23,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:23,078 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:23,100 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:23,101 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [309438832] [2023-11-24 23:53:23,101 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-11-24 23:53:23,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:23,101 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:23,103 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:23,107 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-24 23:53:23,420 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-11-24 23:53:23,420 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:53:23,424 WARN L260 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 84 conjunts are in the unsatisfiable core [2023-11-24 23:53:23,432 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:23,457 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2023-11-24 23:53:23,513 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 15 [2023-11-24 23:53:23,578 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 37 [2023-11-24 23:53:23,689 INFO L349 Elim1Store]: treesize reduction 35, result has 16.7 percent of original size [2023-11-24 23:53:23,690 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 7 case distinctions, treesize of input 58 treesize of output 59 [2023-11-24 23:53:23,830 INFO L349 Elim1Store]: treesize reduction 43, result has 14.0 percent of original size [2023-11-24 23:53:23,831 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 7 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 16 case distinctions, treesize of input 74 treesize of output 81 [2023-11-24 23:53:24,587 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:24,591 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:24,598 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:24,613 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:24,618 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:24,622 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:25,334 INFO L349 Elim1Store]: treesize reduction 939, result has 8.8 percent of original size [2023-11-24 23:53:25,335 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 20 select indices, 20 select index equivalence classes, 15 disjoint index pairs (out of 190 index pairs), introduced 20 new quantified variables, introduced 199 case distinctions, treesize of input 212 treesize of output 262 [2023-11-24 23:53:27,588 INFO L349 Elim1Store]: treesize reduction 344, result has 36.9 percent of original size [2023-11-24 23:53:27,589 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 14 select indices, 14 select index equivalence classes, 6 disjoint index pairs (out of 91 index pairs), introduced 14 new quantified variables, introduced 91 case distinctions, treesize of input 169 treesize of output 269 [2023-11-24 23:53:29,179 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:53:29,180 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:53:30,115 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:30,115 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1638647754] [2023-11-24 23:53:30,115 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:53:30,115 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [309438832] [2023-11-24 23:53:30,115 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [309438832] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-24 23:53:30,115 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [68514025] [2023-11-24 23:53:30,118 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-24 23:53:30,118 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:53:30,119 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:53:30,119 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:53:30,119 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:53:30,545 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-24 23:53:30,546 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:53:32,136 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1688#(and (= |ULTIMATE.start_main_~temp~0#1| 0) (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~#array2~0#1.offset| 0) (<= 3 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |ULTIMATE.start_main_~count~0#1|) (<= 2 |ULTIMATE.start_main_~#array1~0#1.base|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (not (= |ULTIMATE.start_main_~sum~0#1| 0)) (<= 2 |ULTIMATE.start_main_~#array2~0#1.base|) (= (+ |ULTIMATE.start_main_~num~0#1| 1) 0) (= |ULTIMATE.start_main_~#array1~0#1.offset| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~index~0#1| 32765) (<= ~ARR_SIZE~0 32767) (<= 1 |ULTIMATE.start_main_~index~0#1|))' at error location [2023-11-24 23:53:32,137 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:53:32,137 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-11-24 23:53:32,137 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2023-11-24 23:53:32,137 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [724662749] [2023-11-24 23:53:32,137 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-11-24 23:53:32,138 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2023-11-24 23:53:32,138 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:32,139 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2023-11-24 23:53:32,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=213, Invalid=1427, Unknown=0, NotChecked=0, Total=1640 [2023-11-24 23:53:32,148 INFO L87 Difference]: Start difference. First operand 42 states and 46 transitions. Second operand has 20 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 17 states have internal predecessors, (20), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:33,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:33,407 INFO L93 Difference]: Finished difference Result 68 states and 78 transitions. [2023-11-24 23:53:33,408 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-11-24 23:53:33,408 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 17 states have internal predecessors, (20), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2023-11-24 23:53:33,408 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:33,409 INFO L225 Difference]: With dead ends: 68 [2023-11-24 23:53:33,409 INFO L226 Difference]: Without dead ends: 57 [2023-11-24 23:53:33,410 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 565 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=276, Invalid=1794, Unknown=0, NotChecked=0, Total=2070 [2023-11-24 23:53:33,411 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 35 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 328 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 337 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 328 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:33,412 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 110 Invalid, 337 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 328 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-24 23:53:33,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2023-11-24 23:53:33,433 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 49. [2023-11-24 23:53:33,434 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 38 states have (on average 1.1578947368421053) internal successors, (44), 38 states have internal predecessors, (44), 5 states have call successors, (5), 5 states have call predecessors, (5), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2023-11-24 23:53:33,434 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 54 transitions. [2023-11-24 23:53:33,435 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 54 transitions. Word has length 24 [2023-11-24 23:53:33,435 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:33,435 INFO L495 AbstractCegarLoop]: Abstraction has 49 states and 54 transitions. [2023-11-24 23:53:33,436 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 1.1111111111111112) internal successors, (20), 17 states have internal predecessors, (20), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-24 23:53:33,436 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 54 transitions. [2023-11-24 23:53:33,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-11-24 23:53:33,437 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:33,437 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:33,447 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-24 23:53:33,642 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2023-11-24 23:53:33,643 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:33,643 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:33,643 INFO L85 PathProgramCache]: Analyzing trace with hash 1097242359, now seen corresponding path program 7 times [2023-11-24 23:53:33,643 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:33,643 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [27022592] [2023-11-24 23:53:33,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:33,644 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:33,663 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:33,664 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [714710572] [2023-11-24 23:53:33,664 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2023-11-24 23:53:33,665 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:33,665 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:33,666 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:33,670 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-24 23:53:33,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-24 23:53:33,774 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-24 23:53:33,776 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:33,889 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-24 23:53:33,889 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-24 23:53:33,991 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-11-24 23:53:33,991 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-24 23:53:33,991 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [27022592] [2023-11-24 23:53:33,991 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-24 23:53:33,992 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [714710572] [2023-11-24 23:53:33,992 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [714710572] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-24 23:53:33,992 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [655895340] [2023-11-24 23:53:33,994 INFO L159 IcfgInterpreter]: Started Sifa with 15 locations of interest [2023-11-24 23:53:33,994 INFO L166 IcfgInterpreter]: Building call graph [2023-11-24 23:53:33,995 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-24 23:53:33,995 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-24 23:53:33,995 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-24 23:53:34,399 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 1 for LOIs [2023-11-24 23:53:34,400 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-24 23:53:35,137 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2057#(and (= |ULTIMATE.start_main_~temp~0#1| 0) (<= 1 |#StackHeapBarrier|) (= |ULTIMATE.start_main_~#array2~0#1.offset| 0) (<= 3 ~ARR_SIZE~0) (<= ~ARR_SIZE~0 |ULTIMATE.start_main_~count~0#1|) (<= 2 |ULTIMATE.start_main_~#array1~0#1.base|) (= |ULTIMATE.start___VERIFIER_assert_~cond#1| 0) (not (= |ULTIMATE.start_main_~sum~0#1| 0)) (<= 2 |ULTIMATE.start_main_~#array2~0#1.base|) (= (+ |ULTIMATE.start_main_~num~0#1| 1) 0) (= |ULTIMATE.start_main_~#array1~0#1.offset| 0) (= |ULTIMATE.start___VERIFIER_assert_#in~cond#1| 0) (<= |ULTIMATE.start_main_~index~0#1| 32765) (<= ~ARR_SIZE~0 32767) (<= 1 |ULTIMATE.start_main_~index~0#1|))' at error location [2023-11-24 23:53:35,137 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-24 23:53:35,137 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-24 23:53:35,137 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 18 [2023-11-24 23:53:35,137 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1834303683] [2023-11-24 23:53:35,138 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-24 23:53:35,138 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-11-24 23:53:35,138 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-24 23:53:35,139 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-11-24 23:53:35,140 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=153, Invalid=717, Unknown=0, NotChecked=0, Total=870 [2023-11-24 23:53:35,140 INFO L87 Difference]: Start difference. First operand 49 states and 54 transitions. Second operand has 18 states, 18 states have (on average 1.5) internal successors, (27), 18 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:53:35,422 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-24 23:53:35,422 INFO L93 Difference]: Finished difference Result 71 states and 76 transitions. [2023-11-24 23:53:35,422 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2023-11-24 23:53:35,423 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 1.5) internal successors, (27), 18 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 25 [2023-11-24 23:53:35,423 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-24 23:53:35,424 INFO L225 Difference]: With dead ends: 71 [2023-11-24 23:53:35,424 INFO L226 Difference]: Without dead ends: 68 [2023-11-24 23:53:35,425 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 39 SyntacticMatches, 6 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 443 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=222, Invalid=1038, Unknown=0, NotChecked=0, Total=1260 [2023-11-24 23:53:35,425 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 30 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 210 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-24 23:53:35,425 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 117 Invalid, 210 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-24 23:53:35,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2023-11-24 23:53:35,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 57. [2023-11-24 23:53:35,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 44 states have (on average 1.1590909090909092) internal successors, (51), 44 states have internal predecessors, (51), 6 states have call successors, (6), 6 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-11-24 23:53:35,449 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 63 transitions. [2023-11-24 23:53:35,449 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 63 transitions. Word has length 25 [2023-11-24 23:53:35,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-24 23:53:35,449 INFO L495 AbstractCegarLoop]: Abstraction has 57 states and 63 transitions. [2023-11-24 23:53:35,450 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 1.5) internal successors, (27), 18 states have internal predecessors, (27), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-24 23:53:35,450 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 63 transitions. [2023-11-24 23:53:35,451 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-11-24 23:53:35,451 INFO L187 NwaCegarLoop]: Found error trace [2023-11-24 23:53:35,451 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-24 23:53:35,459 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-24 23:53:35,652 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-11-24 23:53:35,652 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-24 23:53:35,653 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-24 23:53:35,653 INFO L85 PathProgramCache]: Analyzing trace with hash -345430900, now seen corresponding path program 8 times [2023-11-24 23:53:35,653 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-24 23:53:35,653 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [899874615] [2023-11-24 23:53:35,653 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-24 23:53:35,653 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-24 23:53:35,670 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-24 23:53:35,670 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [359494687] [2023-11-24 23:53:35,670 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-24 23:53:35,671 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-24 23:53:35,671 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 [2023-11-24 23:53:35,672 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-24 23:53:35,683 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_47445840-c568-420d-bc16-c001d7cd5e9b/bin/utaipan-verify-SwPr7d2a91/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-24 23:53:36,304 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2023-11-24 23:53:36,305 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-24 23:53:36,308 WARN L260 TraceCheckSpWp]: Trace formula consists of 166 conjuncts, 89 conjunts are in the unsatisfiable core [2023-11-24 23:53:36,314 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-24 23:53:36,329 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2023-11-24 23:53:36,367 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 15 [2023-11-24 23:53:36,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 37 [2023-11-24 23:53:36,519 INFO L349 Elim1Store]: treesize reduction 35, result has 16.7 percent of original size [2023-11-24 23:53:36,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 7 case distinctions, treesize of input 58 treesize of output 59 [2023-11-24 23:53:36,640 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,641 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,645 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,648 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,665 INFO L349 Elim1Store]: treesize reduction 47, result has 21.7 percent of original size [2023-11-24 23:53:36,665 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 7 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 16 case distinctions, treesize of input 94 treesize of output 91 [2023-11-24 23:53:36,836 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,838 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,840 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,843 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,845 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,846 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,848 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:36,867 INFO L349 Elim1Store]: treesize reduction 53, result has 14.5 percent of original size [2023-11-24 23:53:36,867 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 8 select indices, 8 select index equivalence classes, 11 disjoint index pairs (out of 28 index pairs), introduced 8 new quantified variables, introduced 29 case distinctions, treesize of input 108 treesize of output 117 [2023-11-24 23:53:37,950 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,956 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,965 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,967 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,968 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,970 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,976 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,978 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,979 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,982 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,988 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:37,991 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:39,199 INFO L349 Elim1Store]: treesize reduction 1421, result has 10.3 percent of original size [2023-11-24 23:53:39,200 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 24 select indices, 24 select index equivalence classes, 19 disjoint index pairs (out of 276 index pairs), introduced 24 new quantified variables, introduced 289 case distinctions, treesize of input 284 treesize of output 375 [2023-11-24 23:53:43,460 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,461 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,462 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,464 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,466 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,469 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,471 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,474 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:43,476 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-24 23:53:46,127 INFO L349 Elim1Store]: treesize reduction 840, result has 38.3 percent of original size [2023-11-24 23:53:46,128 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 22 select indices, 22 select index equivalence classes, 22 disjoint index pairs (out of 231 index pairs), introduced 22 new quantified variables, introduced 231 case distinctions, treesize of input 390 treesize of output 662