./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/prod4br-ll_unwindbound100.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version eb692b52 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/prod4br-ll_unwindbound100.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 4d17ed8dd7de3007f02b2c3df3a75e1fbb5469b0133c538c149df8a118a565d0 --- Real Ultimate output --- This is Ultimate 0.2.2-?-eb692b5 [2022-07-19 16:27:09,164 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-19 16:27:09,166 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-19 16:27:09,206 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-19 16:27:09,207 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-19 16:27:09,208 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-19 16:27:09,210 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-19 16:27:09,212 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-19 16:27:09,214 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-19 16:27:09,219 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-19 16:27:09,220 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-19 16:27:09,222 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-19 16:27:09,223 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-19 16:27:09,225 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-19 16:27:09,227 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-19 16:27:09,230 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-19 16:27:09,231 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-19 16:27:09,233 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-19 16:27:09,234 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-19 16:27:09,239 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-19 16:27:09,241 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-19 16:27:09,242 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-19 16:27:09,243 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-19 16:27:09,244 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-19 16:27:09,245 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-19 16:27:09,249 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-19 16:27:09,249 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-19 16:27:09,250 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-19 16:27:09,251 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-19 16:27:09,252 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-19 16:27:09,253 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-19 16:27:09,253 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-19 16:27:09,254 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-19 16:27:09,255 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-19 16:27:09,255 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-19 16:27:09,256 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-19 16:27:09,256 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-19 16:27:09,257 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-19 16:27:09,257 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-19 16:27:09,257 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-19 16:27:09,258 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-19 16:27:09,260 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-19 16:27:09,261 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2022-07-19 16:27:09,296 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-19 16:27:09,297 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-19 16:27:09,297 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-19 16:27:09,298 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-19 16:27:09,298 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-07-19 16:27:09,298 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-07-19 16:27:09,299 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-19 16:27:09,299 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-19 16:27:09,299 INFO L138 SettingsManager]: * Use SBE=true [2022-07-19 16:27:09,300 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-19 16:27:09,300 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-19 16:27:09,301 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-19 16:27:09,301 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-19 16:27:09,301 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-19 16:27:09,301 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-07-19 16:27:09,301 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-07-19 16:27:09,302 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-07-19 16:27:09,302 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-19 16:27:09,302 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-19 16:27:09,302 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-19 16:27:09,302 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-07-19 16:27:09,303 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-19 16:27:09,303 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-19 16:27:09,303 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-07-19 16:27:09,303 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 16:27:09,303 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-19 16:27:09,304 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-07-19 16:27:09,304 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-07-19 16:27:09,304 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-19 16:27:09,304 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-07-19 16:27:09,305 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-07-19 16:27:09,305 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-07-19 16:27:09,305 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-07-19 16:27:09,305 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 -> 4d17ed8dd7de3007f02b2c3df3a75e1fbb5469b0133c538c149df8a118a565d0 [2022-07-19 16:27:09,558 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-19 16:27:09,579 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-19 16:27:09,581 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-19 16:27:09,582 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-19 16:27:09,582 INFO L275 PluginConnector]: CDTParser initialized [2022-07-19 16:27:09,583 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/prod4br-ll_unwindbound100.c [2022-07-19 16:27:09,647 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fc2bb6764/cdd35f877675464eadc18cbc7528a44a/FLAG3e9bf9986 [2022-07-19 16:27:10,041 INFO L306 CDTParser]: Found 1 translation units. [2022-07-19 16:27:10,042 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/prod4br-ll_unwindbound100.c [2022-07-19 16:27:10,049 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fc2bb6764/cdd35f877675464eadc18cbc7528a44a/FLAG3e9bf9986 [2022-07-19 16:27:10,438 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/fc2bb6764/cdd35f877675464eadc18cbc7528a44a [2022-07-19 16:27:10,440 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-19 16:27:10,442 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-19 16:27:10,443 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-19 16:27:10,443 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-19 16:27:10,446 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-19 16:27:10,446 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,447 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5023b18f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10, skipping insertion in model container [2022-07-19 16:27:10,447 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,454 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-19 16:27:10,468 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-19 16:27:10,644 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/prod4br-ll_unwindbound100.c[524,537] [2022-07-19 16:27:10,684 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 16:27:10,691 INFO L203 MainTranslator]: Completed pre-run [2022-07-19 16:27:10,703 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/prod4br-ll_unwindbound100.c[524,537] [2022-07-19 16:27:10,725 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-19 16:27:10,741 INFO L208 MainTranslator]: Completed translation [2022-07-19 16:27:10,741 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10 WrapperNode [2022-07-19 16:27:10,742 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-19 16:27:10,743 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-19 16:27:10,743 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-19 16:27:10,743 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-19 16:27:10,750 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,764 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,792 INFO L137 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 59 [2022-07-19 16:27:10,793 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-19 16:27:10,794 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-19 16:27:10,794 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-19 16:27:10,794 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-19 16:27:10,801 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,802 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,803 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,803 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,809 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,813 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,817 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,822 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-19 16:27:10,823 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-19 16:27:10,824 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-19 16:27:10,824 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-19 16:27:10,825 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (1/1) ... [2022-07-19 16:27:10,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-07-19 16:27:10,840 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:10,861 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-19 16:27:10,872 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-19 16:27:10,904 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-19 16:27:10,904 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-19 16:27:10,904 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-19 16:27:10,904 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-19 16:27:10,905 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-07-19 16:27:10,905 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-07-19 16:27:10,959 INFO L234 CfgBuilder]: Building ICFG [2022-07-19 16:27:10,961 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-19 16:27:11,137 INFO L275 CfgBuilder]: Performing block encoding [2022-07-19 16:27:11,142 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-19 16:27:11,142 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-07-19 16:27:11,144 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 04:27:11 BoogieIcfgContainer [2022-07-19 16:27:11,144 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-19 16:27:11,145 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-07-19 16:27:11,146 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-07-19 16:27:11,148 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-07-19 16:27:11,149 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.07 04:27:10" (1/3) ... [2022-07-19 16:27:11,149 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@272e6558 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 04:27:11, skipping insertion in model container [2022-07-19 16:27:11,150 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.07 04:27:10" (2/3) ... [2022-07-19 16:27:11,150 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@272e6558 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.07 04:27:11, skipping insertion in model container [2022-07-19 16:27:11,150 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.07 04:27:11" (3/3) ... [2022-07-19 16:27:11,151 INFO L111 eAbstractionObserver]: Analyzing ICFG prod4br-ll_unwindbound100.c [2022-07-19 16:27:11,164 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-07-19 16:27:11,164 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-07-19 16:27:11,219 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-07-19 16:27:11,226 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@5adcec9f, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@68e30a4e [2022-07-19 16:27:11,227 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-07-19 16:27:11,241 INFO L276 IsEmpty]: Start isEmpty. Operand has 23 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-19 16:27:11,248 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2022-07-19 16:27:11,248 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:11,249 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:11,250 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:11,255 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:11,256 INFO L85 PathProgramCache]: Analyzing trace with hash -563977895, now seen corresponding path program 1 times [2022-07-19 16:27:11,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:11,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [861928624] [2022-07-19 16:27:11,265 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:11,266 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:11,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:11,381 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:11,381 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:11,382 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [861928624] [2022-07-19 16:27:11,383 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [861928624] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 16:27:11,383 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 16:27:11,383 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2022-07-19 16:27:11,384 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [728892339] [2022-07-19 16:27:11,385 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 16:27:11,388 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2022-07-19 16:27:11,389 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:11,415 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2022-07-19 16:27:11,416 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-19 16:27:11,418 INFO L87 Difference]: Start difference. First operand has 23 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 16:27:11,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:11,435 INFO L93 Difference]: Finished difference Result 43 states and 63 transitions. [2022-07-19 16:27:11,436 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-19 16:27:11,437 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2022-07-19 16:27:11,437 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:11,445 INFO L225 Difference]: With dead ends: 43 [2022-07-19 16:27:11,446 INFO L226 Difference]: Without dead ends: 19 [2022-07-19 16:27:11,455 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2022-07-19 16:27:11,459 INFO L413 NwaCegarLoop]: 29 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, 29 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-19 16:27:11,459 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 16:27:11,480 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2022-07-19 16:27:11,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2022-07-19 16:27:11,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:11,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 25 transitions. [2022-07-19 16:27:11,502 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 25 transitions. Word has length 9 [2022-07-19 16:27:11,502 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:11,502 INFO L495 AbstractCegarLoop]: Abstraction has 19 states and 25 transitions. [2022-07-19 16:27:11,503 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 16:27:11,503 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 25 transitions. [2022-07-19 16:27:11,504 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2022-07-19 16:27:11,504 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:11,504 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:11,505 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-07-19 16:27:11,505 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:11,505 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:11,506 INFO L85 PathProgramCache]: Analyzing trace with hash -1986058659, now seen corresponding path program 1 times [2022-07-19 16:27:11,506 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:11,506 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [160470453] [2022-07-19 16:27:11,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:11,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:11,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:11,626 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:11,627 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:11,627 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [160470453] [2022-07-19 16:27:11,627 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [160470453] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 16:27:11,627 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 16:27:11,628 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-07-19 16:27:11,628 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1122763425] [2022-07-19 16:27:11,628 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 16:27:11,629 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-07-19 16:27:11,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:11,630 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-07-19 16:27:11,630 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-07-19 16:27:11,630 INFO L87 Difference]: Start difference. First operand 19 states and 25 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 16:27:11,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:11,659 INFO L93 Difference]: Finished difference Result 29 states and 36 transitions. [2022-07-19 16:27:11,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-07-19 16:27:11,660 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2022-07-19 16:27:11,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:11,661 INFO L225 Difference]: With dead ends: 29 [2022-07-19 16:27:11,661 INFO L226 Difference]: Without dead ends: 21 [2022-07-19 16:27:11,661 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 1 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-19 16:27:11,662 INFO L413 NwaCegarLoop]: 23 mSDtfsCounter, 0 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 63 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:11,663 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 63 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 16:27:11,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2022-07-19 16:27:11,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2022-07-19 16:27:11,667 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:11,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2022-07-19 16:27:11,668 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 10 [2022-07-19 16:27:11,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:11,668 INFO L495 AbstractCegarLoop]: Abstraction has 21 states and 27 transitions. [2022-07-19 16:27:11,668 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 16:27:11,669 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 27 transitions. [2022-07-19 16:27:11,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2022-07-19 16:27:11,669 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:11,669 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:11,669 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-07-19 16:27:11,670 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:11,670 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:11,670 INFO L85 PathProgramCache]: Analyzing trace with hash -1984271199, now seen corresponding path program 1 times [2022-07-19 16:27:11,671 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:11,671 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1232287651] [2022-07-19 16:27:11,671 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:11,671 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:11,681 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:11,682 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1949149546] [2022-07-19 16:27:11,682 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:11,682 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:11,683 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:11,684 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-19 16:27:11,685 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-19 16:27:11,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:11,730 INFO L263 TraceCheckSpWp]: Trace formula consists of 58 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-19 16:27:11,733 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:11,831 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:11,832 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 16:27:11,833 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:11,833 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1232287651] [2022-07-19 16:27:11,833 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:11,833 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1949149546] [2022-07-19 16:27:11,834 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1949149546] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 16:27:11,835 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 16:27:11,837 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-19 16:27:11,837 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [956924001] [2022-07-19 16:27:11,838 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 16:27:11,838 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 16:27:11,839 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:11,839 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 16:27:11,840 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-07-19 16:27:11,841 INFO L87 Difference]: Start difference. First operand 21 states and 27 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 16:27:11,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:11,935 INFO L93 Difference]: Finished difference Result 34 states and 45 transitions. [2022-07-19 16:27:11,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 16:27:11,936 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2022-07-19 16:27:11,936 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:11,937 INFO L225 Difference]: With dead ends: 34 [2022-07-19 16:27:11,941 INFO L226 Difference]: Without dead ends: 32 [2022-07-19 16:27:11,941 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-07-19 16:27:11,942 INFO L413 NwaCegarLoop]: 16 mSDtfsCounter, 9 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 53 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:11,943 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 52 Invalid, 53 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 16:27:11,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-07-19 16:27:11,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 26. [2022-07-19 16:27:11,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 21 states have internal predecessors, (25), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-19 16:27:11,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2022-07-19 16:27:11,953 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 10 [2022-07-19 16:27:11,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:11,953 INFO L495 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2022-07-19 16:27:11,954 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-19 16:27:11,954 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2022-07-19 16:27:11,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-07-19 16:27:11,955 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:11,956 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:11,984 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-19 16:27:12,177 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:12,177 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:12,178 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:12,178 INFO L85 PathProgramCache]: Analyzing trace with hash -1194524114, now seen corresponding path program 1 times [2022-07-19 16:27:12,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:12,178 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1769833841] [2022-07-19 16:27:12,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:12,178 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:12,188 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:12,189 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [812306202] [2022-07-19 16:27:12,189 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:12,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:12,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:12,191 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-19 16:27:12,192 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-19 16:27:12,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:12,229 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 15 conjunts are in the unsatisfiable core [2022-07-19 16:27:12,235 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:12,562 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:12,562 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:12,786 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:12,786 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:12,786 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1769833841] [2022-07-19 16:27:12,786 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:12,786 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [812306202] [2022-07-19 16:27:12,787 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [812306202] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 16:27:12,787 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 16:27:12,787 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 14 [2022-07-19 16:27:12,787 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1370236303] [2022-07-19 16:27:12,787 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 16:27:12,788 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-19 16:27:12,788 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:12,788 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-19 16:27:12,788 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2022-07-19 16:27:12,789 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand has 14 states, 12 states have (on average 1.75) internal successors, (21), 11 states have internal predecessors, (21), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:13,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:13,245 INFO L93 Difference]: Finished difference Result 47 states and 64 transitions. [2022-07-19 16:27:13,245 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-07-19 16:27:13,245 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 1.75) internal successors, (21), 11 states have internal predecessors, (21), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2022-07-19 16:27:13,246 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:13,248 INFO L225 Difference]: With dead ends: 47 [2022-07-19 16:27:13,248 INFO L226 Difference]: Without dead ends: 45 [2022-07-19 16:27:13,248 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=99, Invalid=363, Unknown=0, NotChecked=0, Total=462 [2022-07-19 16:27:13,249 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 61 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 247 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:13,250 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 83 Invalid, 247 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 201 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-07-19 16:27:13,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-07-19 16:27:13,257 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 31. [2022-07-19 16:27:13,257 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 25 states have internal predecessors, (28), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2022-07-19 16:27:13,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 37 transitions. [2022-07-19 16:27:13,258 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 37 transitions. Word has length 16 [2022-07-19 16:27:13,258 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:13,258 INFO L495 AbstractCegarLoop]: Abstraction has 31 states and 37 transitions. [2022-07-19 16:27:13,258 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 1.75) internal successors, (21), 11 states have internal predecessors, (21), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:13,259 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 37 transitions. [2022-07-19 16:27:13,259 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-07-19 16:27:13,259 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:13,259 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:13,287 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-19 16:27:13,483 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,SelfDestructingSolverStorable3 [2022-07-19 16:27:13,483 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:13,484 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:13,484 INFO L85 PathProgramCache]: Analyzing trace with hash -1756733383, now seen corresponding path program 1 times [2022-07-19 16:27:13,484 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:13,484 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [99292492] [2022-07-19 16:27:13,485 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:13,485 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:13,494 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:13,494 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1319487703] [2022-07-19 16:27:13,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:13,495 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:13,495 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:13,498 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-19 16:27:13,501 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-19 16:27:13,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:13,534 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-19 16:27:13,535 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:13,562 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:13,563 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:13,592 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:13,593 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:13,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [99292492] [2022-07-19 16:27:13,593 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:13,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1319487703] [2022-07-19 16:27:13,593 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1319487703] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 16:27:13,593 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 16:27:13,594 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2022-07-19 16:27:13,594 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1787716976] [2022-07-19 16:27:13,594 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 16:27:13,594 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 16:27:13,595 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:13,595 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 16:27:13,595 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-07-19 16:27:13,595 INFO L87 Difference]: Start difference. First operand 31 states and 37 transitions. Second operand has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:13,677 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:13,677 INFO L93 Difference]: Finished difference Result 95 states and 115 transitions. [2022-07-19 16:27:13,677 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-19 16:27:13,678 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 19 [2022-07-19 16:27:13,678 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:13,679 INFO L225 Difference]: With dead ends: 95 [2022-07-19 16:27:13,679 INFO L226 Difference]: Without dead ends: 85 [2022-07-19 16:27:13,679 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-07-19 16:27:13,680 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 52 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:13,680 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 124 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 16:27:13,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2022-07-19 16:27:13,693 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 79. [2022-07-19 16:27:13,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 57 states have (on average 1.3508771929824561) internal successors, (77), 61 states have internal predecessors, (77), 13 states have call successors, (13), 9 states have call predecessors, (13), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-07-19 16:27:13,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 99 transitions. [2022-07-19 16:27:13,700 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 99 transitions. Word has length 19 [2022-07-19 16:27:13,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:13,701 INFO L495 AbstractCegarLoop]: Abstraction has 79 states and 99 transitions. [2022-07-19 16:27:13,701 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.625) internal successors, (29), 8 states have internal predecessors, (29), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:13,701 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 99 transitions. [2022-07-19 16:27:13,702 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2022-07-19 16:27:13,702 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:13,702 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:13,719 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-19 16:27:13,907 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:13,908 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:13,908 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:13,908 INFO L85 PathProgramCache]: Analyzing trace with hash -1754945923, now seen corresponding path program 1 times [2022-07-19 16:27:13,908 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:13,908 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [928751341] [2022-07-19 16:27:13,908 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:13,909 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:13,917 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:13,917 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [915382092] [2022-07-19 16:27:13,917 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:13,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:13,917 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:13,919 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-19 16:27:13,924 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-19 16:27:13,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:13,973 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 25 conjunts are in the unsatisfiable core [2022-07-19 16:27:13,974 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:14,751 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:14,751 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:15,589 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:15,589 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:15,589 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [928751341] [2022-07-19 16:27:15,589 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:15,589 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [915382092] [2022-07-19 16:27:15,589 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [915382092] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 16:27:15,590 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 16:27:15,590 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2022-07-19 16:27:15,590 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1704451550] [2022-07-19 16:27:15,590 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 16:27:15,590 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-07-19 16:27:15,591 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:15,591 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-19 16:27:15,591 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2022-07-19 16:27:15,591 INFO L87 Difference]: Start difference. First operand 79 states and 99 transitions. Second operand has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:16,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:16,930 INFO L93 Difference]: Finished difference Result 120 states and 157 transitions. [2022-07-19 16:27:16,930 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-07-19 16:27:16,931 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 19 [2022-07-19 16:27:16,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:16,932 INFO L225 Difference]: With dead ends: 120 [2022-07-19 16:27:16,932 INFO L226 Difference]: Without dead ends: 114 [2022-07-19 16:27:16,933 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=87, Invalid=219, Unknown=0, NotChecked=0, Total=306 [2022-07-19 16:27:16,934 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 104 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 166 mSolverCounterSat, 107 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 104 SdHoareTripleChecker+Valid, 80 SdHoareTripleChecker+Invalid, 273 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 107 IncrementalHoareTripleChecker+Valid, 166 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:16,934 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [104 Valid, 80 Invalid, 273 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [107 Valid, 166 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2022-07-19 16:27:16,935 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2022-07-19 16:27:16,947 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 71. [2022-07-19 16:27:16,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 54 states have (on average 1.3333333333333333) internal successors, (72), 56 states have internal predecessors, (72), 9 states have call successors, (9), 8 states have call predecessors, (9), 7 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-19 16:27:16,948 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-07-19 16:27:16,948 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 19 [2022-07-19 16:27:16,949 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:16,949 INFO L495 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-07-19 16:27:16,949 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:16,949 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-07-19 16:27:16,950 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-07-19 16:27:16,950 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:16,950 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:16,975 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-19 16:27:17,163 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:17,164 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:17,164 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:17,164 INFO L85 PathProgramCache]: Analyzing trace with hash -1942139802, now seen corresponding path program 1 times [2022-07-19 16:27:17,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:17,164 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [466932529] [2022-07-19 16:27:17,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:17,165 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:17,172 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:17,173 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [527821465] [2022-07-19 16:27:17,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:17,173 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:17,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:17,174 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-19 16:27:17,176 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-19 16:27:17,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:17,207 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 10 conjunts are in the unsatisfiable core [2022-07-19 16:27:17,208 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:17,269 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-19 16:27:17,270 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 16:27:17,270 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:17,270 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [466932529] [2022-07-19 16:27:17,270 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:17,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [527821465] [2022-07-19 16:27:17,271 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [527821465] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 16:27:17,271 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 16:27:17,271 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-07-19 16:27:17,272 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [842089152] [2022-07-19 16:27:17,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 16:27:17,272 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-07-19 16:27:17,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:17,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-07-19 16:27:17,276 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2022-07-19 16:27:17,276 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 8 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 7 states have internal predecessors, (13), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:17,405 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:17,405 INFO L93 Difference]: Finished difference Result 108 states and 143 transitions. [2022-07-19 16:27:17,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-19 16:27:17,406 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 7 states have internal predecessors, (13), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2022-07-19 16:27:17,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:17,407 INFO L225 Difference]: With dead ends: 108 [2022-07-19 16:27:17,407 INFO L226 Difference]: Without dead ends: 96 [2022-07-19 16:27:17,407 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-07-19 16:27:17,408 INFO L413 NwaCegarLoop]: 19 mSDtfsCounter, 52 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 86 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 86 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:17,408 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [52 Valid, 83 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 86 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 16:27:17,409 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2022-07-19 16:27:17,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 91. [2022-07-19 16:27:17,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 71 states have (on average 1.3380281690140845) internal successors, (95), 73 states have internal predecessors, (95), 12 states have call successors, (12), 8 states have call predecessors, (12), 7 states have return successors, (10), 9 states have call predecessors, (10), 10 states have call successors, (10) [2022-07-19 16:27:17,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 117 transitions. [2022-07-19 16:27:17,424 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 117 transitions. Word has length 21 [2022-07-19 16:27:17,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:17,424 INFO L495 AbstractCegarLoop]: Abstraction has 91 states and 117 transitions. [2022-07-19 16:27:17,424 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 7 states have internal predecessors, (13), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:17,424 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 117 transitions. [2022-07-19 16:27:17,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-07-19 16:27:17,425 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:17,425 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:17,456 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-07-19 16:27:17,643 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:17,644 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:17,644 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:17,644 INFO L85 PathProgramCache]: Analyzing trace with hash -1954557947, now seen corresponding path program 1 times [2022-07-19 16:27:17,644 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:17,644 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1375273081] [2022-07-19 16:27:17,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:17,645 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:17,655 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:17,656 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2119049960] [2022-07-19 16:27:17,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:17,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:17,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:17,661 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-19 16:27:17,668 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-19 16:27:17,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:17,703 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 5 conjunts are in the unsatisfiable core [2022-07-19 16:27:17,704 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:17,734 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-07-19 16:27:17,735 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-07-19 16:27:17,735 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:17,735 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1375273081] [2022-07-19 16:27:17,735 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:17,735 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2119049960] [2022-07-19 16:27:17,735 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2119049960] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-19 16:27:17,735 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-19 16:27:17,735 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-07-19 16:27:17,735 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1038679141] [2022-07-19 16:27:17,735 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 16:27:17,736 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-07-19 16:27:17,736 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:17,736 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-19 16:27:17,736 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-07-19 16:27:17,736 INFO L87 Difference]: Start difference. First operand 91 states and 117 transitions. Second operand has 6 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-19 16:27:17,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:17,809 INFO L93 Difference]: Finished difference Result 133 states and 172 transitions. [2022-07-19 16:27:17,809 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-19 16:27:17,809 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 32 [2022-07-19 16:27:17,810 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:17,811 INFO L225 Difference]: With dead ends: 133 [2022-07-19 16:27:17,811 INFO L226 Difference]: Without dead ends: 121 [2022-07-19 16:27:17,812 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2022-07-19 16:27:17,812 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 7 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 84 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:17,813 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 84 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-07-19 16:27:17,814 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2022-07-19 16:27:17,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 105. [2022-07-19 16:27:17,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 82 states have (on average 1.3048780487804879) internal successors, (107), 84 states have internal predecessors, (107), 15 states have call successors, (15), 8 states have call predecessors, (15), 7 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-07-19 16:27:17,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 135 transitions. [2022-07-19 16:27:17,853 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 135 transitions. Word has length 32 [2022-07-19 16:27:17,853 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:17,853 INFO L495 AbstractCegarLoop]: Abstraction has 105 states and 135 transitions. [2022-07-19 16:27:17,853 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-19 16:27:17,853 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 135 transitions. [2022-07-19 16:27:17,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-07-19 16:27:17,859 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:17,860 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:17,882 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-19 16:27:18,073 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:18,073 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:18,074 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:18,074 INFO L85 PathProgramCache]: Analyzing trace with hash 346264643, now seen corresponding path program 1 times [2022-07-19 16:27:18,074 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:18,074 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [117910070] [2022-07-19 16:27:18,074 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:18,074 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:18,082 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:18,082 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [908426650] [2022-07-19 16:27:18,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:18,082 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:18,082 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:18,083 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-19 16:27:18,087 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-19 16:27:18,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-19 16:27:18,119 INFO L263 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-19 16:27:18,120 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:18,220 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-07-19 16:27:18,220 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:18,254 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-07-19 16:27:18,254 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:18,254 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [117910070] [2022-07-19 16:27:18,255 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:18,255 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [908426650] [2022-07-19 16:27:18,255 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [908426650] provided 1 perfect and 1 imperfect interpolant sequences [2022-07-19 16:27:18,255 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-07-19 16:27:18,255 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-07-19 16:27:18,255 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1862091139] [2022-07-19 16:27:18,256 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-19 16:27:18,256 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-07-19 16:27:18,256 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:18,256 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-07-19 16:27:18,257 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-07-19 16:27:18,257 INFO L87 Difference]: Start difference. First operand 105 states and 135 transitions. Second operand has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:18,423 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:18,423 INFO L93 Difference]: Finished difference Result 112 states and 141 transitions. [2022-07-19 16:27:18,423 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-07-19 16:27:18,423 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 32 [2022-07-19 16:27:18,424 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:18,424 INFO L225 Difference]: With dead ends: 112 [2022-07-19 16:27:18,424 INFO L226 Difference]: Without dead ends: 92 [2022-07-19 16:27:18,425 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 53 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2022-07-19 16:27:18,425 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 5 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 90 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:18,425 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 90 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 16:27:18,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-07-19 16:27:18,433 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 58. [2022-07-19 16:27:18,433 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 46 states have (on average 1.3043478260869565) internal successors, (60), 47 states have internal predecessors, (60), 6 states have call successors, (6), 5 states have call predecessors, (6), 5 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-07-19 16:27:18,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2022-07-19 16:27:18,434 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 32 [2022-07-19 16:27:18,434 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:18,434 INFO L495 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2022-07-19 16:27:18,434 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-19 16:27:18,434 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2022-07-19 16:27:18,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-07-19 16:27:18,435 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:18,435 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:18,453 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-19 16:27:18,639 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:18,639 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:18,640 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:18,640 INFO L85 PathProgramCache]: Analyzing trace with hash 136508765, now seen corresponding path program 2 times [2022-07-19 16:27:18,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:18,640 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1260265947] [2022-07-19 16:27:18,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:18,641 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:18,659 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:18,667 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1758434468] [2022-07-19 16:27:18,667 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-19 16:27:18,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:18,668 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:18,669 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-19 16:27:18,670 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-19 16:27:18,715 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-19 16:27:18,715 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 16:27:18,716 INFO L263 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-19 16:27:18,718 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:18,796 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 8 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:18,797 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:18,890 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 8 proven. 38 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-07-19 16:27:18,891 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:18,891 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1260265947] [2022-07-19 16:27:18,891 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:18,891 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1758434468] [2022-07-19 16:27:18,892 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1758434468] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 16:27:18,892 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 16:27:18,892 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 14 [2022-07-19 16:27:18,892 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [831721883] [2022-07-19 16:27:18,892 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 16:27:18,893 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-07-19 16:27:18,893 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:18,893 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-19 16:27:18,894 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-07-19 16:27:18,894 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 14 states, 14 states have (on average 4.428571428571429) internal successors, (62), 14 states have internal predecessors, (62), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-19 16:27:19,058 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:19,058 INFO L93 Difference]: Finished difference Result 132 states and 169 transitions. [2022-07-19 16:27:19,059 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-19 16:27:19,059 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.428571428571429) internal successors, (62), 14 states have internal predecessors, (62), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Word has length 46 [2022-07-19 16:27:19,059 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:19,061 INFO L225 Difference]: With dead ends: 132 [2022-07-19 16:27:19,061 INFO L226 Difference]: Without dead ends: 124 [2022-07-19 16:27:19,061 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 78 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-07-19 16:27:19,062 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 129 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 129 SdHoareTripleChecker+Valid, 196 SdHoareTripleChecker+Invalid, 83 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:19,063 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [129 Valid, 196 Invalid, 83 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 16:27:19,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-07-19 16:27:19,082 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2022-07-19 16:27:19,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 100 states have (on average 1.32) internal successors, (132), 101 states have internal predecessors, (132), 12 states have call successors, (12), 11 states have call predecessors, (12), 11 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-07-19 16:27:19,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 155 transitions. [2022-07-19 16:27:19,087 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 155 transitions. Word has length 46 [2022-07-19 16:27:19,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:19,087 INFO L495 AbstractCegarLoop]: Abstraction has 124 states and 155 transitions. [2022-07-19 16:27:19,087 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.428571428571429) internal successors, (62), 14 states have internal predecessors, (62), 9 states have call successors, (9), 6 states have call predecessors, (9), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-07-19 16:27:19,088 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 155 transitions. [2022-07-19 16:27:19,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2022-07-19 16:27:19,099 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:19,100 INFO L195 NwaCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:19,125 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-19 16:27:19,315 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,SelfDestructingSolverStorable9 [2022-07-19 16:27:19,316 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:19,316 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:19,316 INFO L85 PathProgramCache]: Analyzing trace with hash -1689445411, now seen corresponding path program 3 times [2022-07-19 16:27:19,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:19,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1395282107] [2022-07-19 16:27:19,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:19,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:19,327 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:19,327 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [19345744] [2022-07-19 16:27:19,327 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-07-19 16:27:19,327 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:19,328 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:19,329 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-19 16:27:19,331 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-19 16:27:19,575 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2022-07-19 16:27:19,575 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 16:27:19,578 INFO L263 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 23 conjunts are in the unsatisfiable core [2022-07-19 16:27:19,581 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:19,769 INFO L134 CoverageAnalysis]: Checked inductivity of 445 backedges. 20 proven. 425 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:19,769 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:20,028 INFO L134 CoverageAnalysis]: Checked inductivity of 445 backedges. 20 proven. 245 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-07-19 16:27:20,028 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:20,028 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1395282107] [2022-07-19 16:27:20,028 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:20,028 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [19345744] [2022-07-19 16:27:20,028 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [19345744] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 16:27:20,028 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 16:27:20,029 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14] total 26 [2022-07-19 16:27:20,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1731644992] [2022-07-19 16:27:20,029 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 16:27:20,029 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-07-19 16:27:20,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:20,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-07-19 16:27:20,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=281, Invalid=369, Unknown=0, NotChecked=0, Total=650 [2022-07-19 16:27:20,031 INFO L87 Difference]: Start difference. First operand 124 states and 155 transitions. Second operand has 26 states, 26 states have (on average 4.923076923076923) internal successors, (128), 26 states have internal predecessors, (128), 21 states have call successors, (21), 12 states have call predecessors, (21), 11 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2022-07-19 16:27:20,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:20,472 INFO L93 Difference]: Finished difference Result 264 states and 343 transitions. [2022-07-19 16:27:20,472 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2022-07-19 16:27:20,472 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 4.923076923076923) internal successors, (128), 26 states have internal predecessors, (128), 21 states have call successors, (21), 12 states have call predecessors, (21), 11 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) Word has length 100 [2022-07-19 16:27:20,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:20,474 INFO L225 Difference]: With dead ends: 264 [2022-07-19 16:27:20,474 INFO L226 Difference]: Without dead ends: 256 [2022-07-19 16:27:20,476 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 174 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 286 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=796, Invalid=1366, Unknown=0, NotChecked=0, Total=2162 [2022-07-19 16:27:20,476 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 387 mSDsluCounter, 290 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 387 SdHoareTripleChecker+Valid, 333 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:20,476 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [387 Valid, 333 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-07-19 16:27:20,477 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 256 states. [2022-07-19 16:27:20,497 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 256 to 256. [2022-07-19 16:27:20,497 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 208 states have (on average 1.3269230769230769) internal successors, (276), 209 states have internal predecessors, (276), 24 states have call successors, (24), 23 states have call predecessors, (24), 23 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-07-19 16:27:20,499 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 323 transitions. [2022-07-19 16:27:20,499 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 323 transitions. Word has length 100 [2022-07-19 16:27:20,499 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:20,499 INFO L495 AbstractCegarLoop]: Abstraction has 256 states and 323 transitions. [2022-07-19 16:27:20,500 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 4.923076923076923) internal successors, (128), 26 states have internal predecessors, (128), 21 states have call successors, (21), 12 states have call predecessors, (21), 11 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2022-07-19 16:27:20,500 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 323 transitions. [2022-07-19 16:27:20,502 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 209 [2022-07-19 16:27:20,502 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:20,502 INFO L195 NwaCegarLoop]: trace histogram [23, 23, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:20,513 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-19 16:27:20,708 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:20,708 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:20,709 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:20,709 INFO L85 PathProgramCache]: Analyzing trace with hash 482330845, now seen corresponding path program 4 times [2022-07-19 16:27:20,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:20,709 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1706337600] [2022-07-19 16:27:20,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:20,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:20,729 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:20,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [537150734] [2022-07-19 16:27:20,730 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-19 16:27:20,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:20,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:20,731 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-19 16:27:20,734 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-19 16:27:20,965 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-19 16:27:20,965 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 16:27:20,968 INFO L263 TraceCheckSpWp]: Trace formula consists of 630 conjuncts, 47 conjunts are in the unsatisfiable core [2022-07-19 16:27:20,974 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:21,456 INFO L134 CoverageAnalysis]: Checked inductivity of 2167 backedges. 44 proven. 2123 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:21,456 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:22,209 INFO L134 CoverageAnalysis]: Checked inductivity of 2167 backedges. 44 proven. 1199 refuted. 0 times theorem prover too weak. 924 trivial. 0 not checked. [2022-07-19 16:27:22,209 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:22,209 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1706337600] [2022-07-19 16:27:22,209 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:22,209 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [537150734] [2022-07-19 16:27:22,210 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [537150734] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 16:27:22,210 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 16:27:22,210 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 26] total 50 [2022-07-19 16:27:22,210 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [425146578] [2022-07-19 16:27:22,210 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 16:27:22,211 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2022-07-19 16:27:22,211 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:22,212 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2022-07-19 16:27:22,213 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1133, Invalid=1317, Unknown=0, NotChecked=0, Total=2450 [2022-07-19 16:27:22,214 INFO L87 Difference]: Start difference. First operand 256 states and 323 transitions. Second operand has 50 states, 50 states have (on average 5.2) internal successors, (260), 50 states have internal predecessors, (260), 45 states have call successors, (45), 24 states have call predecessors, (45), 23 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2022-07-19 16:27:23,642 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:23,643 INFO L93 Difference]: Finished difference Result 528 states and 691 transitions. [2022-07-19 16:27:23,643 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2022-07-19 16:27:23,643 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 5.2) internal successors, (260), 50 states have internal predecessors, (260), 45 states have call successors, (45), 24 states have call predecessors, (45), 23 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) Word has length 208 [2022-07-19 16:27:23,644 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:23,647 INFO L225 Difference]: With dead ends: 528 [2022-07-19 16:27:23,647 INFO L226 Difference]: Without dead ends: 520 [2022-07-19 16:27:23,650 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 459 GetRequests, 366 SyntacticMatches, 0 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1288 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=3316, Invalid=5614, Unknown=0, NotChecked=0, Total=8930 [2022-07-19 16:27:23,650 INFO L413 NwaCegarLoop]: 67 mSDtfsCounter, 1344 mSDsluCounter, 561 mSDsCounter, 0 mSdLazyCounter, 304 mSolverCounterSat, 208 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1344 SdHoareTripleChecker+Valid, 628 SdHoareTripleChecker+Invalid, 512 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 208 IncrementalHoareTripleChecker+Valid, 304 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:23,651 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1344 Valid, 628 Invalid, 512 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [208 Valid, 304 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-07-19 16:27:23,651 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 520 states. [2022-07-19 16:27:23,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 520 to 520. [2022-07-19 16:27:23,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 520 states, 424 states have (on average 1.330188679245283) internal successors, (564), 425 states have internal predecessors, (564), 48 states have call successors, (48), 47 states have call predecessors, (48), 47 states have return successors, (47), 47 states have call predecessors, (47), 47 states have call successors, (47) [2022-07-19 16:27:23,690 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 520 states to 520 states and 659 transitions. [2022-07-19 16:27:23,690 INFO L78 Accepts]: Start accepts. Automaton has 520 states and 659 transitions. Word has length 208 [2022-07-19 16:27:23,691 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:23,691 INFO L495 AbstractCegarLoop]: Abstraction has 520 states and 659 transitions. [2022-07-19 16:27:23,691 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 50 states have (on average 5.2) internal successors, (260), 50 states have internal predecessors, (260), 45 states have call successors, (45), 24 states have call predecessors, (45), 23 states have return successors, (44), 44 states have call predecessors, (44), 44 states have call successors, (44) [2022-07-19 16:27:23,691 INFO L276 IsEmpty]: Start isEmpty. Operand 520 states and 659 transitions. [2022-07-19 16:27:23,697 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 425 [2022-07-19 16:27:23,697 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:23,697 INFO L195 NwaCegarLoop]: trace histogram [47, 47, 46, 46, 46, 46, 46, 46, 46, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:23,724 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-07-19 16:27:23,919 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,SelfDestructingSolverStorable11 [2022-07-19 16:27:23,920 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:23,920 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:23,920 INFO L85 PathProgramCache]: Analyzing trace with hash -1031888163, now seen corresponding path program 5 times [2022-07-19 16:27:23,920 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:23,920 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1134261555] [2022-07-19 16:27:23,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:23,920 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:23,951 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:23,958 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1257867910] [2022-07-19 16:27:23,958 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-19 16:27:23,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:23,958 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:23,959 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-19 16:27:23,970 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-19 16:27:27,215 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 47 check-sat command(s) [2022-07-19 16:27:27,215 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-19 16:27:27,228 INFO L263 TraceCheckSpWp]: Trace formula consists of 1254 conjuncts, 95 conjunts are in the unsatisfiable core [2022-07-19 16:27:27,238 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-19 16:27:28,471 INFO L134 CoverageAnalysis]: Checked inductivity of 9499 backedges. 92 proven. 9407 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-19 16:27:28,471 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-19 16:27:30,877 INFO L134 CoverageAnalysis]: Checked inductivity of 9499 backedges. 92 proven. 5267 refuted. 0 times theorem prover too weak. 4140 trivial. 0 not checked. [2022-07-19 16:27:30,878 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-19 16:27:30,878 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1134261555] [2022-07-19 16:27:30,878 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-07-19 16:27:30,878 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1257867910] [2022-07-19 16:27:30,878 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1257867910] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-19 16:27:30,878 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-07-19 16:27:30,879 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 50] total 98 [2022-07-19 16:27:30,879 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [197214881] [2022-07-19 16:27:30,879 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-07-19 16:27:30,880 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 98 states [2022-07-19 16:27:30,880 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-19 16:27:30,882 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 98 interpolants. [2022-07-19 16:27:30,884 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=4565, Invalid=4941, Unknown=0, NotChecked=0, Total=9506 [2022-07-19 16:27:30,884 INFO L87 Difference]: Start difference. First operand 520 states and 659 transitions. Second operand has 98 states, 98 states have (on average 5.346938775510204) internal successors, (524), 98 states have internal predecessors, (524), 93 states have call successors, (93), 48 states have call predecessors, (93), 47 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2022-07-19 16:27:36,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-19 16:27:36,030 INFO L93 Difference]: Finished difference Result 1056 states and 1387 transitions. [2022-07-19 16:27:36,030 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 190 states. [2022-07-19 16:27:36,031 INFO L78 Accepts]: Start accepts. Automaton has has 98 states, 98 states have (on average 5.346938775510204) internal successors, (524), 98 states have internal predecessors, (524), 93 states have call successors, (93), 48 states have call predecessors, (93), 47 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) Word has length 424 [2022-07-19 16:27:36,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-07-19 16:27:36,036 INFO L225 Difference]: With dead ends: 1056 [2022-07-19 16:27:36,036 INFO L226 Difference]: Without dead ends: 1048 [2022-07-19 16:27:36,044 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 939 GetRequests, 750 SyntacticMatches, 0 SemanticMatches, 189 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5452 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=13540, Invalid=22750, Unknown=0, NotChecked=0, Total=36290 [2022-07-19 16:27:36,044 INFO L413 NwaCegarLoop]: 115 mSDtfsCounter, 3026 mSDsluCounter, 1110 mSDsCounter, 0 mSdLazyCounter, 632 mSolverCounterSat, 471 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3026 SdHoareTripleChecker+Valid, 1225 SdHoareTripleChecker+Invalid, 1103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 471 IncrementalHoareTripleChecker+Valid, 632 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-07-19 16:27:36,045 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [3026 Valid, 1225 Invalid, 1103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [471 Valid, 632 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-07-19 16:27:36,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1048 states. [2022-07-19 16:27:36,123 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1048 to 1048. [2022-07-19 16:27:36,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1048 states, 856 states have (on average 1.3317757009345794) internal successors, (1140), 857 states have internal predecessors, (1140), 96 states have call successors, (96), 95 states have call predecessors, (96), 95 states have return successors, (95), 95 states have call predecessors, (95), 95 states have call successors, (95) [2022-07-19 16:27:36,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1048 states to 1048 states and 1331 transitions. [2022-07-19 16:27:36,129 INFO L78 Accepts]: Start accepts. Automaton has 1048 states and 1331 transitions. Word has length 424 [2022-07-19 16:27:36,130 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-07-19 16:27:36,130 INFO L495 AbstractCegarLoop]: Abstraction has 1048 states and 1331 transitions. [2022-07-19 16:27:36,131 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 98 states, 98 states have (on average 5.346938775510204) internal successors, (524), 98 states have internal predecessors, (524), 93 states have call successors, (93), 48 states have call predecessors, (93), 47 states have return successors, (92), 92 states have call predecessors, (92), 92 states have call successors, (92) [2022-07-19 16:27:36,131 INFO L276 IsEmpty]: Start isEmpty. Operand 1048 states and 1331 transitions. [2022-07-19 16:27:36,151 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 857 [2022-07-19 16:27:36,151 INFO L187 NwaCegarLoop]: Found error trace [2022-07-19 16:27:36,152 INFO L195 NwaCegarLoop]: trace histogram [95, 95, 94, 94, 94, 94, 94, 94, 94, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-19 16:27:36,172 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-07-19 16:27:36,364 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,SelfDestructingSolverStorable12 [2022-07-19 16:27:36,365 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-07-19 16:27:36,365 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-19 16:27:36,365 INFO L85 PathProgramCache]: Analyzing trace with hash 1549948637, now seen corresponding path program 6 times [2022-07-19 16:27:36,365 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-19 16:27:36,365 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2063400841] [2022-07-19 16:27:36,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-19 16:27:36,366 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-19 16:27:36,403 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-07-19 16:27:36,403 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1654407441] [2022-07-19 16:27:36,403 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-07-19 16:27:36,403 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-19 16:27:36,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-19 16:27:36,405 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-19 16:27:36,410 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process