./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c --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/nla-digbench-scaling/egcd2-ll_unwindbound5.c -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 74e9855722264d342377b8ab219a69c32c582cc628f82167488f3dea5640534c --- Real Ultimate output --- This is Ultimate 0.2.2-?-791161d [2022-07-22 15:58:56,974 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-22 15:58:56,975 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-22 15:58:57,008 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-22 15:58:57,009 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-22 15:58:57,010 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-22 15:58:57,013 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-22 15:58:57,016 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-22 15:58:57,018 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-22 15:58:57,018 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-22 15:58:57,019 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-22 15:58:57,020 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-22 15:58:57,021 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-22 15:58:57,023 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-22 15:58:57,023 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-22 15:58:57,025 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-22 15:58:57,027 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-22 15:58:57,029 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-22 15:58:57,032 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-22 15:58:57,033 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-22 15:58:57,036 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-22 15:58:57,036 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-22 15:58:57,037 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-22 15:58:57,038 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-22 15:58:57,041 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-22 15:58:57,043 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-22 15:58:57,045 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-22 15:58:57,046 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-22 15:58:57,046 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-22 15:58:57,047 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-22 15:58:57,047 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-22 15:58:57,047 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-22 15:58:57,048 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-22 15:58:57,049 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-22 15:58:57,049 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-22 15:58:57,050 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-22 15:58:57,050 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-22 15:58:57,051 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-22 15:58:57,051 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-22 15:58:57,051 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-22 15:58:57,052 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-22 15:58:57,052 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-22 15:58:57,054 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-22 15:58:57,076 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-22 15:58:57,077 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-22 15:58:57,077 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-22 15:58:57,077 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-22 15:58:57,077 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-22 15:58:57,078 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-22 15:58:57,078 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-22 15:58:57,078 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-22 15:58:57,078 INFO L138 SettingsManager]: * Use SBE=true [2022-07-22 15:58:57,080 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-22 15:58:57,080 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-22 15:58:57,080 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-22 15:58:57,080 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-22 15:58:57,081 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-22 15:58:57,081 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-22 15:58:57,081 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-22 15:58:57,081 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-22 15:58:57,081 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-22 15:58:57,082 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-22 15:58:57,082 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-22 15:58:57,083 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-22 15:58:57,083 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-22 15:58:57,083 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-22 15:58:57,083 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-22 15:58:57,083 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-22 15:58:57,083 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-22 15:58:57,084 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-22 15:58:57,084 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-22 15:58:57,084 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-22 15:58:57,084 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-22 15:58:57,084 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-22 15:58:57,084 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-22 15:58:57,084 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-22 15:58:57,085 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 -> 74e9855722264d342377b8ab219a69c32c582cc628f82167488f3dea5640534c [2022-07-22 15:58:57,234 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-22 15:58:57,252 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-22 15:58:57,254 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-22 15:58:57,255 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-22 15:58:57,256 INFO L275 PluginConnector]: CDTParser initialized [2022-07-22 15:58:57,257 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2022-07-22 15:58:57,312 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c8cf59152/62f06382c0814b928fba15d27880e165/FLAG604338e7a [2022-07-22 15:58:57,641 INFO L306 CDTParser]: Found 1 translation units. [2022-07-22 15:58:57,641 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound5.c [2022-07-22 15:58:57,645 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c8cf59152/62f06382c0814b928fba15d27880e165/FLAG604338e7a [2022-07-22 15:58:58,080 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c8cf59152/62f06382c0814b928fba15d27880e165 [2022-07-22 15:58:58,082 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-22 15:58:58,083 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-22 15:58:58,085 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-22 15:58:58,085 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-22 15:58:58,097 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-22 15:58:58,098 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,099 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@49ec74de and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58, skipping insertion in model container [2022-07-22 15:58:58,099 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,105 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-22 15:58:58,120 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-22 15:58:58,274 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/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2022-07-22 15:58:58,296 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-22 15:58:58,302 INFO L203 MainTranslator]: Completed pre-run [2022-07-22 15:58:58,311 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/nla-digbench-scaling/egcd2-ll_unwindbound5.c[490,503] [2022-07-22 15:58:58,317 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-22 15:58:58,325 INFO L208 MainTranslator]: Completed translation [2022-07-22 15:58:58,325 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58 WrapperNode [2022-07-22 15:58:58,325 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-22 15:58:58,326 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-22 15:58:58,326 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-22 15:58:58,326 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-22 15:58:58,331 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,335 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,350 INFO L137 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2022-07-22 15:58:58,350 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-22 15:58:58,351 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-22 15:58:58,351 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-22 15:58:58,351 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-22 15:58:58,356 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,357 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,358 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,358 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,360 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,363 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,364 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,366 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-22 15:58:58,366 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-22 15:58:58,367 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-22 15:58:58,367 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-22 15:58:58,367 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (1/1) ... [2022-07-22 15:58:58,373 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-22 15:58:58,379 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:58:58,389 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 15:58:58,400 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 15:58:58,418 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-22 15:58:58,418 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-07-22 15:58:58,418 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-07-22 15:58:58,419 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-22 15:58:58,419 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-22 15:58:58,419 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-22 15:58:58,419 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-22 15:58:58,419 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-22 15:58:58,457 INFO L234 CfgBuilder]: Building ICFG [2022-07-22 15:58:58,458 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-22 15:58:58,557 INFO L275 CfgBuilder]: Performing block encoding [2022-07-22 15:58:58,560 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-22 15:58:58,561 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-07-22 15:58:58,562 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 03:58:58 BoogieIcfgContainer [2022-07-22 15:58:58,562 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-22 15:58:58,563 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-22 15:58:58,564 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-22 15:58:58,581 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-22 15:58:58,582 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.07 03:58:58" (1/3) ... [2022-07-22 15:58:58,582 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31f78666 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.07 03:58:58, skipping insertion in model container [2022-07-22 15:58:58,582 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 03:58:58" (2/3) ... [2022-07-22 15:58:58,583 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31f78666 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.07 03:58:58, skipping insertion in model container [2022-07-22 15:58:58,583 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 03:58:58" (3/3) ... [2022-07-22 15:58:58,584 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound5.c [2022-07-22 15:58:58,593 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-22 15:58:58,593 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-22 15:58:58,627 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-22 15:58:58,631 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@3f799ffb, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@7136a5ee [2022-07-22 15:58:58,635 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-22 15:58:58,638 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-22 15:58:58,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-07-22 15:58:58,643 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:58:58,643 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:58:58,644 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:58:58,647 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:58:58,647 INFO L85 PathProgramCache]: Analyzing trace with hash 1022199732, now seen corresponding path program 1 times [2022-07-22 15:58:58,653 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:58:58,656 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1157782847] [2022-07-22 15:58:58,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:58:58,657 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:58:58,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:58,739 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2022-07-22 15:58:58,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:58,743 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-07-22 15:58:58,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:58,747 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-07-22 15:58:58,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:58,750 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2022-07-22 15:58:58,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:58,753 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-22 15:58:58,754 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:58:58,754 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1157782847] [2022-07-22 15:58:58,754 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1157782847] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 15:58:58,755 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 15:58:58,755 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-22 15:58:58,756 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [980000323] [2022-07-22 15:58:58,756 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 15:58:58,759 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-22 15:58:58,763 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:58:58,779 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-22 15:58:58,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-22 15:58:58,780 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-22 15:58:58,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:58:58,794 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2022-07-22 15:58:58,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-22 15:58:58,795 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-07-22 15:58:58,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:58:58,799 INFO L225 Difference]: With dead ends: 65 [2022-07-22 15:58:58,799 INFO L226 Difference]: Without dead ends: 30 [2022-07-22 15:58:58,801 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 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 15:58:58,804 INFO L413 NwaCegarLoop]: 45 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, 45 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 15:58:58,805 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 15:58:58,815 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2022-07-22 15:58:58,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2022-07-22 15:58:58,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-22 15:58:58,829 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2022-07-22 15:58:58,830 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2022-07-22 15:58:58,830 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:58:58,830 INFO L495 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2022-07-22 15:58:58,830 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-22 15:58:58,831 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2022-07-22 15:58:58,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-07-22 15:58:58,832 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:58:58,832 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:58:58,832 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-22 15:58:58,833 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:58:58,833 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:58:58,833 INFO L85 PathProgramCache]: Analyzing trace with hash -455220980, now seen corresponding path program 1 times [2022-07-22 15:58:58,833 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:58:58,834 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1611702237] [2022-07-22 15:58:58,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:58:58,834 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:58:58,846 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:58:58,847 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2034695765] [2022-07-22 15:58:58,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:58:58,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:58:58,847 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:58:58,872 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 15:58:58,873 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 15:58:58,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:58,920 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 3 conjunts are in the unsatisfiable core [2022-07-22 15:58:58,923 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:58:58,993 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-22 15:58:58,993 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-22 15:58:58,993 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:58:58,993 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1611702237] [2022-07-22 15:58:58,994 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:58:58,994 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2034695765] [2022-07-22 15:58:58,994 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2034695765] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 15:58:58,994 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 15:58:58,994 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-22 15:58:58,995 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [672054766] [2022-07-22 15:58:58,995 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 15:58:58,996 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-22 15:58:58,996 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:58:58,996 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-22 15:58:58,996 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-22 15:58:58,997 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 15:58:59,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:58:59,010 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2022-07-22 15:58:59,010 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-22 15:58:59,011 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2022-07-22 15:58:59,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:58:59,011 INFO L225 Difference]: With dead ends: 40 [2022-07-22 15:58:59,011 INFO L226 Difference]: Without dead ends: 32 [2022-07-22 15:58:59,012 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-22 15:58:59,013 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 15:58:59,015 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 15:58:59,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-07-22 15:58:59,026 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-07-22 15:58:59,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-22 15:58:59,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2022-07-22 15:58:59,027 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2022-07-22 15:58:59,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:58:59,028 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2022-07-22 15:58:59,029 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 15:58:59,029 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2022-07-22 15:58:59,029 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-07-22 15:58:59,029 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:58:59,030 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:58:59,049 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 15:58:59,231 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:58:59,232 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:58:59,232 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:58:59,232 INFO L85 PathProgramCache]: Analyzing trace with hash -1233535180, now seen corresponding path program 1 times [2022-07-22 15:58:59,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:58:59,232 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [526138299] [2022-07-22 15:58:59,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:58:59,233 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:58:59,245 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:58:59,245 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [224208666] [2022-07-22 15:58:59,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:58:59,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:58:59,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:58:59,264 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 15:58:59,290 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 15:58:59,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:59,326 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-22 15:58:59,328 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:58:59,368 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-22 15:58:59,368 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:58:59,437 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-22 15:58:59,437 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:58:59,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [526138299] [2022-07-22 15:58:59,438 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:58:59,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [224208666] [2022-07-22 15:58:59,438 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [224208666] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 15:58:59,438 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 15:58:59,438 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-07-22 15:58:59,440 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [269898297] [2022-07-22 15:58:59,440 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 15:58:59,441 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-22 15:58:59,441 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:58:59,441 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-22 15:58:59,441 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-07-22 15:58:59,441 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-22 15:58:59,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:58:59,526 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2022-07-22 15:58:59,526 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-22 15:58:59,526 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2022-07-22 15:58:59,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:58:59,529 INFO L225 Difference]: With dead ends: 49 [2022-07-22 15:58:59,529 INFO L226 Difference]: Without dead ends: 41 [2022-07-22 15:58:59,530 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 52 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-07-22 15:58:59,532 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 30 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-22 15:58:59,533 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 92 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-22 15:58:59,534 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-07-22 15:58:59,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2022-07-22 15:58:59,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.25) internal successors, (25), 21 states have internal predecessors, (25), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-22 15:58:59,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2022-07-22 15:58:59,547 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 30 [2022-07-22 15:58:59,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:58:59,547 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2022-07-22 15:58:59,547 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-07-22 15:58:59,547 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-07-22 15:58:59,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-07-22 15:58:59,548 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:58:59,548 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:58:59,592 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 15:58:59,749 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,SelfDestructingSolverStorable2 [2022-07-22 15:58:59,750 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:58:59,750 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:58:59,751 INFO L85 PathProgramCache]: Analyzing trace with hash -73118621, now seen corresponding path program 1 times [2022-07-22 15:58:59,751 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:58:59,751 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2060754597] [2022-07-22 15:58:59,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:58:59,752 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:58:59,765 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:58:59,765 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1136212185] [2022-07-22 15:58:59,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:58:59,765 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:58:59,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:58:59,767 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 15:58:59,768 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 15:58:59,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:58:59,800 INFO L263 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-22 15:58:59,801 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:58:59,882 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-22 15:58:59,882 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:58:59,922 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-22 15:58:59,923 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:58:59,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2060754597] [2022-07-22 15:58:59,923 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:58:59,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1136212185] [2022-07-22 15:58:59,923 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1136212185] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-22 15:58:59,923 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-22 15:58:59,924 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-07-22 15:58:59,924 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [136783428] [2022-07-22 15:58:59,924 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 15:58:59,924 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 15:58:59,924 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:58:59,925 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 15:58:59,925 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-07-22 15:58:59,925 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 15:58:59,956 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:58:59,956 INFO L93 Difference]: Finished difference Result 39 states and 49 transitions. [2022-07-22 15:58:59,957 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-22 15:58:59,957 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2022-07-22 15:58:59,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:58:59,958 INFO L225 Difference]: With dead ends: 39 [2022-07-22 15:58:59,958 INFO L226 Difference]: Without dead ends: 37 [2022-07-22 15:58:59,958 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 53 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-07-22 15:58:59,959 INFO L413 NwaCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 15:58:59,959 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 115 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 15:58:59,960 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-07-22 15:58:59,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-07-22 15:58:59,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-22 15:58:59,964 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 47 transitions. [2022-07-22 15:58:59,964 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 47 transitions. Word has length 32 [2022-07-22 15:58:59,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:58:59,965 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 47 transitions. [2022-07-22 15:58:59,965 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 15:58:59,965 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 47 transitions. [2022-07-22 15:58:59,965 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2022-07-22 15:58:59,965 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:58:59,966 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:58:59,984 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 15:59:00,182 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:00,183 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:00,184 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:00,184 INFO L85 PathProgramCache]: Analyzing trace with hash 96561445, now seen corresponding path program 1 times [2022-07-22 15:59:00,184 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:00,185 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [616440580] [2022-07-22 15:59:00,185 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:00,185 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:00,212 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:00,212 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1471176831] [2022-07-22 15:59:00,212 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:00,212 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:00,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:00,215 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 15:59:00,216 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 15:59:00,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:00,249 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-22 15:59:00,250 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:00,293 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-22 15:59:00,293 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-22 15:59:00,293 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:00,294 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [616440580] [2022-07-22 15:59:00,294 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:00,294 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1471176831] [2022-07-22 15:59:00,294 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1471176831] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 15:59:00,294 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 15:59:00,294 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-07-22 15:59:00,294 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1520479273] [2022-07-22 15:59:00,294 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 15:59:00,294 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 15:59:00,294 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:00,295 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 15:59:00,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-07-22 15:59:00,295 INFO L87 Difference]: Start difference. First operand 37 states and 47 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 15:59:00,326 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:00,327 INFO L93 Difference]: Finished difference Result 62 states and 80 transitions. [2022-07-22 15:59:00,330 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-22 15:59:00,330 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2022-07-22 15:59:00,331 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:00,331 INFO L225 Difference]: With dead ends: 62 [2022-07-22 15:59:00,331 INFO L226 Difference]: Without dead ends: 39 [2022-07-22 15:59:00,331 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-07-22 15:59:00,332 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:00,332 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 122 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 15:59:00,332 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-07-22 15:59:00,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2022-07-22 15:59:00,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 26 states have internal predecessors, (30), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-22 15:59:00,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 49 transitions. [2022-07-22 15:59:00,336 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 49 transitions. Word has length 35 [2022-07-22 15:59:00,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:00,337 INFO L495 AbstractCegarLoop]: Abstraction has 39 states and 49 transitions. [2022-07-22 15:59:00,337 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-07-22 15:59:00,337 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 49 transitions. [2022-07-22 15:59:00,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-07-22 15:59:00,337 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:00,338 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:00,359 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 15:59:00,555 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:00,555 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:00,555 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:00,555 INFO L85 PathProgramCache]: Analyzing trace with hash 433790877, now seen corresponding path program 1 times [2022-07-22 15:59:00,556 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:00,556 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2094187348] [2022-07-22 15:59:00,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:00,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:00,563 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:00,563 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [234384495] [2022-07-22 15:59:00,563 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:00,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:00,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:00,567 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 15:59:00,568 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 15:59:00,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:00,600 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 15 conjunts are in the unsatisfiable core [2022-07-22 15:59:00,602 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:00,720 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-07-22 15:59:00,720 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:00,777 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-22 15:59:00,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:00,778 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2094187348] [2022-07-22 15:59:00,778 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:00,778 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [234384495] [2022-07-22 15:59:00,778 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [234384495] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-22 15:59:00,778 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-22 15:59:00,778 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-07-22 15:59:00,778 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1145120456] [2022-07-22 15:59:00,778 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 15:59:00,778 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 15:59:00,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:00,779 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 15:59:00,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-07-22 15:59:00,779 INFO L87 Difference]: Start difference. First operand 39 states and 49 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-07-22 15:59:00,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:00,814 INFO L93 Difference]: Finished difference Result 53 states and 68 transitions. [2022-07-22 15:59:00,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-22 15:59:00,815 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2022-07-22 15:59:00,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:00,815 INFO L225 Difference]: With dead ends: 53 [2022-07-22 15:59:00,815 INFO L226 Difference]: Without dead ends: 51 [2022-07-22 15:59:00,816 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 63 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-07-22 15:59:00,816 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 8 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:00,816 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 141 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 15:59:00,817 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-07-22 15:59:00,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2022-07-22 15:59:00,827 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 32 states have internal predecessors, (38), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-07-22 15:59:00,832 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 65 transitions. [2022-07-22 15:59:00,832 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 65 transitions. Word has length 37 [2022-07-22 15:59:00,832 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:00,832 INFO L495 AbstractCegarLoop]: Abstraction has 50 states and 65 transitions. [2022-07-22 15:59:00,833 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-07-22 15:59:00,833 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 65 transitions. [2022-07-22 15:59:00,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-07-22 15:59:00,838 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:00,838 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:00,854 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-07-22 15:59:01,047 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:01,048 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:01,048 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:01,048 INFO L85 PathProgramCache]: Analyzing trace with hash -553232285, now seen corresponding path program 1 times [2022-07-22 15:59:01,048 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:01,049 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [674481972] [2022-07-22 15:59:01,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:01,049 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:01,056 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:01,056 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [475989266] [2022-07-22 15:59:01,056 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:01,056 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:01,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:01,080 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 15:59:01,081 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 15:59:01,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:01,114 INFO L263 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 15 conjunts are in the unsatisfiable core [2022-07-22 15:59:01,115 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:01,223 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2022-07-22 15:59:01,224 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:01,271 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-22 15:59:01,271 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:01,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [674481972] [2022-07-22 15:59:01,271 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:01,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [475989266] [2022-07-22 15:59:01,271 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [475989266] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-22 15:59:01,272 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-22 15:59:01,272 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-07-22 15:59:01,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [666260354] [2022-07-22 15:59:01,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 15:59:01,272 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 15:59:01,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:01,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 15:59:01,273 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-07-22 15:59:01,273 INFO L87 Difference]: Start difference. First operand 50 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-22 15:59:01,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:01,307 INFO L93 Difference]: Finished difference Result 57 states and 71 transitions. [2022-07-22 15:59:01,307 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-22 15:59:01,307 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2022-07-22 15:59:01,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:01,308 INFO L225 Difference]: With dead ends: 57 [2022-07-22 15:59:01,308 INFO L226 Difference]: Without dead ends: 55 [2022-07-22 15:59:01,309 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 73 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-07-22 15:59:01,309 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:01,309 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 132 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 15:59:01,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-07-22 15:59:01,314 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2022-07-22 15:59:01,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 34 states have (on average 1.2058823529411764) internal successors, (41), 35 states have internal predecessors, (41), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-07-22 15:59:01,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 68 transitions. [2022-07-22 15:59:01,328 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 68 transitions. Word has length 42 [2022-07-22 15:59:01,328 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:01,328 INFO L495 AbstractCegarLoop]: Abstraction has 54 states and 68 transitions. [2022-07-22 15:59:01,329 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-07-22 15:59:01,329 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 68 transitions. [2022-07-22 15:59:01,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-07-22 15:59:01,329 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:01,329 INFO L195 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:01,350 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-07-22 15:59:01,530 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:01,530 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:01,530 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:01,531 INFO L85 PathProgramCache]: Analyzing trace with hash 2115683101, now seen corresponding path program 1 times [2022-07-22 15:59:01,531 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:01,531 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [551870028] [2022-07-22 15:59:01,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:01,531 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:01,538 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:01,538 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1143670064] [2022-07-22 15:59:01,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:01,538 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:01,538 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:01,539 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:01,540 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-07-22 15:59:01,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:01,579 INFO L263 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-22 15:59:01,580 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:01,695 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-07-22 15:59:01,696 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:01,842 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:01,843 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [551870028] [2022-07-22 15:59:01,843 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:01,843 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1143670064] [2022-07-22 15:59:01,843 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1143670064] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 15:59:01,843 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-22 15:59:01,843 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-07-22 15:59:01,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2123169327] [2022-07-22 15:59:01,843 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:01,843 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-07-22 15:59:01,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:01,844 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-07-22 15:59:01,844 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-07-22 15:59:01,844 INFO L87 Difference]: Start difference. First operand 54 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-07-22 15:59:01,949 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:01,949 INFO L93 Difference]: Finished difference Result 61 states and 74 transitions. [2022-07-22 15:59:01,949 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-07-22 15:59:01,950 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2022-07-22 15:59:01,950 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:01,950 INFO L225 Difference]: With dead ends: 61 [2022-07-22 15:59:01,951 INFO L226 Difference]: Without dead ends: 59 [2022-07-22 15:59:01,951 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 42 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2022-07-22 15:59:01,951 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:01,951 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 136 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-22 15:59:01,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2022-07-22 15:59:01,956 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2022-07-22 15:59:01,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-07-22 15:59:01,957 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2022-07-22 15:59:01,957 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 47 [2022-07-22 15:59:01,957 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:01,958 INFO L495 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2022-07-22 15:59:01,958 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-07-22 15:59:01,958 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2022-07-22 15:59:01,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-07-22 15:59:01,958 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:01,958 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:01,977 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-07-22 15:59:02,169 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:02,170 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:02,170 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:02,170 INFO L85 PathProgramCache]: Analyzing trace with hash -879665460, now seen corresponding path program 1 times [2022-07-22 15:59:02,170 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:02,170 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [186145695] [2022-07-22 15:59:02,171 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:02,171 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:02,177 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:02,195 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [82666497] [2022-07-22 15:59:02,195 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:02,195 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:02,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:02,197 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:02,198 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-07-22 15:59:02,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:02,229 INFO L263 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-22 15:59:02,230 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:02,276 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-22 15:59:02,276 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:02,333 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-22 15:59:02,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:02,335 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [186145695] [2022-07-22 15:59:02,335 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:02,336 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [82666497] [2022-07-22 15:59:02,336 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [82666497] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 15:59:02,336 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 15:59:02,336 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2022-07-22 15:59:02,338 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [29900653] [2022-07-22 15:59:02,338 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:02,339 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-07-22 15:59:02,339 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:02,339 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-07-22 15:59:02,340 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-07-22 15:59:02,340 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2022-07-22 15:59:02,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:02,433 INFO L93 Difference]: Finished difference Result 169 states and 198 transitions. [2022-07-22 15:59:02,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-22 15:59:02,433 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 56 [2022-07-22 15:59:02,434 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:02,436 INFO L225 Difference]: With dead ends: 169 [2022-07-22 15:59:02,436 INFO L226 Difference]: Without dead ends: 161 [2022-07-22 15:59:02,437 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 102 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=47, Invalid=85, Unknown=0, NotChecked=0, Total=132 [2022-07-22 15:59:02,438 INFO L413 NwaCegarLoop]: 52 mSDtfsCounter, 57 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:02,438 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 237 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 81 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-22 15:59:02,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2022-07-22 15:59:02,458 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 155. [2022-07-22 15:59:02,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 100 states have (on average 1.18) internal successors, (118), 103 states have internal predecessors, (118), 34 states have call successors, (34), 20 states have call predecessors, (34), 20 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2022-07-22 15:59:02,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 183 transitions. [2022-07-22 15:59:02,459 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 183 transitions. Word has length 56 [2022-07-22 15:59:02,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:02,460 INFO L495 AbstractCegarLoop]: Abstraction has 155 states and 183 transitions. [2022-07-22 15:59:02,460 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.333333333333333) internal successors, (39), 9 states have internal predecessors, (39), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2022-07-22 15:59:02,460 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 183 transitions. [2022-07-22 15:59:02,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2022-07-22 15:59:02,460 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:02,460 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:02,493 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-07-22 15:59:02,677 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-07-22 15:59:02,677 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:02,677 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:02,677 INFO L85 PathProgramCache]: Analyzing trace with hash -1506412172, now seen corresponding path program 1 times [2022-07-22 15:59:02,678 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:02,678 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [270523966] [2022-07-22 15:59:02,678 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:02,678 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:02,684 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:02,684 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [709070599] [2022-07-22 15:59:02,684 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:02,685 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:02,685 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:02,687 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:02,687 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-07-22 15:59:02,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:02,724 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-22 15:59:02,727 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:02,769 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-07-22 15:59:02,769 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:02,824 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-07-22 15:59:02,825 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:02,825 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [270523966] [2022-07-22 15:59:02,825 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:02,825 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [709070599] [2022-07-22 15:59:02,825 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [709070599] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 15:59:02,825 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 15:59:02,825 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-07-22 15:59:02,826 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1391106225] [2022-07-22 15:59:02,826 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:02,827 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-07-22 15:59:02,827 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:02,827 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-07-22 15:59:02,827 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-07-22 15:59:02,828 INFO L87 Difference]: Start difference. First operand 155 states and 183 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2022-07-22 15:59:03,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:03,019 INFO L93 Difference]: Finished difference Result 221 states and 288 transitions. [2022-07-22 15:59:03,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-22 15:59:03,019 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2022-07-22 15:59:03,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:03,020 INFO L225 Difference]: With dead ends: 221 [2022-07-22 15:59:03,020 INFO L226 Difference]: Without dead ends: 207 [2022-07-22 15:59:03,021 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 104 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2022-07-22 15:59:03,021 INFO L413 NwaCegarLoop]: 67 mSDtfsCounter, 61 mSDsluCounter, 271 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 338 SdHoareTripleChecker+Invalid, 259 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:03,021 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 338 Invalid, 259 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-22 15:59:03,022 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 207 states. [2022-07-22 15:59:03,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 207 to 185. [2022-07-22 15:59:03,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 121 states have (on average 1.2148760330578512) internal successors, (147), 123 states have internal predecessors, (147), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2022-07-22 15:59:03,034 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 233 transitions. [2022-07-22 15:59:03,035 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 233 transitions. Word has length 57 [2022-07-22 15:59:03,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:03,035 INFO L495 AbstractCegarLoop]: Abstraction has 185 states and 233 transitions. [2022-07-22 15:59:03,035 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2022-07-22 15:59:03,035 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 233 transitions. [2022-07-22 15:59:03,035 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-07-22 15:59:03,035 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:03,035 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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] [2022-07-22 15:59:03,067 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-07-22 15:59:03,252 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-07-22 15:59:03,252 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:03,252 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:03,252 INFO L85 PathProgramCache]: Analyzing trace with hash -1869160295, now seen corresponding path program 1 times [2022-07-22 15:59:03,252 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:03,252 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [285425312] [2022-07-22 15:59:03,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:03,253 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:03,259 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:03,259 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [27876258] [2022-07-22 15:59:03,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:03,259 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:03,259 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:03,273 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:03,279 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-07-22 15:59:03,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:03,314 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-22 15:59:03,316 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:03,368 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-22 15:59:03,368 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:03,413 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-22 15:59:03,413 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:03,413 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [285425312] [2022-07-22 15:59:03,413 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:03,413 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [27876258] [2022-07-22 15:59:03,414 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [27876258] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 15:59:03,414 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 15:59:03,414 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 9 [2022-07-22 15:59:03,414 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1312219128] [2022-07-22 15:59:03,414 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:03,414 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-07-22 15:59:03,415 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:03,415 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-07-22 15:59:03,415 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2022-07-22 15:59:03,415 INFO L87 Difference]: Start difference. First operand 185 states and 233 transitions. Second operand has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2022-07-22 15:59:03,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:03,513 INFO L93 Difference]: Finished difference Result 265 states and 346 transitions. [2022-07-22 15:59:03,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-22 15:59:03,514 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 59 [2022-07-22 15:59:03,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:03,515 INFO L225 Difference]: With dead ends: 265 [2022-07-22 15:59:03,515 INFO L226 Difference]: Without dead ends: 193 [2022-07-22 15:59:03,516 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 108 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2022-07-22 15:59:03,516 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 54 mSDsluCounter, 187 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 32 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 238 SdHoareTripleChecker+Invalid, 124 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:03,516 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 238 Invalid, 124 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-22 15:59:03,517 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 193 states. [2022-07-22 15:59:03,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 193 to 191. [2022-07-22 15:59:03,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 127 states have (on average 1.1811023622047243) internal successors, (150), 129 states have internal predecessors, (150), 44 states have call successors, (44), 19 states have call predecessors, (44), 19 states have return successors, (42), 42 states have call predecessors, (42), 42 states have call successors, (42) [2022-07-22 15:59:03,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 236 transitions. [2022-07-22 15:59:03,528 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 236 transitions. Word has length 59 [2022-07-22 15:59:03,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:03,528 INFO L495 AbstractCegarLoop]: Abstraction has 191 states and 236 transitions. [2022-07-22 15:59:03,528 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.555555555555555) internal successors, (41), 9 states have internal predecessors, (41), 4 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2022-07-22 15:59:03,529 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 236 transitions. [2022-07-22 15:59:03,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-07-22 15:59:03,529 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:03,529 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 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] [2022-07-22 15:59:03,548 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2022-07-22 15:59:03,746 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-07-22 15:59:03,746 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:03,746 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:03,746 INFO L85 PathProgramCache]: Analyzing trace with hash 991223133, now seen corresponding path program 1 times [2022-07-22 15:59:03,746 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:03,746 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [815043712] [2022-07-22 15:59:03,746 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:03,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:03,753 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:03,753 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [748996630] [2022-07-22 15:59:03,753 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:03,753 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:03,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:03,755 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:03,797 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-22 15:59:03,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:03,835 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-22 15:59:03,837 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:03,943 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 15 proven. 14 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-22 15:59:03,944 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:04,017 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-07-22 15:59:04,017 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:04,017 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [815043712] [2022-07-22 15:59:04,017 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:04,017 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [748996630] [2022-07-22 15:59:04,017 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [748996630] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 15:59:04,018 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 15:59:04,018 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-07-22 15:59:04,018 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [832229810] [2022-07-22 15:59:04,018 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:04,018 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-22 15:59:04,018 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:04,019 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-22 15:59:04,019 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2022-07-22 15:59:04,019 INFO L87 Difference]: Start difference. First operand 191 states and 236 transitions. Second operand has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-07-22 15:59:04,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:04,323 INFO L93 Difference]: Finished difference Result 268 states and 354 transitions. [2022-07-22 15:59:04,324 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-07-22 15:59:04,324 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 64 [2022-07-22 15:59:04,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:04,326 INFO L225 Difference]: With dead ends: 268 [2022-07-22 15:59:04,326 INFO L226 Difference]: Without dead ends: 263 [2022-07-22 15:59:04,327 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 117 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=213, Unknown=0, NotChecked=0, Total=272 [2022-07-22 15:59:04,327 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 50 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 299 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 232 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 299 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:04,327 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 232 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 299 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-22 15:59:04,328 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2022-07-22 15:59:04,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 233. [2022-07-22 15:59:04,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 155 states have (on average 1.2129032258064516) internal successors, (188), 163 states have internal predecessors, (188), 56 states have call successors, (56), 21 states have call predecessors, (56), 21 states have return successors, (53), 48 states have call predecessors, (53), 53 states have call successors, (53) [2022-07-22 15:59:04,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 297 transitions. [2022-07-22 15:59:04,347 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 297 transitions. Word has length 64 [2022-07-22 15:59:04,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:04,348 INFO L495 AbstractCegarLoop]: Abstraction has 233 states and 297 transitions. [2022-07-22 15:59:04,348 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2022-07-22 15:59:04,348 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 297 transitions. [2022-07-22 15:59:04,348 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-07-22 15:59:04,348 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:04,349 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 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] [2022-07-22 15:59:04,367 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-22 15:59:04,565 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-07-22 15:59:04,565 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:04,565 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:04,565 INFO L85 PathProgramCache]: Analyzing trace with hash 1694315171, now seen corresponding path program 2 times [2022-07-22 15:59:04,565 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:04,565 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1864529108] [2022-07-22 15:59:04,565 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:04,566 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:04,572 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:04,572 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1539239544] [2022-07-22 15:59:04,572 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-22 15:59:04,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:04,572 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:04,583 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:04,584 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-07-22 15:59:04,626 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-22 15:59:04,626 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-22 15:59:04,627 INFO L263 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 32 conjunts are in the unsatisfiable core [2022-07-22 15:59:04,628 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:04,903 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2022-07-22 15:59:04,903 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:05,028 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:05,028 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1864529108] [2022-07-22 15:59:05,028 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:05,029 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1539239544] [2022-07-22 15:59:05,029 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1539239544] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 15:59:05,029 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-07-22 15:59:05,029 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-07-22 15:59:05,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1689909429] [2022-07-22 15:59:05,029 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:05,029 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-22 15:59:05,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:05,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-22 15:59:05,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2022-07-22 15:59:05,030 INFO L87 Difference]: Start difference. First operand 233 states and 297 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2022-07-22 15:59:05,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:05,372 INFO L93 Difference]: Finished difference Result 252 states and 320 transitions. [2022-07-22 15:59:05,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-07-22 15:59:05,372 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) Word has length 69 [2022-07-22 15:59:05,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:05,374 INFO L225 Difference]: With dead ends: 252 [2022-07-22 15:59:05,374 INFO L226 Difference]: Without dead ends: 250 [2022-07-22 15:59:05,374 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 75 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=72, Invalid=308, Unknown=0, NotChecked=0, Total=380 [2022-07-22 15:59:05,374 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 41 mSDsluCounter, 206 mSDsCounter, 0 mSdLazyCounter, 306 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 253 SdHoareTripleChecker+Invalid, 324 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 306 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:05,375 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 253 Invalid, 324 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 306 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-22 15:59:05,375 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 250 states. [2022-07-22 15:59:05,388 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 250 to 248. [2022-07-22 15:59:05,388 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 248 states, 164 states have (on average 1.2134146341463414) internal successors, (199), 172 states have internal predecessors, (199), 60 states have call successors, (60), 23 states have call predecessors, (60), 23 states have return successors, (57), 52 states have call predecessors, (57), 57 states have call successors, (57) [2022-07-22 15:59:05,389 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 248 states to 248 states and 316 transitions. [2022-07-22 15:59:05,389 INFO L78 Accepts]: Start accepts. Automaton has 248 states and 316 transitions. Word has length 69 [2022-07-22 15:59:05,390 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:05,390 INFO L495 AbstractCegarLoop]: Abstraction has 248 states and 316 transitions. [2022-07-22 15:59:05,390 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2022-07-22 15:59:05,390 INFO L276 IsEmpty]: Start isEmpty. Operand 248 states and 316 transitions. [2022-07-22 15:59:05,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-07-22 15:59:05,391 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:05,391 INFO L195 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:05,411 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-07-22 15:59:05,607 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-07-22 15:59:05,607 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:05,608 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:05,608 INFO L85 PathProgramCache]: Analyzing trace with hash -1349365539, now seen corresponding path program 3 times [2022-07-22 15:59:05,608 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:05,608 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1725273429] [2022-07-22 15:59:05,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:05,608 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:05,614 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:05,614 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2135522743] [2022-07-22 15:59:05,614 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-22 15:59:05,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:05,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:05,621 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:05,656 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-07-22 15:59:05,695 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-07-22 15:59:05,695 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-22 15:59:05,696 INFO L263 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 51 conjunts are in the unsatisfiable core [2022-07-22 15:59:05,698 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:06,229 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 36 proven. 26 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-07-22 15:59:06,229 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:24,366 WARN L233 SmtUtils]: Spent 6.95s on a formula simplification that was a NOOP. DAG size: 3 (called from [L 813] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2022-07-22 15:59:24,588 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 36 proven. 17 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2022-07-22 15:59:24,588 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:24,589 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1725273429] [2022-07-22 15:59:24,589 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:24,589 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2135522743] [2022-07-22 15:59:24,589 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2135522743] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 15:59:24,589 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 15:59:24,589 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 21 [2022-07-22 15:59:24,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1441230626] [2022-07-22 15:59:24,589 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:24,589 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-07-22 15:59:24,589 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:24,590 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-07-22 15:59:24,590 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=335, Unknown=1, NotChecked=0, Total=420 [2022-07-22 15:59:24,590 INFO L87 Difference]: Start difference. First operand 248 states and 316 transitions. Second operand has 21 states, 20 states have (on average 2.25) internal successors, (45), 17 states have internal predecessors, (45), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-22 15:59:26,602 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-22 15:59:29,950 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-22 15:59:46,538 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.69s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-07-22 15:59:49,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:49,001 INFO L93 Difference]: Finished difference Result 359 states and 490 transitions. [2022-07-22 15:59:49,001 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-07-22 15:59:49,002 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.25) internal successors, (45), 17 states have internal predecessors, (45), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) Word has length 74 [2022-07-22 15:59:49,002 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:49,003 INFO L225 Difference]: With dead ends: 359 [2022-07-22 15:59:49,003 INFO L226 Difference]: Without dead ends: 355 [2022-07-22 15:59:49,004 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 125 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 258 ImplicationChecksByTransitivity, 15.5s TimeCoverageRelationStatistics Valid=289, Invalid=970, Unknown=1, NotChecked=0, Total=1260 [2022-07-22 15:59:49,004 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 140 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 695 mSolverCounterSat, 129 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 152 SdHoareTripleChecker+Valid, 232 SdHoareTripleChecker+Invalid, 826 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 129 IncrementalHoareTripleChecker+Valid, 695 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.0s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:49,005 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [152 Valid, 232 Invalid, 826 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [129 Valid, 695 Invalid, 2 Unknown, 0 Unchecked, 13.0s Time] [2022-07-22 15:59:49,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 355 states. [2022-07-22 15:59:49,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 355 to 322. [2022-07-22 15:59:49,060 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 322 states, 209 states have (on average 1.2535885167464116) internal successors, (262), 218 states have internal predecessors, (262), 88 states have call successors, (88), 25 states have call predecessors, (88), 24 states have return successors, (85), 78 states have call predecessors, (85), 85 states have call successors, (85) [2022-07-22 15:59:49,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 322 states to 322 states and 435 transitions. [2022-07-22 15:59:49,062 INFO L78 Accepts]: Start accepts. Automaton has 322 states and 435 transitions. Word has length 74 [2022-07-22 15:59:49,062 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:49,062 INFO L495 AbstractCegarLoop]: Abstraction has 322 states and 435 transitions. [2022-07-22 15:59:49,063 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.25) internal successors, (45), 17 states have internal predecessors, (45), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) [2022-07-22 15:59:49,063 INFO L276 IsEmpty]: Start isEmpty. Operand 322 states and 435 transitions. [2022-07-22 15:59:49,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-07-22 15:59:49,065 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:49,065 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 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] [2022-07-22 15:59:49,091 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-07-22 15:59:49,266 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-07-22 15:59:49,266 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:49,266 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:49,266 INFO L85 PathProgramCache]: Analyzing trace with hash -484140586, now seen corresponding path program 1 times [2022-07-22 15:59:49,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:49,267 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1765591366] [2022-07-22 15:59:49,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:49,267 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:49,275 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:49,275 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1178515174] [2022-07-22 15:59:49,275 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:49,275 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:49,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:49,285 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:49,286 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-07-22 15:59:49,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:49,333 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 38 conjunts are in the unsatisfiable core [2022-07-22 15:59:49,334 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:49,709 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-07-22 15:59:49,709 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 15:59:50,114 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2022-07-22 15:59:50,114 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:50,115 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1765591366] [2022-07-22 15:59:50,115 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:50,115 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1178515174] [2022-07-22 15:59:50,115 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1178515174] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 15:59:50,115 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-22 15:59:50,115 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-07-22 15:59:50,115 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1881573487] [2022-07-22 15:59:50,115 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-22 15:59:50,115 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-07-22 15:59:50,115 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:50,116 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-07-22 15:59:50,116 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=284, Unknown=0, NotChecked=0, Total=342 [2022-07-22 15:59:50,117 INFO L87 Difference]: Start difference. First operand 322 states and 435 transitions. Second operand has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2022-07-22 15:59:53,772 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:53,772 INFO L93 Difference]: Finished difference Result 392 states and 540 transitions. [2022-07-22 15:59:53,772 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-07-22 15:59:53,772 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) Word has length 80 [2022-07-22 15:59:53,773 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:53,783 INFO L225 Difference]: With dead ends: 392 [2022-07-22 15:59:53,784 INFO L226 Difference]: Without dead ends: 386 [2022-07-22 15:59:53,786 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 140 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 232 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=248, Invalid=1084, Unknown=0, NotChecked=0, Total=1332 [2022-07-22 15:59:53,787 INFO L413 NwaCegarLoop]: 47 mSDtfsCounter, 87 mSDsluCounter, 320 mSDsCounter, 0 mSdLazyCounter, 746 mSolverCounterSat, 140 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 87 SdHoareTripleChecker+Valid, 367 SdHoareTripleChecker+Invalid, 886 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 140 IncrementalHoareTripleChecker+Valid, 746 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:53,787 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [87 Valid, 367 Invalid, 886 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [140 Valid, 746 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2022-07-22 15:59:53,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 386 states. [2022-07-22 15:59:53,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 386 to 375. [2022-07-22 15:59:53,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 375 states, 241 states have (on average 1.2655601659751037) internal successors, (305), 249 states have internal predecessors, (305), 107 states have call successors, (107), 26 states have call predecessors, (107), 26 states have return successors, (105), 99 states have call predecessors, (105), 105 states have call successors, (105) [2022-07-22 15:59:53,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 375 states to 375 states and 517 transitions. [2022-07-22 15:59:53,842 INFO L78 Accepts]: Start accepts. Automaton has 375 states and 517 transitions. Word has length 80 [2022-07-22 15:59:53,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:53,842 INFO L495 AbstractCegarLoop]: Abstraction has 375 states and 517 transitions. [2022-07-22 15:59:53,843 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2022-07-22 15:59:53,843 INFO L276 IsEmpty]: Start isEmpty. Operand 375 states and 517 transitions. [2022-07-22 15:59:53,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2022-07-22 15:59:53,843 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:53,844 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:53,862 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2022-07-22 15:59:54,059 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:54,059 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:54,060 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:54,060 INFO L85 PathProgramCache]: Analyzing trace with hash 1209192741, now seen corresponding path program 1 times [2022-07-22 15:59:54,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:54,060 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [829541810] [2022-07-22 15:59:54,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:54,060 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:54,072 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:54,077 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1142099503] [2022-07-22 15:59:54,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:54,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:54,077 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:54,078 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:54,080 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-07-22 15:59:54,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 15:59:54,126 INFO L263 TraceCheckSpWp]: Trace formula consists of 262 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-22 15:59:54,127 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 15:59:54,147 INFO L134 CoverageAnalysis]: Checked inductivity of 181 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2022-07-22 15:59:54,147 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-22 15:59:54,147 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 15:59:54,147 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [829541810] [2022-07-22 15:59:54,147 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-22 15:59:54,147 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1142099503] [2022-07-22 15:59:54,147 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1142099503] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 15:59:54,148 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 15:59:54,148 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-22 15:59:54,148 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [844723402] [2022-07-22 15:59:54,148 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 15:59:54,148 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-22 15:59:54,148 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 15:59:54,149 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-22 15:59:54,149 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-22 15:59:54,149 INFO L87 Difference]: Start difference. First operand 375 states and 517 transitions. Second operand has 5 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-22 15:59:54,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 15:59:54,278 INFO L93 Difference]: Finished difference Result 603 states and 875 transitions. [2022-07-22 15:59:54,279 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-22 15:59:54,279 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 89 [2022-07-22 15:59:54,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-22 15:59:54,281 INFO L225 Difference]: With dead ends: 603 [2022-07-22 15:59:54,281 INFO L226 Difference]: Without dead ends: 444 [2022-07-22 15:59:54,281 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 86 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-07-22 15:59:54,282 INFO L413 NwaCegarLoop]: 57 mSDtfsCounter, 11 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 73 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 73 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-22 15:59:54,282 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 157 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 73 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-22 15:59:54,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 444 states. [2022-07-22 15:59:54,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 444 to 408. [2022-07-22 15:59:54,339 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 408 states, 264 states have (on average 1.2727272727272727) internal successors, (336), 272 states have internal predecessors, (336), 117 states have call successors, (117), 26 states have call predecessors, (117), 26 states have return successors, (115), 109 states have call predecessors, (115), 115 states have call successors, (115) [2022-07-22 15:59:54,340 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 408 states to 408 states and 568 transitions. [2022-07-22 15:59:54,341 INFO L78 Accepts]: Start accepts. Automaton has 408 states and 568 transitions. Word has length 89 [2022-07-22 15:59:54,341 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-22 15:59:54,341 INFO L495 AbstractCegarLoop]: Abstraction has 408 states and 568 transitions. [2022-07-22 15:59:54,341 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 3 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2022-07-22 15:59:54,341 INFO L276 IsEmpty]: Start isEmpty. Operand 408 states and 568 transitions. [2022-07-22 15:59:54,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2022-07-22 15:59:54,342 INFO L187 NwaCegarLoop]: Found error trace [2022-07-22 15:59:54,342 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:54,359 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-07-22 15:59:54,559 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-07-22 15:59:54,559 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-22 15:59:54,559 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 15:59:54,559 INFO L85 PathProgramCache]: Analyzing trace with hash 1707915242, now seen corresponding path program 1 times [2022-07-22 15:59:54,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 15:59:54,559 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1069416788] [2022-07-22 15:59:54,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:54,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 15:59:54,573 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-22 15:59:54,573 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [855651100] [2022-07-22 15:59:54,573 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 15:59:54,575 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 15:59:54,575 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 15:59:54,576 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 15:59:54,577 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-07-22 15:59:54,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 15:59:54,627 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 15:59:54,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 15:59:54,690 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 15:59:54,693 INFO L271 BasicCegarLoop]: Counterexample is feasible [2022-07-22 15:59:54,694 INFO L805 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-07-22 15:59:54,726 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-07-22 15:59:54,924 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-07-22 15:59:54,927 INFO L356 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 15:59:54,929 INFO L176 ceAbstractionStarter]: Computing trace abstraction results [2022-07-22 15:59:54,990 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.07 03:59:54 BoogieIcfgContainer [2022-07-22 15:59:54,990 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-07-22 15:59:54,990 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2022-07-22 15:59:54,990 INFO L271 PluginConnector]: Initializing Witness Printer... [2022-07-22 15:59:54,991 INFO L275 PluginConnector]: Witness Printer initialized [2022-07-22 15:59:54,991 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 03:58:58" (3/4) ... [2022-07-22 15:59:54,992 INFO L131 WitnessPrinter]: Generating witness for reachability counterexample [2022-07-22 15:59:55,051 INFO L141 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2022-07-22 15:59:55,051 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2022-07-22 15:59:55,052 INFO L158 Benchmark]: Toolchain (without parser) took 56968.45ms. Allocated memory was 86.0MB in the beginning and 151.0MB in the end (delta: 65.0MB). Free memory was 51.4MB in the beginning and 116.4MB in the end (delta: -65.0MB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-22 15:59:55,052 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 86.0MB. Free memory was 61.6MB in the beginning and 61.6MB in the end (delta: 18.4kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-22 15:59:55,052 INFO L158 Benchmark]: CACSL2BoogieTranslator took 240.99ms. Allocated memory is still 86.0MB. Free memory was 51.2MB in the beginning and 60.9MB in the end (delta: -9.7MB). Peak memory consumption was 7.6MB. Max. memory is 16.1GB. [2022-07-22 15:59:55,052 INFO L158 Benchmark]: Boogie Procedure Inliner took 24.09ms. Allocated memory is still 86.0MB. Free memory was 60.9MB in the beginning and 59.4MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-22 15:59:55,053 INFO L158 Benchmark]: Boogie Preprocessor took 15.14ms. Allocated memory is still 86.0MB. Free memory was 59.3MB in the beginning and 58.2MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2022-07-22 15:59:55,053 INFO L158 Benchmark]: RCFGBuilder took 195.83ms. Allocated memory is still 86.0MB. Free memory was 58.2MB in the beginning and 47.5MB in the end (delta: 10.6MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2022-07-22 15:59:55,053 INFO L158 Benchmark]: TraceAbstraction took 56426.67ms. Allocated memory was 86.0MB in the beginning and 151.0MB in the end (delta: 65.0MB). Free memory was 47.0MB in the beginning and 121.6MB in the end (delta: -74.6MB). Peak memory consumption was 75.0MB. Max. memory is 16.1GB. [2022-07-22 15:59:55,053 INFO L158 Benchmark]: Witness Printer took 61.22ms. Allocated memory is still 151.0MB. Free memory was 121.6MB in the beginning and 116.4MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2022-07-22 15:59:55,054 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.17ms. Allocated memory is still 86.0MB. Free memory was 61.6MB in the beginning and 61.6MB in the end (delta: 18.4kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 240.99ms. Allocated memory is still 86.0MB. Free memory was 51.2MB in the beginning and 60.9MB in the end (delta: -9.7MB). Peak memory consumption was 7.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 24.09ms. Allocated memory is still 86.0MB. Free memory was 60.9MB in the beginning and 59.4MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 15.14ms. Allocated memory is still 86.0MB. Free memory was 59.3MB in the beginning and 58.2MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 195.83ms. Allocated memory is still 86.0MB. Free memory was 58.2MB in the beginning and 47.5MB in the end (delta: 10.6MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 56426.67ms. Allocated memory was 86.0MB in the beginning and 151.0MB in the end (delta: 65.0MB). Free memory was 47.0MB in the beginning and 121.6MB in the end (delta: -74.6MB). Peak memory consumption was 75.0MB. Max. memory is 16.1GB. * Witness Printer took 61.22ms. Allocated memory is still 151.0MB. Free memory was 121.6MB in the beginning and 116.4MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; VAL [counter=0] [L20] int x, y; [L21] long long a, b, p, q, r, s, c, k, xy, yy; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L24] RET assume_abort_if_not(x >= 1) VAL [counter=0, x=2, y=3] [L25] CALL assume_abort_if_not(y >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L25] RET assume_abort_if_not(y >= 1) VAL [counter=0, x=2, y=3] [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 [L33] c = 0 [L34] k = 0 [L35] xy = (long long) x * y [L36] yy = (long long) y * y VAL [a=2, b=3, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L37] CALL assume_abort_if_not(xy < 2147483647) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L37] RET assume_abort_if_not(xy < 2147483647) VAL [a=2, b=3, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L38] CALL assume_abort_if_not(yy < 2147483647) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, cond=1, counter=0] [L38] RET assume_abort_if_not(yy < 2147483647) VAL [a=2, b=3, c=0, counter=0, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L40] EXPR counter++ VAL [a=2, b=3, c=0, counter=1, counter++=0, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [a=2, b=3, c=2, counter=1, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L46] EXPR counter++ VAL [a=2, b=3, c=2, counter=2, counter++=1, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=2] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L51] COND TRUE !(c >= b) VAL [a=2, b=3, c=2, counter=2, k=0, p=1, q=0, r=0, s=1, x=2, xy=6, y=3, yy=9] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k VAL [a=3, b=2, c=2, counter=2, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L40] EXPR counter++ VAL [a=3, b=2, c=2, counter=3, counter++=2, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L40] COND TRUE counter++<5 [L41] COND FALSE !(!(b != 0)) [L43] c = a [L44] k = 0 VAL [a=3, b=2, c=3, counter=3, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L46] EXPR counter++ VAL [a=3, b=2, c=3, counter=4, counter++=3, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=4] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=3, b=2, c=3, counter=4, k=0, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L51] COND FALSE !(!(c >= b)) [L53] c = c - b [L54] k = k + 1 VAL [a=3, b=2, c=1, counter=4, k=1, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L46] EXPR counter++ VAL [a=3, b=2, c=1, counter=5, counter++=4, k=1, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L46] COND TRUE counter++<5 [L47] CALL __VERIFIER_assert(a == k * b + c) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L47] RET __VERIFIER_assert(a == k * b + c) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L48] CALL __VERIFIER_assert(a == y*r + x*p) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L48] RET __VERIFIER_assert(a == y*r + x*p) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L49] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L49] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L50] CALL __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, cond=1, counter=5] [L50] RET __VERIFIER_assert(q*xy + s*yy - q*x - b*y - s*y + b == 0) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L51] COND TRUE !(c >= b) VAL [a=3, b=2, c=1, counter=5, k=1, p=0, q=1, r=1, s=0, temp=0, x=2, xy=6, y=3, yy=9] [L57] a = b [L58] b = c [L60] long long temp; [L61] temp = p [L62] p = q [L63] q = temp - q * k [L64] temp = r [L65] r = s [L66] s = temp - s * k VAL [a=2, b=1, c=1, counter=5, k=1, p=1, q=-1, r=0, s=1, temp=1, x=2, xy=6, y=3, yy=9] [L40] EXPR counter++ VAL [a=2, b=1, c=1, counter=6, counter++=5, k=1, p=1, q=-1, r=0, s=1, temp=1, x=2, xy=6, y=3, yy=9] [L40] COND FALSE !(counter++<5) [L70] CALL __VERIFIER_assert(q*x + s*y == 0) VAL [\old(cond)=0, counter=6] [L11] COND TRUE !(cond) VAL [\old(cond)=0, cond=0, counter=6] [L13] reach_error() VAL [\old(cond)=0, cond=0, counter=6] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 34 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 56.3s, OverallIterations: 17, TraceHistogramMax: 13, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 29.7s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 2 mSolverCounterUnknown, 625 SdHoareTripleChecker+Valid, 17.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 571 mSDsluCounter, 2937 SdHoareTripleChecker+Invalid, 16.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2227 mSDsCounter, 500 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2807 IncrementalHoareTripleChecker+Invalid, 3309 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 500 mSolverCounterUnsat, 710 mSDtfsCounter, 2807 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1415 GetRequests, 1211 SyntacticMatches, 15 SemanticMatches, 189 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 644 ImplicationChecksByTransitivity, 17.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=408occurred in iteration=16, InterpolantAutomatonStates: 151, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 16 MinimizatonAttempts, 153 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 21.6s InterpolantComputationTime, 934 NumberOfCodeBlocks, 914 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 1333 ConstructedInterpolants, 0 QuantifiedInterpolants, 6724 SizeOfPredicates, 51 NumberOfNonLiveVariables, 2372 ConjunctsInSsa, 248 ConjunctsInUnsatCore, 26 InterpolantComputations, 7 PerfectInterpolantSequences, 1536/1717 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2022-07-22 15:59:55,078 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE