./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/heap-manipulation/dancing.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 791161d1 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/heap-manipulation/dancing.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a --- Real Ultimate output --- This is Ultimate 0.2.2-?-791161d [2022-07-22 14:35:12,485 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-22 14:35:12,487 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-22 14:35:12,533 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-22 14:35:12,533 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-22 14:35:12,535 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-22 14:35:12,536 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-22 14:35:12,539 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-22 14:35:12,540 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-22 14:35:12,544 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-22 14:35:12,545 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-22 14:35:12,547 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-22 14:35:12,547 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-22 14:35:12,549 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-22 14:35:12,550 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-22 14:35:12,553 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-22 14:35:12,554 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-22 14:35:12,556 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-22 14:35:12,557 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-22 14:35:12,562 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-22 14:35:12,564 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-22 14:35:12,565 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-22 14:35:12,565 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-22 14:35:12,566 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-22 14:35:12,568 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-22 14:35:12,574 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-22 14:35:12,575 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-22 14:35:12,575 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-22 14:35:12,576 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-22 14:35:12,577 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-22 14:35:12,578 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-22 14:35:12,578 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-22 14:35:12,579 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-22 14:35:12,580 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-22 14:35:12,581 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-22 14:35:12,582 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-22 14:35:12,582 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-22 14:35:12,583 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-22 14:35:12,583 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-22 14:35:12,584 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-22 14:35:12,584 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-22 14:35:12,586 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-22 14:35:12,587 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-22 14:35:12,614 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-22 14:35:12,615 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-22 14:35:12,615 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-22 14:35:12,615 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-22 14:35:12,616 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-22 14:35:12,616 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-22 14:35:12,617 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-22 14:35:12,617 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-22 14:35:12,617 INFO L138 SettingsManager]: * Use SBE=true [2022-07-22 14:35:12,618 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-22 14:35:12,618 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-22 14:35:12,618 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-22 14:35:12,619 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-22 14:35:12,619 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-22 14:35:12,619 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-22 14:35:12,619 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-22 14:35:12,620 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-22 14:35:12,620 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-22 14:35:12,620 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-22 14:35:12,620 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-22 14:35:12,621 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-22 14:35:12,622 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-22 14:35:12,622 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-22 14:35:12,622 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-22 14:35:12,622 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-22 14:35:12,623 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-22 14:35:12,623 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-22 14:35:12,623 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-22 14:35:12,623 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-22 14:35:12,624 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-22 14:35:12,624 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-22 14:35:12,624 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-22 14:35:12,625 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-22 14:35:12,625 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/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 -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a [2022-07-22 14:35:12,850 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-22 14:35:12,872 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-22 14:35:12,875 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-22 14:35:12,875 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-22 14:35:12,876 INFO L275 PluginConnector]: CDTParser initialized [2022-07-22 14:35:12,877 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/heap-manipulation/dancing.i [2022-07-22 14:35:12,937 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3cf2c2293/f93943a056924311934ca81d3b9b909c/FLAG8343f2f9d [2022-07-22 14:35:13,388 INFO L306 CDTParser]: Found 1 translation units. [2022-07-22 14:35:13,389 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i [2022-07-22 14:35:13,404 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3cf2c2293/f93943a056924311934ca81d3b9b909c/FLAG8343f2f9d [2022-07-22 14:35:13,423 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3cf2c2293/f93943a056924311934ca81d3b9b909c [2022-07-22 14:35:13,426 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-22 14:35:13,427 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-22 14:35:13,430 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-22 14:35:13,430 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-22 14:35:13,433 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-22 14:35:13,434 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,435 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5c55e355 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13, skipping insertion in model container [2022-07-22 14:35:13,435 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,441 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-22 14:35:13,477 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-22 14:35:13,622 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i[938,951] [2022-07-22 14:35:13,746 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-22 14:35:13,754 INFO L203 MainTranslator]: Completed pre-run [2022-07-22 14:35:13,764 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i[938,951] [2022-07-22 14:35:13,785 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-22 14:35:13,809 INFO L208 MainTranslator]: Completed translation [2022-07-22 14:35:13,810 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13 WrapperNode [2022-07-22 14:35:13,810 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-22 14:35:13,811 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-22 14:35:13,811 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-22 14:35:13,811 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-22 14:35:13,821 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,836 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,855 INFO L137 Inliner]: procedures = 124, calls = 40, calls flagged for inlining = 5, calls inlined = 5, statements flattened = 90 [2022-07-22 14:35:13,856 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-22 14:35:13,857 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-22 14:35:13,857 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-22 14:35:13,857 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-22 14:35:13,864 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,865 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,868 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,868 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,876 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,885 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,891 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,893 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-22 14:35:13,894 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-22 14:35:13,894 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-22 14:35:13,895 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-22 14:35:13,896 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (1/1) ... [2022-07-22 14:35:13,907 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-22 14:35:13,918 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 14:35:13,932 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-07-22 14:35:13,935 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-07-22 14:35:13,966 INFO L130 BoogieDeclarations]: Found specification of procedure is_list_containing_x [2022-07-22 14:35:13,966 INFO L138 BoogieDeclarations]: Found implementation of procedure is_list_containing_x [2022-07-22 14:35:13,967 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-22 14:35:13,967 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-22 14:35:13,967 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2022-07-22 14:35:13,967 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-22 14:35:13,967 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2022-07-22 14:35:13,968 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2022-07-22 14:35:13,968 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2022-07-22 14:35:13,968 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-07-22 14:35:13,968 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-22 14:35:13,968 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-22 14:35:13,968 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-22 14:35:14,041 INFO L234 CfgBuilder]: Building ICFG [2022-07-22 14:35:14,042 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-22 14:35:14,277 INFO L275 CfgBuilder]: Performing block encoding [2022-07-22 14:35:14,295 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-22 14:35:14,296 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-07-22 14:35:14,297 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 02:35:14 BoogieIcfgContainer [2022-07-22 14:35:14,297 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-22 14:35:14,299 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-22 14:35:14,299 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-22 14:35:14,312 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-22 14:35:14,313 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.07 02:35:13" (1/3) ... [2022-07-22 14:35:14,313 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@68352297 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.07 02:35:14, skipping insertion in model container [2022-07-22 14:35:14,314 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:35:13" (2/3) ... [2022-07-22 14:35:14,314 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@68352297 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.07 02:35:14, skipping insertion in model container [2022-07-22 14:35:14,314 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 02:35:14" (3/3) ... [2022-07-22 14:35:14,315 INFO L111 eAbstractionObserver]: Analyzing ICFG dancing.i [2022-07-22 14:35:14,328 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-22 14:35:14,329 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-22 14:35:14,370 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-22 14:35:14,376 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=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@cd88e55, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@173352d9 [2022-07-22 14:35:14,376 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-22 14:35:14,381 INFO L276 IsEmpty]: Start isEmpty. Operand has 41 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 32 states have internal predecessors, (45), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-07-22 14:35:14,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-07-22 14:35:14,388 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:14,389 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:14,389 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:14,394 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:14,394 INFO L85 PathProgramCache]: Analyzing trace with hash 1472755522, now seen corresponding path program 1 times [2022-07-22 14:35:14,400 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:14,401 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [990088267] [2022-07-22 14:35:14,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:14,402 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:14,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:14,611 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:14,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:14,638 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 14:35:14,640 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:14,641 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [990088267] [2022-07-22 14:35:14,642 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [990088267] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:14,642 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:14,642 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-22 14:35:14,644 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2099983991] [2022-07-22 14:35:14,644 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:14,649 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-22 14:35:14,650 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:14,678 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-22 14:35:14,679 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-22 14:35:14,681 INFO L87 Difference]: Start difference. First operand has 41 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 32 states have internal predecessors, (45), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-22 14:35:14,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:14,707 INFO L93 Difference]: Finished difference Result 77 states and 107 transitions. [2022-07-22 14:35:14,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-22 14:35:14,709 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 20 [2022-07-22 14:35:14,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:14,718 INFO L225 Difference]: With dead ends: 77 [2022-07-22 14:35:14,719 INFO L226 Difference]: Without dead ends: 37 [2022-07-22 14:35:14,722 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-22 14:35:14,725 INFO L413 NwaCegarLoop]: 54 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 54 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:14,726 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 14:35:14,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-07-22 14:35:14,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-07-22 14:35:14,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 28 states have (on average 1.3928571428571428) internal successors, (39), 29 states have internal predecessors, (39), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-22 14:35:14,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 50 transitions. [2022-07-22 14:35:14,772 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 50 transitions. Word has length 20 [2022-07-22 14:35:14,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:14,773 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 50 transitions. [2022-07-22 14:35:14,774 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-22 14:35:14,774 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 50 transitions. [2022-07-22 14:35:14,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-07-22 14:35:14,776 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:14,776 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:14,777 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-22 14:35:14,777 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:14,778 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:14,778 INFO L85 PathProgramCache]: Analyzing trace with hash -751028367, now seen corresponding path program 1 times [2022-07-22 14:35:14,778 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:14,778 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1209499264] [2022-07-22 14:35:14,778 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:14,779 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:14,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:14,944 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:14,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:14,952 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 14:35:14,952 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:14,952 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1209499264] [2022-07-22 14:35:14,952 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1209499264] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:14,953 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:14,953 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-22 14:35:14,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [232463781] [2022-07-22 14:35:14,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:14,955 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 14:35:14,955 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:14,956 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 14:35:14,956 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-22 14:35:14,957 INFO L87 Difference]: Start difference. First operand 37 states and 50 transitions. Second operand has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-22 14:35:14,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:14,999 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2022-07-22 14:35:14,999 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-22 14:35:14,999 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 20 [2022-07-22 14:35:15,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:15,001 INFO L225 Difference]: With dead ends: 45 [2022-07-22 14:35:15,001 INFO L226 Difference]: Without dead ends: 43 [2022-07-22 14:35:15,001 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-22 14:35:15,002 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 6 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 181 SdHoareTripleChecker+Invalid, 20 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:15,003 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 181 Invalid, 20 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 14:35:15,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2022-07-22 14:35:15,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2022-07-22 14:35:15,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 31 states have (on average 1.3548387096774193) internal successors, (42), 33 states have internal predecessors, (42), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-07-22 14:35:15,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 55 transitions. [2022-07-22 14:35:15,010 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 55 transitions. Word has length 20 [2022-07-22 14:35:15,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:15,011 INFO L495 AbstractCegarLoop]: Abstraction has 42 states and 55 transitions. [2022-07-22 14:35:15,012 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-22 14:35:15,012 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 55 transitions. [2022-07-22 14:35:15,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-07-22 14:35:15,013 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:15,013 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:15,013 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-07-22 14:35:15,014 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:15,014 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:15,014 INFO L85 PathProgramCache]: Analyzing trace with hash 789210768, now seen corresponding path program 1 times [2022-07-22 14:35:15,015 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:15,015 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971917443] [2022-07-22 14:35:15,015 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:15,015 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:15,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:15,071 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:15,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:15,088 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2022-07-22 14:35:15,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:15,093 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-22 14:35:15,093 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:15,093 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1971917443] [2022-07-22 14:35:15,093 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1971917443] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:15,094 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:15,094 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-22 14:35:15,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1745721747] [2022-07-22 14:35:15,094 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:15,094 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-22 14:35:15,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:15,095 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-22 14:35:15,095 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-22 14:35:15,096 INFO L87 Difference]: Start difference. First operand 42 states and 55 transitions. Second operand has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-22 14:35:15,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:15,135 INFO L93 Difference]: Finished difference Result 86 states and 116 transitions. [2022-07-22 14:35:15,136 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-22 14:35:15,136 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 26 [2022-07-22 14:35:15,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:15,137 INFO L225 Difference]: With dead ends: 86 [2022-07-22 14:35:15,137 INFO L226 Difference]: Without dead ends: 63 [2022-07-22 14:35:15,138 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2022-07-22 14:35:15,139 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 15 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:15,139 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 134 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 14:35:15,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-07-22 14:35:15,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2022-07-22 14:35:15,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 42 states have (on average 1.380952380952381) internal successors, (58), 44 states have internal predecessors, (58), 8 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-22 14:35:15,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 73 transitions. [2022-07-22 14:35:15,147 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 73 transitions. Word has length 26 [2022-07-22 14:35:15,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:15,148 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 73 transitions. [2022-07-22 14:35:15,148 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-22 14:35:15,148 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 73 transitions. [2022-07-22 14:35:15,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-07-22 14:35:15,149 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:15,149 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:15,150 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-07-22 14:35:15,150 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:15,150 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:15,150 INFO L85 PathProgramCache]: Analyzing trace with hash 860755832, now seen corresponding path program 1 times [2022-07-22 14:35:15,151 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:15,151 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1524621533] [2022-07-22 14:35:15,151 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:15,151 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:15,173 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:15,204 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 14:35:15,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:15,228 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2022-07-22 14:35:15,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:15,233 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-22 14:35:15,234 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:15,234 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1524621533] [2022-07-22 14:35:15,234 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1524621533] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 14:35:15,234 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [53572614] [2022-07-22 14:35:15,235 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:15,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:35:15,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 14:35:15,239 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 14:35:15,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-07-22 14:35:15,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:15,379 INFO L263 TraceCheckSpWp]: Trace formula consists of 235 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-22 14:35:15,388 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 14:35:15,497 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 14:35:15,498 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 14:35:15,640 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-22 14:35:15,643 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [53572614] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 14:35:15,644 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 14:35:15,644 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 16 [2022-07-22 14:35:15,644 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [272596710] [2022-07-22 14:35:15,644 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 14:35:15,645 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-07-22 14:35:15,645 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:15,647 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-07-22 14:35:15,647 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2022-07-22 14:35:15,648 INFO L87 Difference]: Start difference. First operand 54 states and 73 transitions. Second operand has 16 states, 16 states have (on average 2.625) internal successors, (42), 16 states have internal predecessors, (42), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2022-07-22 14:35:15,945 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:15,945 INFO L93 Difference]: Finished difference Result 118 states and 165 transitions. [2022-07-22 14:35:15,946 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-22 14:35:15,946 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.625) internal successors, (42), 16 states have internal predecessors, (42), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) Word has length 29 [2022-07-22 14:35:15,946 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:15,948 INFO L225 Difference]: With dead ends: 118 [2022-07-22 14:35:15,948 INFO L226 Difference]: Without dead ends: 82 [2022-07-22 14:35:15,949 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2022-07-22 14:35:15,957 INFO L413 NwaCegarLoop]: 80 mSDtfsCounter, 132 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 338 SdHoareTripleChecker+Invalid, 262 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:15,958 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [134 Valid, 338 Invalid, 262 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 205 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-22 14:35:15,958 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2022-07-22 14:35:15,967 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 63. [2022-07-22 14:35:15,972 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 48 states have (on average 1.375) internal successors, (66), 52 states have internal predecessors, (66), 10 states have call successors, (10), 3 states have call predecessors, (10), 4 states have return successors, (12), 7 states have call predecessors, (12), 9 states have call successors, (12) [2022-07-22 14:35:15,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 88 transitions. [2022-07-22 14:35:15,978 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 88 transitions. Word has length 29 [2022-07-22 14:35:15,978 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:15,978 INFO L495 AbstractCegarLoop]: Abstraction has 63 states and 88 transitions. [2022-07-22 14:35:15,978 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.625) internal successors, (42), 16 states have internal predecessors, (42), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2022-07-22 14:35:15,979 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 88 transitions. [2022-07-22 14:35:15,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2022-07-22 14:35:15,985 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:15,985 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:16,011 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-07-22 14:35:16,199 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:35:16,200 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:16,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:16,200 INFO L85 PathProgramCache]: Analyzing trace with hash 162961828, now seen corresponding path program 1 times [2022-07-22 14:35:16,201 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:16,201 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2060005606] [2022-07-22 14:35:16,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:16,201 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:16,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,291 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 14:35:16,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,296 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-07-22 14:35:16,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,318 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-22 14:35:16,318 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:16,318 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2060005606] [2022-07-22 14:35:16,318 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2060005606] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:16,318 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:16,319 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-07-22 14:35:16,322 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [255657494] [2022-07-22 14:35:16,322 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:16,322 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-22 14:35:16,322 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:16,323 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-22 14:35:16,323 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-07-22 14:35:16,327 INFO L87 Difference]: Start difference. First operand 63 states and 88 transitions. Second operand has 7 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-07-22 14:35:16,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:16,403 INFO L93 Difference]: Finished difference Result 75 states and 105 transitions. [2022-07-22 14:35:16,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-22 14:35:16,404 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 31 [2022-07-22 14:35:16,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:16,406 INFO L225 Difference]: With dead ends: 75 [2022-07-22 14:35:16,406 INFO L226 Difference]: Without dead ends: 73 [2022-07-22 14:35:16,407 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-07-22 14:35:16,408 INFO L413 NwaCegarLoop]: 53 mSDtfsCounter, 7 mSDsluCounter, 236 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 289 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:16,409 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 289 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 14:35:16,410 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2022-07-22 14:35:16,430 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2022-07-22 14:35:16,430 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 53 states have (on average 1.3396226415094339) internal successors, (71), 58 states have internal predecessors, (71), 11 states have call successors, (11), 4 states have call predecessors, (11), 6 states have return successors, (19), 8 states have call predecessors, (19), 10 states have call successors, (19) [2022-07-22 14:35:16,431 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 101 transitions. [2022-07-22 14:35:16,431 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 101 transitions. Word has length 31 [2022-07-22 14:35:16,431 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:16,431 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 101 transitions. [2022-07-22 14:35:16,431 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-07-22 14:35:16,432 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 101 transitions. [2022-07-22 14:35:16,432 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-07-22 14:35:16,432 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:16,433 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 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, 1] [2022-07-22 14:35:16,433 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2022-07-22 14:35:16,433 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:16,433 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:16,433 INFO L85 PathProgramCache]: Analyzing trace with hash 786337177, now seen corresponding path program 1 times [2022-07-22 14:35:16,434 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:16,434 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1703175322] [2022-07-22 14:35:16,434 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:16,434 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:16,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,555 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 14:35:16,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,568 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2022-07-22 14:35:16,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,576 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:16,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,582 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-07-22 14:35:16,583 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:16,583 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1703175322] [2022-07-22 14:35:16,583 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1703175322] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 14:35:16,583 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1520929972] [2022-07-22 14:35:16,583 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:16,583 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:35:16,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 14:35:16,585 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 14:35:16,586 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-07-22 14:35:16,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:16,702 INFO L263 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 50 conjunts are in the unsatisfiable core [2022-07-22 14:35:16,706 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 14:35:16,764 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:16,771 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2022-07-22 14:35:16,782 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:16,783 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2022-07-22 14:35:16,790 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:16,792 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2022-07-22 14:35:16,797 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:16,798 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2022-07-22 14:35:16,962 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2022-07-22 14:35:16,968 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2022-07-22 14:35:16,985 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 9 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-22 14:35:16,986 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 14:35:17,048 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 4 [2022-07-22 14:35:17,196 INFO L356 Elim1Store]: treesize reduction 21, result has 47.5 percent of original size [2022-07-22 14:35:17,197 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 31 [2022-07-22 14:35:17,204 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 24 [2022-07-22 14:35:17,207 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2022-07-22 14:35:17,216 INFO L356 Elim1Store]: treesize reduction 39, result has 2.5 percent of original size [2022-07-22 14:35:17,216 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 1 [2022-07-22 14:35:17,244 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2022-07-22 14:35:17,245 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1520929972] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 14:35:17,245 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 14:35:17,245 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 8, 7] total 16 [2022-07-22 14:35:17,245 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [91708579] [2022-07-22 14:35:17,245 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 14:35:17,247 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-07-22 14:35:17,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:17,248 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-07-22 14:35:17,248 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=204, Unknown=0, NotChecked=0, Total=240 [2022-07-22 14:35:17,248 INFO L87 Difference]: Start difference. First operand 71 states and 101 transitions. Second operand has 16 states, 16 states have (on average 3.4375) internal successors, (55), 15 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2022-07-22 14:35:17,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:17,785 INFO L93 Difference]: Finished difference Result 269 states and 401 transitions. [2022-07-22 14:35:17,785 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2022-07-22 14:35:17,786 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.4375) internal successors, (55), 15 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) Word has length 37 [2022-07-22 14:35:17,786 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:17,788 INFO L225 Difference]: With dead ends: 269 [2022-07-22 14:35:17,789 INFO L226 Difference]: Without dead ends: 198 [2022-07-22 14:35:17,790 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 73 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 101 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=162, Invalid=708, Unknown=0, NotChecked=0, Total=870 [2022-07-22 14:35:17,791 INFO L413 NwaCegarLoop]: 103 mSDtfsCounter, 193 mSDsluCounter, 778 mSDsCounter, 0 mSdLazyCounter, 381 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 199 SdHoareTripleChecker+Valid, 881 SdHoareTripleChecker+Invalid, 485 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 381 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 55 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:17,791 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [199 Valid, 881 Invalid, 485 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 381 Invalid, 0 Unknown, 55 Unchecked, 0.3s Time] [2022-07-22 14:35:17,795 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2022-07-22 14:35:17,819 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 90. [2022-07-22 14:35:17,821 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 69 states have (on average 1.3333333333333333) internal successors, (92), 74 states have internal predecessors, (92), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (20), 10 states have call predecessors, (20), 12 states have call successors, (20) [2022-07-22 14:35:17,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 125 transitions. [2022-07-22 14:35:17,823 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 125 transitions. Word has length 37 [2022-07-22 14:35:17,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:17,824 INFO L495 AbstractCegarLoop]: Abstraction has 90 states and 125 transitions. [2022-07-22 14:35:17,825 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.4375) internal successors, (55), 15 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2022-07-22 14:35:17,825 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 125 transitions. [2022-07-22 14:35:17,826 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-22 14:35:17,826 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:17,826 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:17,854 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-07-22 14:35:18,047 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2022-07-22 14:35:18,048 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:18,048 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:18,048 INFO L85 PathProgramCache]: Analyzing trace with hash -1693334873, now seen corresponding path program 1 times [2022-07-22 14:35:18,049 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:18,049 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [958353622] [2022-07-22 14:35:18,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:18,049 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:18,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,137 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:18,140 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,148 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2022-07-22 14:35:18,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,153 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-22 14:35:18,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,158 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-22 14:35:18,159 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:18,159 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [958353622] [2022-07-22 14:35:18,159 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [958353622] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:18,159 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:18,160 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-22 14:35:18,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1204461948] [2022-07-22 14:35:18,160 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:18,160 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 14:35:18,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:18,161 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 14:35:18,161 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-22 14:35:18,161 INFO L87 Difference]: Start difference. First operand 90 states and 125 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 14:35:18,277 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:18,277 INFO L93 Difference]: Finished difference Result 133 states and 181 transitions. [2022-07-22 14:35:18,278 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-22 14:35:18,278 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 35 [2022-07-22 14:35:18,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:18,279 INFO L225 Difference]: With dead ends: 133 [2022-07-22 14:35:18,279 INFO L226 Difference]: Without dead ends: 102 [2022-07-22 14:35:18,280 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2022-07-22 14:35:18,281 INFO L413 NwaCegarLoop]: 50 mSDtfsCounter, 20 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 59 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 165 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 59 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:18,281 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [20 Valid, 165 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 59 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-22 14:35:18,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2022-07-22 14:35:18,300 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 92. [2022-07-22 14:35:18,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 71 states have (on average 1.323943661971831) internal successors, (94), 76 states have internal predecessors, (94), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (20), 10 states have call predecessors, (20), 12 states have call successors, (20) [2022-07-22 14:35:18,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 127 transitions. [2022-07-22 14:35:18,302 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 127 transitions. Word has length 35 [2022-07-22 14:35:18,302 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:18,302 INFO L495 AbstractCegarLoop]: Abstraction has 92 states and 127 transitions. [2022-07-22 14:35:18,302 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 14:35:18,302 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 127 transitions. [2022-07-22 14:35:18,305 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-22 14:35:18,305 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:18,306 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:18,306 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2022-07-22 14:35:18,306 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:18,306 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:18,306 INFO L85 PathProgramCache]: Analyzing trace with hash -1474480155, now seen corresponding path program 1 times [2022-07-22 14:35:18,306 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:18,307 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1652711642] [2022-07-22 14:35:18,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:18,307 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:18,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,372 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:18,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,375 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2022-07-22 14:35:18,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,377 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-22 14:35:18,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,394 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-07-22 14:35:18,394 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:18,395 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1652711642] [2022-07-22 14:35:18,395 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1652711642] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:18,395 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:18,395 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-07-22 14:35:18,395 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [892859614] [2022-07-22 14:35:18,395 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:18,396 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-07-22 14:35:18,396 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:18,397 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-22 14:35:18,397 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-07-22 14:35:18,397 INFO L87 Difference]: Start difference. First operand 92 states and 127 transitions. Second operand has 6 states, 5 states have (on average 5.4) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-22 14:35:18,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:18,435 INFO L93 Difference]: Finished difference Result 99 states and 133 transitions. [2022-07-22 14:35:18,435 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-22 14:35:18,435 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 5.4) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 35 [2022-07-22 14:35:18,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:18,436 INFO L225 Difference]: With dead ends: 99 [2022-07-22 14:35:18,436 INFO L226 Difference]: Without dead ends: 92 [2022-07-22 14:35:18,436 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-07-22 14:35:18,437 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 5 mSDsluCounter, 186 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:18,437 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 237 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 14:35:18,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-07-22 14:35:18,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 80. [2022-07-22 14:35:18,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 63 states have (on average 1.3333333333333333) internal successors, (84), 66 states have internal predecessors, (84), 10 states have call successors, (10), 4 states have call predecessors, (10), 6 states have return successors, (15), 9 states have call predecessors, (15), 9 states have call successors, (15) [2022-07-22 14:35:18,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 109 transitions. [2022-07-22 14:35:18,446 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 109 transitions. Word has length 35 [2022-07-22 14:35:18,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:18,446 INFO L495 AbstractCegarLoop]: Abstraction has 80 states and 109 transitions. [2022-07-22 14:35:18,446 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 5.4) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-22 14:35:18,446 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 109 transitions. [2022-07-22 14:35:18,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-07-22 14:35:18,447 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:18,448 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:18,448 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2022-07-22 14:35:18,448 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:18,448 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:18,449 INFO L85 PathProgramCache]: Analyzing trace with hash 1846747895, now seen corresponding path program 1 times [2022-07-22 14:35:18,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:18,449 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [535985658] [2022-07-22 14:35:18,449 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:18,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:18,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,478 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:18,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,481 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2022-07-22 14:35:18,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,484 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-22 14:35:18,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,507 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-22 14:35:18,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:18,508 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [535985658] [2022-07-22 14:35:18,508 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [535985658] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:18,508 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:18,508 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-22 14:35:18,508 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1696127173] [2022-07-22 14:35:18,508 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:18,509 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 14:35:18,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:18,509 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 14:35:18,509 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-22 14:35:18,510 INFO L87 Difference]: Start difference. First operand 80 states and 109 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-22 14:35:18,565 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:18,565 INFO L93 Difference]: Finished difference Result 130 states and 171 transitions. [2022-07-22 14:35:18,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-22 14:35:18,566 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 36 [2022-07-22 14:35:18,566 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:18,568 INFO L225 Difference]: With dead ends: 130 [2022-07-22 14:35:18,569 INFO L226 Difference]: Without dead ends: 62 [2022-07-22 14:35:18,570 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-22 14:35:18,572 INFO L413 NwaCegarLoop]: 42 mSDtfsCounter, 16 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:18,573 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 144 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 14:35:18,573 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2022-07-22 14:35:18,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 60. [2022-07-22 14:35:18,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 46 states have (on average 1.3043478260869565) internal successors, (60), 48 states have internal predecessors, (60), 8 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (11), 7 states have call predecessors, (11), 7 states have call successors, (11) [2022-07-22 14:35:18,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 79 transitions. [2022-07-22 14:35:18,581 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 79 transitions. Word has length 36 [2022-07-22 14:35:18,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:18,581 INFO L495 AbstractCegarLoop]: Abstraction has 60 states and 79 transitions. [2022-07-22 14:35:18,582 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2022-07-22 14:35:18,582 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 79 transitions. [2022-07-22 14:35:18,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-07-22 14:35:18,582 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:18,582 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:18,582 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2022-07-22 14:35:18,583 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:18,583 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:18,583 INFO L85 PathProgramCache]: Analyzing trace with hash -827934680, now seen corresponding path program 1 times [2022-07-22 14:35:18,583 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:18,583 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [740980299] [2022-07-22 14:35:18,583 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:18,583 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:18,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,685 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 14:35:18,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,737 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:18,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,762 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2022-07-22 14:35:18,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,767 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:18,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,769 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-22 14:35:18,770 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:18,770 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [740980299] [2022-07-22 14:35:18,770 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [740980299] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 14:35:18,770 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1264392901] [2022-07-22 14:35:18,770 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:18,770 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:35:18,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 14:35:18,772 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 14:35:18,795 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-07-22 14:35:18,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:18,908 INFO L263 TraceCheckSpWp]: Trace formula consists of 357 conjuncts, 45 conjunts are in the unsatisfiable core [2022-07-22 14:35:18,912 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 14:35:18,923 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2022-07-22 14:35:18,948 INFO L356 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2022-07-22 14:35:18,949 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2022-07-22 14:35:18,985 INFO L356 Elim1Store]: treesize reduction 30, result has 38.8 percent of original size [2022-07-22 14:35:18,986 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 78 [2022-07-22 14:35:18,992 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2022-07-22 14:35:19,003 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2022-07-22 14:35:19,060 INFO L356 Elim1Store]: treesize reduction 35, result has 2.8 percent of original size [2022-07-22 14:35:19,061 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 102 treesize of output 46 [2022-07-22 14:35:19,063 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2022-07-22 14:35:19,069 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse3 (select (select |c_#memory_$Pointer$.base| |c_ULTIMATE.start_main_~#list~0#1.base|) (+ |c_ULTIMATE.start_main_~#list~0#1.offset| 4)))) (let ((.cse2 (not (= .cse3 |c_ULTIMATE.start_main_~x~0#1.base|)))) (or (and (exists ((v_DerPreprocessor_1 (Array Int Int)) (v_DerPreprocessor_2 (Array Int Int))) (let ((.cse1 (+ |c_ULTIMATE.start_main_~#list~0#1.offset| 4))) (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_ULTIMATE.start_main_~#list~0#1.base|) .cse1))) (and (= (select (store (store (store (store |c_#memory_$Pointer$.base| .cse0 v_DerPreprocessor_1) |c_ULTIMATE.start_main_~#list~0#1.base| v_DerPreprocessor_2) .cse0 v_DerPreprocessor_1) |c_ULTIMATE.start_main_~#list~0#1.base| v_DerPreprocessor_2) .cse0) v_DerPreprocessor_1) (= .cse0 (select v_DerPreprocessor_2 .cse1)))))) .cse2) (and .cse2 (not (= .cse3 |c_ULTIMATE.start_main_~#list~0#1.base|)))))) is different from true [2022-07-22 14:35:19,143 WARN L855 $PredicateComparison]: unable to prove that (or (exists ((|v_ULTIMATE.start_main_~#list~0#1.base_BEFORE_CALL_3| Int) (|v_ULTIMATE.start_main_~#list~0#1.offset_BEFORE_CALL_1| Int)) (not (= (select (select |c_#memory_$Pointer$.base| |v_ULTIMATE.start_main_~#list~0#1.base_BEFORE_CALL_3|) (+ |v_ULTIMATE.start_main_~#list~0#1.offset_BEFORE_CALL_1| 4)) |v_ULTIMATE.start_main_~#list~0#1.base_BEFORE_CALL_3|))) (exists ((v_DerPreprocessor_1 (Array Int Int)) (v_DerPreprocessor_2 (Array Int Int)) (|v_ULTIMATE.start_main_~#list~0#1.base_BEFORE_CALL_3| Int) (|v_ULTIMATE.start_main_~#list~0#1.offset_BEFORE_CALL_1| Int)) (let ((.cse1 (+ |v_ULTIMATE.start_main_~#list~0#1.offset_BEFORE_CALL_1| 4))) (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |v_ULTIMATE.start_main_~#list~0#1.base_BEFORE_CALL_3|) .cse1))) (and (= (select (store (store (store (store |c_#memory_$Pointer$.base| .cse0 v_DerPreprocessor_1) |v_ULTIMATE.start_main_~#list~0#1.base_BEFORE_CALL_3| v_DerPreprocessor_2) .cse0 v_DerPreprocessor_1) |v_ULTIMATE.start_main_~#list~0#1.base_BEFORE_CALL_3| v_DerPreprocessor_2) .cse0) v_DerPreprocessor_1) (= (select v_DerPreprocessor_2 .cse1) .cse0)))))) is different from true [2022-07-22 14:35:29,536 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 20 proven. 4 refuted. 0 times theorem prover too weak. 5 trivial. 3 not checked. [2022-07-22 14:35:29,536 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 14:35:29,725 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-22 14:35:29,726 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 124 treesize of output 127 [2022-07-22 14:35:29,730 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 152 treesize of output 144 [2022-07-22 14:35:29,741 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 144 treesize of output 140 [2022-07-22 14:35:29,786 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2022-07-22 14:35:29,796 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 26 [2022-07-22 14:35:29,928 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2022-07-22 14:35:29,928 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1264392901] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 14:35:29,928 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 14:35:29,929 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 12] total 24 [2022-07-22 14:35:29,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [947255613] [2022-07-22 14:35:29,929 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 14:35:29,929 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-07-22 14:35:29,929 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:29,930 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-07-22 14:35:29,930 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=385, Unknown=13, NotChecked=82, Total=552 [2022-07-22 14:35:29,930 INFO L87 Difference]: Start difference. First operand 60 states and 79 transitions. Second operand has 24 states, 21 states have (on average 2.9047619047619047) internal successors, (61), 23 states have internal predecessors, (61), 7 states have call successors, (10), 3 states have call predecessors, (10), 6 states have return successors, (9), 4 states have call predecessors, (9), 7 states have call successors, (9) [2022-07-22 14:35:32,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:32,697 INFO L93 Difference]: Finished difference Result 186 states and 269 transitions. [2022-07-22 14:35:32,697 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-07-22 14:35:32,698 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 21 states have (on average 2.9047619047619047) internal successors, (61), 23 states have internal predecessors, (61), 7 states have call successors, (10), 3 states have call predecessors, (10), 6 states have return successors, (9), 4 states have call predecessors, (9), 7 states have call successors, (9) Word has length 46 [2022-07-22 14:35:32,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:32,699 INFO L225 Difference]: With dead ends: 186 [2022-07-22 14:35:32,699 INFO L226 Difference]: Without dead ends: 145 [2022-07-22 14:35:32,699 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 85 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 203 ImplicationChecksByTransitivity, 12.6s TimeCoverageRelationStatistics Valid=152, Invalid=823, Unknown=25, NotChecked=122, Total=1122 [2022-07-22 14:35:32,700 INFO L413 NwaCegarLoop]: 96 mSDtfsCounter, 109 mSDsluCounter, 885 mSDsCounter, 0 mSdLazyCounter, 734 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 115 SdHoareTripleChecker+Valid, 981 SdHoareTripleChecker+Invalid, 1398 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 734 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 622 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:32,700 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [115 Valid, 981 Invalid, 1398 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 734 Invalid, 0 Unknown, 622 Unchecked, 0.5s Time] [2022-07-22 14:35:32,700 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2022-07-22 14:35:32,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 99. [2022-07-22 14:35:32,714 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 74 states have (on average 1.3243243243243243) internal successors, (98), 79 states have internal predecessors, (98), 15 states have call successors, (15), 5 states have call predecessors, (15), 9 states have return successors, (27), 14 states have call predecessors, (27), 14 states have call successors, (27) [2022-07-22 14:35:32,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 140 transitions. [2022-07-22 14:35:32,714 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 140 transitions. Word has length 46 [2022-07-22 14:35:32,715 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:32,715 INFO L495 AbstractCegarLoop]: Abstraction has 99 states and 140 transitions. [2022-07-22 14:35:32,715 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 21 states have (on average 2.9047619047619047) internal successors, (61), 23 states have internal predecessors, (61), 7 states have call successors, (10), 3 states have call predecessors, (10), 6 states have return successors, (9), 4 states have call predecessors, (9), 7 states have call successors, (9) [2022-07-22 14:35:32,715 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 140 transitions. [2022-07-22 14:35:32,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-07-22 14:35:32,716 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:32,716 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:32,744 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-07-22 14:35:32,942 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:35:32,942 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:32,942 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:32,943 INFO L85 PathProgramCache]: Analyzing trace with hash 828672736, now seen corresponding path program 1 times [2022-07-22 14:35:32,943 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:32,943 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424175921] [2022-07-22 14:35:32,943 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:32,943 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:32,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:32,991 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 14:35:32,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:32,995 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:32,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:32,997 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-22 14:35:33,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,015 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:33,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,021 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2022-07-22 14:35:33,022 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:33,022 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424175921] [2022-07-22 14:35:33,022 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1424175921] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 14:35:33,022 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 14:35:33,022 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-07-22 14:35:33,022 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [906167991] [2022-07-22 14:35:33,022 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 14:35:33,023 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-22 14:35:33,023 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:35:33,023 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-22 14:35:33,024 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2022-07-22 14:35:33,024 INFO L87 Difference]: Start difference. First operand 99 states and 140 transitions. Second operand has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 5 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 14:35:33,096 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:35:33,097 INFO L93 Difference]: Finished difference Result 123 states and 175 transitions. [2022-07-22 14:35:33,097 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-22 14:35:33,097 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 5 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) Word has length 44 [2022-07-22 14:35:33,097 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:35:33,098 INFO L225 Difference]: With dead ends: 123 [2022-07-22 14:35:33,098 INFO L226 Difference]: Without dead ends: 121 [2022-07-22 14:35:33,099 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-07-22 14:35:33,099 INFO L413 NwaCegarLoop]: 52 mSDtfsCounter, 7 mSDsluCounter, 279 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 331 SdHoareTripleChecker+Invalid, 68 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 14:35:33,099 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 331 Invalid, 68 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 14:35:33,100 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2022-07-22 14:35:33,111 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 102. [2022-07-22 14:35:33,111 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 76 states have (on average 1.3157894736842106) internal successors, (100), 81 states have internal predecessors, (100), 15 states have call successors, (15), 5 states have call predecessors, (15), 10 states have return successors, (35), 15 states have call predecessors, (35), 14 states have call successors, (35) [2022-07-22 14:35:33,112 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 150 transitions. [2022-07-22 14:35:33,112 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 150 transitions. Word has length 44 [2022-07-22 14:35:33,112 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:35:33,112 INFO L495 AbstractCegarLoop]: Abstraction has 102 states and 150 transitions. [2022-07-22 14:35:33,112 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 5 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 14:35:33,112 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 150 transitions. [2022-07-22 14:35:33,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-07-22 14:35:33,113 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:35:33,113 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:35:33,113 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2022-07-22 14:35:33,113 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:35:33,114 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:35:33,114 INFO L85 PathProgramCache]: Analyzing trace with hash 604583819, now seen corresponding path program 1 times [2022-07-22 14:35:33,114 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:35:33,114 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [515293634] [2022-07-22 14:35:33,114 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:33,114 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:35:33,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,365 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 14:35:33,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,371 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:33,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,373 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-22 14:35:33,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,443 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:33,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,448 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:35:33,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,457 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2022-07-22 14:35:33,457 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:35:33,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [515293634] [2022-07-22 14:35:33,457 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [515293634] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 14:35:33,457 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1268208496] [2022-07-22 14:35:33,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:35:33,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:35:33,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 14:35:33,459 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 14:35:33,463 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-07-22 14:35:33,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:35:33,590 INFO L263 TraceCheckSpWp]: Trace formula consists of 325 conjuncts, 91 conjunts are in the unsatisfiable core [2022-07-22 14:35:33,594 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 14:35:33,661 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:33,662 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2022-07-22 14:35:33,665 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:33,666 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2022-07-22 14:35:33,671 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:33,672 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2022-07-22 14:35:33,676 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:33,676 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 23 [2022-07-22 14:35:34,071 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:34,073 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:34,074 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-22 14:35:34,083 INFO L356 Elim1Store]: treesize reduction 19, result has 32.1 percent of original size [2022-07-22 14:35:34,083 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 79 treesize of output 62 [2022-07-22 14:35:34,090 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:34,091 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:35:34,097 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 88 treesize of output 71 [2022-07-22 14:35:52,512 WARN L233 SmtUtils]: Spent 6.03s on a formula simplification that was a NOOP. DAG size: 44 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-22 14:35:58,665 WARN L233 SmtUtils]: Spent 6.04s on a formula simplification that was a NOOP. DAG size: 52 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-22 14:36:08,074 WARN L233 SmtUtils]: Spent 6.04s on a formula simplification that was a NOOP. DAG size: 44 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-22 14:36:14,205 WARN L233 SmtUtils]: Spent 6.02s on a formula simplification that was a NOOP. DAG size: 49 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-22 14:36:14,413 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 36 proven. 9 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-07-22 14:36:14,422 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 14:36:14,573 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1268208496] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 14:36:14,573 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 14:36:14,574 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 21] total 33 [2022-07-22 14:36:14,574 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1626145057] [2022-07-22 14:36:14,574 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 14:36:14,574 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2022-07-22 14:36:14,575 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:36:14,575 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2022-07-22 14:36:14,575 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=121, Invalid=994, Unknown=7, NotChecked=0, Total=1122 [2022-07-22 14:36:14,576 INFO L87 Difference]: Start difference. First operand 102 states and 150 transitions. Second operand has 33 states, 30 states have (on average 2.033333333333333) internal successors, (61), 31 states have internal predecessors, (61), 10 states have call successors, (10), 5 states have call predecessors, (10), 6 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-22 14:36:28,456 WARN L233 SmtUtils]: Spent 6.02s on a formula simplification that was a NOOP. DAG size: 50 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-22 14:36:35,649 WARN L233 SmtUtils]: Spent 6.11s on a formula simplification. DAG size of input: 66 DAG size of output: 60 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-07-22 14:36:36,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:36:36,115 INFO L93 Difference]: Finished difference Result 307 states and 476 transitions. [2022-07-22 14:36:36,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2022-07-22 14:36:36,116 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 30 states have (on average 2.033333333333333) internal successors, (61), 31 states have internal predecessors, (61), 10 states have call successors, (10), 5 states have call predecessors, (10), 6 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) Word has length 50 [2022-07-22 14:36:36,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:36:36,118 INFO L225 Difference]: With dead ends: 307 [2022-07-22 14:36:36,118 INFO L226 Difference]: Without dead ends: 256 [2022-07-22 14:36:36,119 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 48 SyntacticMatches, 1 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 842 ImplicationChecksByTransitivity, 61.0s TimeCoverageRelationStatistics Valid=389, Invalid=2903, Unknown=14, NotChecked=0, Total=3306 [2022-07-22 14:36:36,120 INFO L413 NwaCegarLoop]: 96 mSDtfsCounter, 139 mSDsluCounter, 1088 mSDsCounter, 0 mSdLazyCounter, 932 mSolverCounterSat, 107 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 143 SdHoareTripleChecker+Valid, 1184 SdHoareTripleChecker+Invalid, 1560 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 107 IncrementalHoareTripleChecker+Valid, 932 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 521 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-07-22 14:36:36,120 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [143 Valid, 1184 Invalid, 1560 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [107 Valid, 932 Invalid, 0 Unknown, 521 Unchecked, 0.8s Time] [2022-07-22 14:36:36,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 256 states. [2022-07-22 14:36:36,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 256 to 156. [2022-07-22 14:36:36,158 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 156 states, 118 states have (on average 1.305084745762712) internal successors, (154), 125 states have internal predecessors, (154), 22 states have call successors, (22), 7 states have call predecessors, (22), 15 states have return successors, (53), 23 states have call predecessors, (53), 21 states have call successors, (53) [2022-07-22 14:36:36,159 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 229 transitions. [2022-07-22 14:36:36,160 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 229 transitions. Word has length 50 [2022-07-22 14:36:36,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:36:36,161 INFO L495 AbstractCegarLoop]: Abstraction has 156 states and 229 transitions. [2022-07-22 14:36:36,161 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 30 states have (on average 2.033333333333333) internal successors, (61), 31 states have internal predecessors, (61), 10 states have call successors, (10), 5 states have call predecessors, (10), 6 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-22 14:36:36,161 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 229 transitions. [2022-07-22 14:36:36,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-07-22 14:36:36,163 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:36:36,163 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:36:36,181 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-07-22 14:36:36,367 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:36:36,367 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:36:36,368 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:36:36,368 INFO L85 PathProgramCache]: Analyzing trace with hash -13848694, now seen corresponding path program 1 times [2022-07-22 14:36:36,368 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:36:36,368 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [845899919] [2022-07-22 14:36:36,368 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:36:36,368 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:36:36,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:36,466 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 14:36:36,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:36,473 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:36:36,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:36,475 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2022-07-22 14:36:36,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:36,478 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:36:36,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:36,480 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-07-22 14:36:36,480 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:36:36,480 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [845899919] [2022-07-22 14:36:36,480 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [845899919] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 14:36:36,480 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1265197723] [2022-07-22 14:36:36,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:36:36,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:36:36,481 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 14:36:36,482 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 14:36:36,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-07-22 14:36:36,607 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:36,609 INFO L263 TraceCheckSpWp]: Trace formula consists of 283 conjuncts, 43 conjunts are in the unsatisfiable core [2022-07-22 14:36:36,612 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 14:36:36,662 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:36,663 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2022-07-22 14:36:36,666 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:36,667 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2022-07-22 14:36:36,825 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 12 [2022-07-22 14:36:36,841 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 19 proven. 1 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-07-22 14:36:36,841 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 14:36:36,882 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 4 [2022-07-22 14:36:36,984 INFO L356 Elim1Store]: treesize reduction 21, result has 47.5 percent of original size [2022-07-22 14:36:36,984 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 23 treesize of output 29 [2022-07-22 14:36:36,987 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 22 [2022-07-22 14:36:36,989 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2022-07-22 14:36:37,044 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-07-22 14:36:37,044 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1265197723] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 14:36:37,044 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 14:36:37,045 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 9] total 23 [2022-07-22 14:36:37,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1562736970] [2022-07-22 14:36:37,045 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 14:36:37,045 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-07-22 14:36:37,045 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 14:36:37,046 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-22 14:36:37,046 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=441, Unknown=0, NotChecked=0, Total=506 [2022-07-22 14:36:37,046 INFO L87 Difference]: Start difference. First operand 156 states and 229 transitions. Second operand has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 23 states have internal predecessors, (60), 6 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-07-22 14:36:37,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 14:36:37,857 INFO L93 Difference]: Finished difference Result 301 states and 429 transitions. [2022-07-22 14:36:37,857 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-22 14:36:37,858 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 23 states have internal predecessors, (60), 6 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 43 [2022-07-22 14:36:37,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 14:36:37,859 INFO L225 Difference]: With dead ends: 301 [2022-07-22 14:36:37,860 INFO L226 Difference]: Without dead ends: 239 [2022-07-22 14:36:37,860 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 269 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=323, Invalid=1159, Unknown=0, NotChecked=0, Total=1482 [2022-07-22 14:36:37,861 INFO L413 NwaCegarLoop]: 88 mSDtfsCounter, 210 mSDsluCounter, 678 mSDsCounter, 0 mSdLazyCounter, 467 mSolverCounterSat, 76 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 213 SdHoareTripleChecker+Valid, 766 SdHoareTripleChecker+Invalid, 598 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 76 IncrementalHoareTripleChecker+Valid, 467 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 55 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-22 14:36:37,861 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [213 Valid, 766 Invalid, 598 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [76 Valid, 467 Invalid, 0 Unknown, 55 Unchecked, 0.3s Time] [2022-07-22 14:36:37,862 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 239 states. [2022-07-22 14:36:37,879 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 239 to 197. [2022-07-22 14:36:37,880 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 197 states, 151 states have (on average 1.2582781456953642) internal successors, (190), 156 states have internal predecessors, (190), 26 states have call successors, (26), 14 states have call predecessors, (26), 19 states have return successors, (52), 26 states have call predecessors, (52), 24 states have call successors, (52) [2022-07-22 14:36:37,881 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 197 states to 197 states and 268 transitions. [2022-07-22 14:36:37,881 INFO L78 Accepts]: Start accepts. Automaton has 197 states and 268 transitions. Word has length 43 [2022-07-22 14:36:37,881 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 14:36:37,881 INFO L495 AbstractCegarLoop]: Abstraction has 197 states and 268 transitions. [2022-07-22 14:36:37,881 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 23 states have internal predecessors, (60), 6 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-07-22 14:36:37,882 INFO L276 IsEmpty]: Start isEmpty. Operand 197 states and 268 transitions. [2022-07-22 14:36:37,882 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-22 14:36:37,883 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 14:36:37,883 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 14:36:37,911 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-07-22 14:36:38,100 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-07-22 14:36:38,100 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 14:36:38,101 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 14:36:38,101 INFO L85 PathProgramCache]: Analyzing trace with hash 191887930, now seen corresponding path program 1 times [2022-07-22 14:36:38,101 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 14:36:38,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1851710042] [2022-07-22 14:36:38,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:36:38,101 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 14:36:38,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:38,177 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 14:36:38,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:38,219 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:36:38,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:38,225 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2022-07-22 14:36:38,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:38,229 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 14:36:38,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:38,230 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2022-07-22 14:36:38,230 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 14:36:38,230 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1851710042] [2022-07-22 14:36:38,231 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1851710042] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 14:36:38,231 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1923238141] [2022-07-22 14:36:38,231 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 14:36:38,231 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 14:36:38,231 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 14:36:38,232 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 14:36:38,233 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-07-22 14:36:38,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 14:36:38,377 INFO L263 TraceCheckSpWp]: Trace formula consists of 362 conjuncts, 123 conjunts are in the unsatisfiable core [2022-07-22 14:36:38,385 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 14:36:38,423 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,423 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-22 14:36:38,424 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2022-07-22 14:36:38,426 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,427 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 23 [2022-07-22 14:36:38,437 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,437 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2022-07-22 14:36:38,441 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,441 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2022-07-22 14:36:38,559 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,597 INFO L356 Elim1Store]: treesize reduction 59, result has 32.2 percent of original size [2022-07-22 14:36:38,597 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 50 treesize of output 94 [2022-07-22 14:36:38,615 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,617 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,619 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-22 14:36:38,620 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-22 14:36:38,640 INFO L356 Elim1Store]: treesize reduction 50, result has 32.4 percent of original size [2022-07-22 14:36:38,640 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 52 treesize of output 46 [2022-07-22 14:36:38,649 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2022-07-22 14:36:38,658 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2022-07-22 14:36:38,675 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2022-07-22 14:36:38,726 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:38,735 INFO L356 Elim1Store]: treesize reduction 48, result has 9.4 percent of original size [2022-07-22 14:36:38,736 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 117 treesize of output 70 [2022-07-22 14:36:38,739 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 60 treesize of output 40 [2022-07-22 14:36:40,652 INFO L190 IndexEqualityManager]: detected not equals via solver [2022-07-22 14:36:40,655 INFO L173 IndexEqualityManager]: detected equality via solver [2022-07-22 14:36:41,318 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-22 14:36:41,323 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 19 select indices, 19 select index equivalence classes, 2 disjoint index pairs (out of 171 index pairs), introduced 19 new quantified variables, introduced 170 case distinctions, treesize of input 399 treesize of output 1207 [2022-07-22 14:36:41,923 INFO L356 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2022-07-22 14:36:41,924 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 11 select indices, 11 select index equivalence classes, 0 disjoint index pairs (out of 55 index pairs), introduced 14 new quantified variables, introduced 55 case distinctions, treesize of input 1219 treesize of output 1472 [2022-07-22 14:36:42,263 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 5 [2022-07-22 14:36:42,335 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 5 [2022-07-22 14:36:42,667 INFO L390 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 5