./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version cf1a7837 Calling Ultimate with: /usr/lib/jvm/java-11-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 9e9911e775b3214ba13077b05d83e9364947724e9afa3bb89f51b07ee325bd90 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-cf1a783 [2023-11-12 00:57:30,024 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-12 00:57:30,129 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/config/svcomp-Reach-32bit-Taipan_Default.epf [2023-11-12 00:57:30,138 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-12 00:57:30,139 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-12 00:57:30,187 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-12 00:57:30,188 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-12 00:57:30,189 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-12 00:57:30,190 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-12 00:57:30,196 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-12 00:57:30,196 INFO L153 SettingsManager]: * User list type=DISABLED [2023-11-12 00:57:30,198 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-11-12 00:57:30,198 INFO L153 SettingsManager]: * Explicit value domain=true [2023-11-12 00:57:30,201 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-11-12 00:57:30,201 INFO L153 SettingsManager]: * Octagon Domain=false [2023-11-12 00:57:30,202 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2023-11-12 00:57:30,202 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-11-12 00:57:30,203 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-11-12 00:57:30,204 INFO L153 SettingsManager]: * Interval Domain=false [2023-11-12 00:57:30,204 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-11-12 00:57:30,205 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-11-12 00:57:30,206 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2023-11-12 00:57:30,207 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-12 00:57:30,208 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-12 00:57:30,208 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-12 00:57:30,209 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-12 00:57:30,209 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-12 00:57:30,210 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-12 00:57:30,210 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-12 00:57:30,211 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-12 00:57:30,213 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-12 00:57:30,213 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-12 00:57:30,213 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-12 00:57:30,214 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-12 00:57:30,214 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-12 00:57:30,215 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-12 00:57:30,215 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:57:30,215 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-12 00:57:30,216 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-12 00:57:30,216 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-12 00:57:30,216 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-11-12 00:57:30,217 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-12 00:57:30,217 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-12 00:57:30,218 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-11-12 00:57:30,219 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-12 00:57:30,219 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_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 9e9911e775b3214ba13077b05d83e9364947724e9afa3bb89f51b07ee325bd90 [2023-11-12 00:57:30,638 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-12 00:57:30,671 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-12 00:57:30,674 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-12 00:57:30,675 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-12 00:57:30,676 INFO L274 PluginConnector]: CDTParser initialized [2023-11-12 00:57:30,678 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/../../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c [2023-11-12 00:57:33,990 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-12 00:57:34,245 INFO L384 CDTParser]: Found 1 translation units. [2023-11-12 00:57:34,246 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c [2023-11-12 00:57:34,257 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/data/004133c41/685da848dee64df2a243a2aa218e2002/FLAG71b289b38 [2023-11-12 00:57:34,283 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/data/004133c41/685da848dee64df2a243a2aa218e2002 [2023-11-12 00:57:34,290 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-12 00:57:34,292 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-12 00:57:34,296 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-12 00:57:34,296 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-12 00:57:34,303 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-12 00:57:34,306 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,308 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3cb8d47b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34, skipping insertion in model container [2023-11-12 00:57:34,308 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,344 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-12 00:57:34,590 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_de330b7a-1561-4068-a50f-92483a404bcc/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c[490,503] [2023-11-12 00:57:34,648 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:57:34,663 INFO L202 MainTranslator]: Completed pre-run [2023-11-12 00:57:34,684 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_de330b7a-1561-4068-a50f-92483a404bcc/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound20.c[490,503] [2023-11-12 00:57:34,720 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-12 00:57:34,746 INFO L206 MainTranslator]: Completed translation [2023-11-12 00:57:34,746 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34 WrapperNode [2023-11-12 00:57:34,746 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-12 00:57:34,748 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-12 00:57:34,748 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-12 00:57:34,749 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-12 00:57:34,758 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,779 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,817 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 86 [2023-11-12 00:57:34,818 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-12 00:57:34,819 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-12 00:57:34,819 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-12 00:57:34,820 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-12 00:57:34,832 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,832 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,838 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,839 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,855 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,859 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,860 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,862 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,864 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-12 00:57:34,865 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-12 00:57:34,866 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-12 00:57:34,866 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-12 00:57:34,867 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (1/1) ... [2023-11-12 00:57:34,884 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-12 00:57:34,898 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:34,914 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-12 00:57:34,945 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-12 00:57:34,970 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-12 00:57:34,971 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-11-12 00:57:34,971 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-11-12 00:57:34,971 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-11-12 00:57:34,971 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-12 00:57:34,972 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-12 00:57:34,972 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-11-12 00:57:34,972 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-11-12 00:57:35,050 INFO L236 CfgBuilder]: Building ICFG [2023-11-12 00:57:35,053 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-12 00:57:35,303 INFO L277 CfgBuilder]: Performing block encoding [2023-11-12 00:57:35,342 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-12 00:57:35,342 INFO L302 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-12 00:57:35,346 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:57:35 BoogieIcfgContainer [2023-11-12 00:57:35,346 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-12 00:57:35,349 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-12 00:57:35,349 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-12 00:57:35,354 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-12 00:57:35,354 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 12:57:34" (1/3) ... [2023-11-12 00:57:35,355 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d02b6d0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:57:35, skipping insertion in model container [2023-11-12 00:57:35,356 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 12:57:34" (2/3) ... [2023-11-12 00:57:35,356 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1d02b6d0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 12:57:35, skipping insertion in model container [2023-11-12 00:57:35,357 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 12:57:35" (3/3) ... [2023-11-12 00:57:35,358 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound20.c [2023-11-12 00:57:35,384 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-12 00:57:35,384 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-11-12 00:57:35,442 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-12 00:57:35,450 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;@1247a904, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-12 00:57:35,451 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-11-12 00:57:35,456 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 15 states have (on average 1.5333333333333334) internal successors, (23), 17 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2023-11-12 00:57:35,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-11-12 00:57:35,467 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:35,467 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:35,468 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:35,475 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:35,476 INFO L85 PathProgramCache]: Analyzing trace with hash 1288775727, now seen corresponding path program 1 times [2023-11-12 00:57:35,488 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:35,489 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [490103497] [2023-11-12 00:57:35,490 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:35,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:35,605 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:35,606 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [613181524] [2023-11-12 00:57:35,607 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:35,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:35,607 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:35,612 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:35,621 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-12 00:57:35,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:35,783 INFO L262 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 1 conjunts are in the unsatisfiable core [2023-11-12 00:57:35,811 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:35,860 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:57:35,860 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:57:35,861 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:35,861 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [490103497] [2023-11-12 00:57:35,861 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:35,863 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613181524] [2023-11-12 00:57:35,863 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613181524] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:57:35,863 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:57:35,864 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-11-12 00:57:35,866 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [905994687] [2023-11-12 00:57:35,867 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:35,872 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-11-12 00:57:35,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:35,911 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-11-12 00:57:35,912 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-11-12 00:57:35,914 INFO L87 Difference]: Start difference. First operand has 29 states, 15 states have (on average 1.5333333333333334) internal successors, (23), 17 states have internal predecessors, (23), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:35,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:35,982 INFO L93 Difference]: Finished difference Result 50 states and 81 transitions. [2023-11-12 00:57:35,985 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-11-12 00:57:35,988 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 19 [2023-11-12 00:57:35,988 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:35,998 INFO L225 Difference]: With dead ends: 50 [2023-11-12 00:57:35,999 INFO L226 Difference]: Without dead ends: 27 [2023-11-12 00:57:36,004 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 18 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-12 00:57:36,010 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:57:36,013 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 37 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:57:36,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2023-11-12 00:57:36,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2023-11-12 00:57:36,072 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 14 states have (on average 1.3571428571428572) internal successors, (19), 16 states have internal predecessors, (19), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:57:36,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 38 transitions. [2023-11-12 00:57:36,076 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 38 transitions. Word has length 19 [2023-11-12 00:57:36,077 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:36,078 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 38 transitions. [2023-11-12 00:57:36,078 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:36,079 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 38 transitions. [2023-11-12 00:57:36,085 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2023-11-12 00:57:36,086 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:36,086 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:36,099 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-12 00:57:36,294 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:36,294 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:36,296 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:36,297 INFO L85 PathProgramCache]: Analyzing trace with hash 226858993, now seen corresponding path program 1 times [2023-11-12 00:57:36,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:36,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1796400243] [2023-11-12 00:57:36,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:36,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:36,354 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:36,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [694717732] [2023-11-12 00:57:36,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:36,355 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:36,355 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:36,360 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:36,369 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-12 00:57:36,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:36,449 INFO L262 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 3 conjunts are in the unsatisfiable core [2023-11-12 00:57:36,452 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:36,534 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:57:36,535 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:57:36,535 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:36,535 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1796400243] [2023-11-12 00:57:36,536 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:36,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [694717732] [2023-11-12 00:57:36,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [694717732] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:57:36,536 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:57:36,537 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-12 00:57:36,537 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1224665251] [2023-11-12 00:57:36,537 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:36,538 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-12 00:57:36,538 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:36,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-12 00:57:36,540 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 00:57:36,540 INFO L87 Difference]: Start difference. First operand 27 states and 38 transitions. Second operand has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:36,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:36,567 INFO L93 Difference]: Finished difference Result 37 states and 49 transitions. [2023-11-12 00:57:36,567 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-12 00:57:36,568 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 20 [2023-11-12 00:57:36,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:36,569 INFO L225 Difference]: With dead ends: 37 [2023-11-12 00:57:36,569 INFO L226 Difference]: Without dead ends: 29 [2023-11-12 00:57:36,570 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-11-12 00:57:36,571 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 0 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:57:36,572 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 91 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:57:36,573 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2023-11-12 00:57:36,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2023-11-12 00:57:36,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 16 states have (on average 1.3125) internal successors, (21), 17 states have internal predecessors, (21), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:57:36,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 40 transitions. [2023-11-12 00:57:36,582 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 40 transitions. Word has length 20 [2023-11-12 00:57:36,583 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:36,583 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 40 transitions. [2023-11-12 00:57:36,583 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.0) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:36,583 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 40 transitions. [2023-11-12 00:57:36,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2023-11-12 00:57:36,585 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:36,585 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:36,609 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-12 00:57:36,798 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:36,799 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:36,800 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:36,800 INFO L85 PathProgramCache]: Analyzing trace with hash -1563892497, now seen corresponding path program 1 times [2023-11-12 00:57:36,800 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:36,801 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [291485850] [2023-11-12 00:57:36,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:36,802 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:36,827 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:36,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1799007158] [2023-11-12 00:57:36,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:36,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:36,829 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:36,831 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:36,833 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-12 00:57:36,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:36,903 INFO L262 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-12 00:57:36,906 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:36,958 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:57:36,958 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:57:37,038 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:57:37,039 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:37,039 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [291485850] [2023-11-12 00:57:37,039 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:37,040 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1799007158] [2023-11-12 00:57:37,040 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1799007158] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:57:37,040 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1639712301] [2023-11-12 00:57:37,068 INFO L159 IcfgInterpreter]: Started Sifa with 16 locations of interest [2023-11-12 00:57:37,068 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:57:37,071 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:57:37,076 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:57:37,076 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:57:38,669 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 7 for LOIs [2023-11-12 00:57:38,671 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:57:40,156 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1639712301] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:57:40,156 INFO L185 FreeRefinementEngine]: Found 1 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:57:40,157 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [5, 5] total 15 [2023-11-12 00:57:40,158 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1850076207] [2023-11-12 00:57:40,158 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:40,159 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-11-12 00:57:40,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:40,161 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-12 00:57:40,162 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:57:40,163 INFO L87 Difference]: Start difference. First operand 29 states and 40 transitions. Second operand has 12 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-12 00:57:40,422 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:40,423 INFO L93 Difference]: Finished difference Result 38 states and 50 transitions. [2023-11-12 00:57:40,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-11-12 00:57:40,424 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 21 [2023-11-12 00:57:40,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:40,427 INFO L225 Difference]: With dead ends: 38 [2023-11-12 00:57:40,427 INFO L226 Difference]: Without dead ends: 30 [2023-11-12 00:57:40,429 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 46 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2023-11-12 00:57:40,437 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 0 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 108 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-11-12 00:57:40,443 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 108 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-11-12 00:57:40,445 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2023-11-12 00:57:40,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2023-11-12 00:57:40,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 18 states have internal predecessors, (22), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:57:40,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2023-11-12 00:57:40,460 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 21 [2023-11-12 00:57:40,460 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:40,461 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2023-11-12 00:57:40,461 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 6 states have internal predecessors, (9), 5 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-11-12 00:57:40,461 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2023-11-12 00:57:40,462 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2023-11-12 00:57:40,463 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:40,463 INFO L195 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:40,470 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-11-12 00:57:40,670 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:40,671 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:40,671 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:40,672 INFO L85 PathProgramCache]: Analyzing trace with hash 281079646, now seen corresponding path program 1 times [2023-11-12 00:57:40,672 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:40,672 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1826693392] [2023-11-12 00:57:40,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:40,672 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:40,686 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:40,686 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1150082173] [2023-11-12 00:57:40,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:40,687 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:40,688 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:40,689 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:40,716 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-12 00:57:40,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:40,772 INFO L262 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-12 00:57:40,776 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:40,873 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:57:40,873 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:57:40,967 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:57:40,967 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:40,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1826693392] [2023-11-12 00:57:40,968 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:40,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1150082173] [2023-11-12 00:57:40,970 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1150082173] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-12 00:57:40,970 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:57:40,971 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 11 [2023-11-12 00:57:40,971 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [151724098] [2023-11-12 00:57:40,972 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:40,973 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:57:40,973 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:40,974 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:57:40,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2023-11-12 00:57:40,975 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:41,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:41,092 INFO L93 Difference]: Finished difference Result 36 states and 46 transitions. [2023-11-12 00:57:41,093 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:57:41,094 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 23 [2023-11-12 00:57:41,094 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:41,095 INFO L225 Difference]: With dead ends: 36 [2023-11-12 00:57:41,095 INFO L226 Difference]: Without dead ends: 34 [2023-11-12 00:57:41,096 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-11-12 00:57:41,097 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 8 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:57:41,098 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 104 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:57:41,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-11-12 00:57:41,112 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2023-11-12 00:57:41,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 20 states have (on average 1.25) internal successors, (25), 21 states have internal predecessors, (25), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:57:41,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 44 transitions. [2023-11-12 00:57:41,118 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 44 transitions. Word has length 23 [2023-11-12 00:57:41,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:41,120 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 44 transitions. [2023-11-12 00:57:41,120 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:41,120 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 44 transitions. [2023-11-12 00:57:41,122 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-11-12 00:57:41,122 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:41,123 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:41,135 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-11-12 00:57:41,324 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:41,324 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:41,324 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:41,325 INFO L85 PathProgramCache]: Analyzing trace with hash -717512630, now seen corresponding path program 1 times [2023-11-12 00:57:41,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:41,325 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2028829291] [2023-11-12 00:57:41,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:41,325 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:41,342 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:41,344 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2113787980] [2023-11-12 00:57:41,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:41,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:41,346 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:41,351 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:41,387 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-12 00:57:41,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:41,427 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-12 00:57:41,429 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:41,474 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:57:41,474 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-12 00:57:41,474 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:41,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2028829291] [2023-11-12 00:57:41,475 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:41,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2113787980] [2023-11-12 00:57:41,475 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2113787980] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:57:41,475 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-12 00:57:41,476 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-11-12 00:57:41,476 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [332515277] [2023-11-12 00:57:41,476 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:41,477 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:57:41,477 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:41,478 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:57:41,478 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:57:41,478 INFO L87 Difference]: Start difference. First operand 34 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:41,512 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:41,512 INFO L93 Difference]: Finished difference Result 59 states and 77 transitions. [2023-11-12 00:57:41,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-12 00:57:41,513 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 26 [2023-11-12 00:57:41,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:41,514 INFO L225 Difference]: With dead ends: 59 [2023-11-12 00:57:41,515 INFO L226 Difference]: Without dead ends: 36 [2023-11-12 00:57:41,516 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-11-12 00:57:41,517 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 113 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-12 00:57:41,518 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 113 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:57:41,519 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2023-11-12 00:57:41,529 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2023-11-12 00:57:41,530 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 23 states have internal predecessors, (27), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-11-12 00:57:41,531 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 46 transitions. [2023-11-12 00:57:41,532 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 46 transitions. Word has length 26 [2023-11-12 00:57:41,532 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:41,532 INFO L495 AbstractCegarLoop]: Abstraction has 36 states and 46 transitions. [2023-11-12 00:57:41,533 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-11-12 00:57:41,533 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 46 transitions. [2023-11-12 00:57:41,534 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2023-11-12 00:57:41,534 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:41,535 INFO L195 NwaCegarLoop]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:41,551 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-11-12 00:57:41,741 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:41,742 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:41,743 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:41,743 INFO L85 PathProgramCache]: Analyzing trace with hash -207347326, now seen corresponding path program 1 times [2023-11-12 00:57:41,743 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:41,744 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [860919523] [2023-11-12 00:57:41,744 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:41,744 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:41,758 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:41,758 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [407421947] [2023-11-12 00:57:41,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:41,759 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:41,759 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:41,761 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:41,792 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-11-12 00:57:41,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:41,858 INFO L262 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:57:41,861 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:42,111 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-11-12 00:57:42,111 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:57:42,237 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-11-12 00:57:42,238 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:42,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [860919523] [2023-11-12 00:57:42,238 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:42,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [407421947] [2023-11-12 00:57:42,239 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [407421947] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-12 00:57:42,239 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:57:42,239 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 12 [2023-11-12 00:57:42,240 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1395651150] [2023-11-12 00:57:42,240 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:42,241 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:57:42,241 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:42,241 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:57:42,242 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-11-12 00:57:42,242 INFO L87 Difference]: Start difference. First operand 36 states and 46 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 00:57:42,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:42,320 INFO L93 Difference]: Finished difference Result 50 states and 65 transitions. [2023-11-12 00:57:42,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:57:42,321 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 28 [2023-11-12 00:57:42,322 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:42,323 INFO L225 Difference]: With dead ends: 50 [2023-11-12 00:57:42,323 INFO L226 Difference]: Without dead ends: 48 [2023-11-12 00:57:42,323 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2023-11-12 00:57:42,325 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 7 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:57:42,325 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 121 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:57:42,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2023-11-12 00:57:42,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 47. [2023-11-12 00:57:42,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 28 states have (on average 1.25) internal successors, (35), 29 states have internal predecessors, (35), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-11-12 00:57:42,344 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 62 transitions. [2023-11-12 00:57:42,344 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 62 transitions. Word has length 28 [2023-11-12 00:57:42,345 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:42,345 INFO L495 AbstractCegarLoop]: Abstraction has 47 states and 62 transitions. [2023-11-12 00:57:42,345 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-11-12 00:57:42,345 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 62 transitions. [2023-11-12 00:57:42,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2023-11-12 00:57:42,347 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:42,347 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:42,359 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-11-12 00:57:42,548 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:42,549 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:42,549 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:42,549 INFO L85 PathProgramCache]: Analyzing trace with hash -159662690, now seen corresponding path program 1 times [2023-11-12 00:57:42,549 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:42,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [13534029] [2023-11-12 00:57:42,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:42,550 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:42,564 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:42,565 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1797408247] [2023-11-12 00:57:42,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:42,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:42,566 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:42,567 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:42,571 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-11-12 00:57:42,637 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:42,638 INFO L262 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 23 conjunts are in the unsatisfiable core [2023-11-12 00:57:42,641 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:42,860 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2023-11-12 00:57:42,861 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:57:43,041 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-11-12 00:57:43,041 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:43,042 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [13534029] [2023-11-12 00:57:43,042 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:43,042 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1797408247] [2023-11-12 00:57:43,042 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1797408247] provided 1 perfect and 1 imperfect interpolant sequences [2023-11-12 00:57:43,042 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:57:43,043 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 12 [2023-11-12 00:57:43,043 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1696781585] [2023-11-12 00:57:43,043 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:43,044 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-12 00:57:43,044 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:43,045 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-12 00:57:43,045 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2023-11-12 00:57:43,045 INFO L87 Difference]: Start difference. First operand 47 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-12 00:57:43,116 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:43,117 INFO L93 Difference]: Finished difference Result 54 states and 68 transitions. [2023-11-12 00:57:43,117 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-12 00:57:43,117 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 33 [2023-11-12 00:57:43,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:43,119 INFO L225 Difference]: With dead ends: 54 [2023-11-12 00:57:43,119 INFO L226 Difference]: Without dead ends: 52 [2023-11-12 00:57:43,119 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2023-11-12 00:57:43,120 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 7 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-12 00:57:43,121 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 112 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-12 00:57:43,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2023-11-12 00:57:43,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2023-11-12 00:57:43,137 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 32 states have internal predecessors, (38), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2023-11-12 00:57:43,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 65 transitions. [2023-11-12 00:57:43,138 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 65 transitions. Word has length 33 [2023-11-12 00:57:43,139 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:43,139 INFO L495 AbstractCegarLoop]: Abstraction has 51 states and 65 transitions. [2023-11-12 00:57:43,139 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-11-12 00:57:43,139 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 65 transitions. [2023-11-12 00:57:43,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-11-12 00:57:43,141 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:43,141 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:43,153 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-11-12 00:57:43,347 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:43,350 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:43,350 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:43,350 INFO L85 PathProgramCache]: Analyzing trace with hash -2048234814, now seen corresponding path program 1 times [2023-11-12 00:57:43,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:43,351 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1328207514] [2023-11-12 00:57:43,351 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:43,351 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:43,374 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:43,375 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2009962003] [2023-11-12 00:57:43,375 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:43,375 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:43,375 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:43,377 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:43,382 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-11-12 00:57:43,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:43,450 INFO L262 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 24 conjunts are in the unsatisfiable core [2023-11-12 00:57:43,453 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:43,711 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 13 proven. 2 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2023-11-12 00:57:43,711 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:57:43,865 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:43,865 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1328207514] [2023-11-12 00:57:43,866 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:43,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2009962003] [2023-11-12 00:57:43,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2009962003] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-12 00:57:43,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1870135883] [2023-11-12 00:57:43,870 INFO L159 IcfgInterpreter]: Started Sifa with 23 locations of interest [2023-11-12 00:57:43,870 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:57:43,871 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:57:43,871 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:57:43,872 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:57:45,506 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 9 for LOIs [2023-11-12 00:57:45,515 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 7 for LOIs [2023-11-12 00:57:45,518 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:57:50,448 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1870135883] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-12 00:57:50,448 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-12 00:57:50,448 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [9] total 24 [2023-11-12 00:57:50,449 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1401330718] [2023-11-12 00:57:50,449 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-12 00:57:50,449 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2023-11-12 00:57:50,449 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:57:50,450 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2023-11-12 00:57:50,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=580, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:57:50,451 INFO L87 Difference]: Start difference. First operand 51 states and 65 transitions. Second operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 10 states have internal predecessors, (13), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-12 00:57:51,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:57:51,116 INFO L93 Difference]: Finished difference Result 75 states and 90 transitions. [2023-11-12 00:57:51,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2023-11-12 00:57:51,117 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 10 states have internal predecessors, (13), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 38 [2023-11-12 00:57:51,117 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:57:51,118 INFO L225 Difference]: With dead ends: 75 [2023-11-12 00:57:51,119 INFO L226 Difference]: Without dead ends: 73 [2023-11-12 00:57:51,119 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 52 SyntacticMatches, 3 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 227 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=122, Invalid=580, Unknown=0, NotChecked=0, Total=702 [2023-11-12 00:57:51,120 INFO L413 NwaCegarLoop]: 17 mSDtfsCounter, 1 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 271 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-11-12 00:57:51,120 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [2 Valid, 99 Invalid, 271 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-11-12 00:57:51,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2023-11-12 00:57:51,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2023-11-12 00:57:51,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 43 states have (on average 1.1627906976744187) internal successors, (50), 45 states have internal predecessors, (50), 18 states have call successors, (18), 9 states have call predecessors, (18), 9 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2023-11-12 00:57:51,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2023-11-12 00:57:51,144 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 38 [2023-11-12 00:57:51,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:57:51,144 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2023-11-12 00:57:51,145 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 10 states have internal predecessors, (13), 5 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2023-11-12 00:57:51,145 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2023-11-12 00:57:51,146 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2023-11-12 00:57:51,147 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:57:51,147 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:57:51,156 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-11-12 00:57:51,353 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,9 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:51,353 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:57:51,354 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:57:51,354 INFO L85 PathProgramCache]: Analyzing trace with hash 2026078407, now seen corresponding path program 1 times [2023-11-12 00:57:51,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:57:51,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [222218671] [2023-11-12 00:57:51,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:51,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:57:51,363 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:57:51,363 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [853515654] [2023-11-12 00:57:51,363 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:57:51,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:57:51,364 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:57:51,365 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:57:51,400 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-11-12 00:57:51,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:57:51,447 INFO L262 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-12 00:57:51,449 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:57:51,528 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 00:57:51,528 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:57:51,610 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2023-11-12 00:57:51,610 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:57:51,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [222218671] [2023-11-12 00:57:51,610 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:57:51,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [853515654] [2023-11-12 00:57:51,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [853515654] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:57:51,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1078152335] [2023-11-12 00:57:51,614 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2023-11-12 00:57:51,614 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:57:51,615 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:57:51,615 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:57:51,615 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:57:58,201 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 113 for LOIs [2023-11-12 00:57:58,495 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 7 for LOIs [2023-11-12 00:57:58,496 INFO L180 IcfgInterpreter]: Interpretation finished [2023-11-12 00:58:06,714 WARN L293 SmtUtils]: Spent 6.60s on a formula simplification. DAG size of input: 139 DAG size of output: 115 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-11-12 00:58:10,589 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2391#(and (<= 2 ~counter~0) (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (<= ~counter~0 20))' at error location [2023-11-12 00:58:10,589 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-11-12 00:58:10,590 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-12 00:58:10,590 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-11-12 00:58:10,590 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1024544052] [2023-11-12 00:58:10,590 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-12 00:58:10,591 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-11-12 00:58:10,591 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-11-12 00:58:10,592 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-11-12 00:58:10,593 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=593, Unknown=0, NotChecked=0, Total=756 [2023-11-12 00:58:10,593 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-11-12 00:58:10,844 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-12 00:58:10,844 INFO L93 Difference]: Finished difference Result 192 states and 235 transitions. [2023-11-12 00:58:10,844 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-11-12 00:58:10,845 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 47 [2023-11-12 00:58:10,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-12 00:58:10,847 INFO L225 Difference]: With dead ends: 192 [2023-11-12 00:58:10,847 INFO L226 Difference]: Without dead ends: 184 [2023-11-12 00:58:10,848 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 109 SyntacticMatches, 4 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 439 ImplicationChecksByTransitivity, 12.2s TimeCoverageRelationStatistics Valid=197, Invalid=795, Unknown=0, NotChecked=0, Total=992 [2023-11-12 00:58:10,849 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 76 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 85 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 85 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-12 00:58:10,850 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [76 Valid, 151 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 85 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-12 00:58:10,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2023-11-12 00:58:10,913 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 176. [2023-11-12 00:58:10,915 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 176 states, 110 states have (on average 1.2181818181818183) internal successors, (134), 114 states have internal predecessors, (134), 44 states have call successors, (44), 21 states have call predecessors, (44), 21 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2023-11-12 00:58:10,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 176 states to 176 states and 218 transitions. [2023-11-12 00:58:10,921 INFO L78 Accepts]: Start accepts. Automaton has 176 states and 218 transitions. Word has length 47 [2023-11-12 00:58:10,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-12 00:58:10,922 INFO L495 AbstractCegarLoop]: Abstraction has 176 states and 218 transitions. [2023-11-12 00:58:10,922 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.3) internal successors, (33), 10 states have internal predecessors, (33), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2023-11-12 00:58:10,922 INFO L276 IsEmpty]: Start isEmpty. Operand 176 states and 218 transitions. [2023-11-12 00:58:10,925 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2023-11-12 00:58:10,927 INFO L187 NwaCegarLoop]: Found error trace [2023-11-12 00:58:10,928 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-12 00:58:10,934 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-11-12 00:58:11,133 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:58:11,134 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-12 00:58:11,134 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-12 00:58:11,134 INFO L85 PathProgramCache]: Analyzing trace with hash -1622665511, now seen corresponding path program 1 times [2023-11-12 00:58:11,134 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-11-12 00:58:11,134 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [518233270] [2023-11-12 00:58:11,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:58:11,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-12 00:58:11,144 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-11-12 00:58:11,144 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [814539108] [2023-11-12 00:58:11,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-12 00:58:11,145 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-12 00:58:11,145 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 [2023-11-12 00:58:11,146 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-12 00:58:11,152 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_de330b7a-1561-4068-a50f-92483a404bcc/bin/utaipan-verify-NcY6lQBIFX/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-11-12 00:58:11,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-12 00:58:11,214 INFO L262 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 9 conjunts are in the unsatisfiable core [2023-11-12 00:58:11,216 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-12 00:58:11,275 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2023-11-12 00:58:11,275 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-12 00:58:11,354 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 8 proven. 6 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2023-11-12 00:58:11,354 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-11-12 00:58:11,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [518233270] [2023-11-12 00:58:11,354 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-11-12 00:58:11,354 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [814539108] [2023-11-12 00:58:11,355 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [814539108] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-12 00:58:11,355 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1728447536] [2023-11-12 00:58:11,357 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2023-11-12 00:58:11,357 INFO L166 IcfgInterpreter]: Building call graph [2023-11-12 00:58:11,358 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-11-12 00:58:11,358 INFO L176 IcfgInterpreter]: Starting interpretation [2023-11-12 00:58:11,358 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-11-12 00:58:16,772 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 109 for LOIs [2023-11-12 00:58:17,065 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 7 for LOIs [2023-11-12 00:58:17,067 INFO L180 IcfgInterpreter]: Interpretation finished