./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/uthash-2.0.2/uthash_FNV_test1-1.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version ff03de63 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/uthash-2.0.2/uthash_FNV_test1-1.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-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 ! overflow) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 72c3cbe0b435a963730c7c79c0d825f3c978c53ad7cc61822ef9417e2e6ee67f --- Real Ultimate output --- This is Ultimate 0.2.2-dev-ff03de6 [2021-12-21 20:54:40,936 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-21 20:54:40,937 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-21 20:54:40,989 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-21 20:54:40,989 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-21 20:54:40,990 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-21 20:54:40,991 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-21 20:54:40,992 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-21 20:54:40,993 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-21 20:54:40,994 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-21 20:54:40,995 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-21 20:54:40,995 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-21 20:54:40,996 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-21 20:54:40,996 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-21 20:54:40,997 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-21 20:54:40,998 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-21 20:54:40,998 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-21 20:54:40,999 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-21 20:54:41,000 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-21 20:54:41,001 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-21 20:54:41,002 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-21 20:54:41,003 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-21 20:54:41,003 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-21 20:54:41,004 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-21 20:54:41,006 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-21 20:54:41,006 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-21 20:54:41,006 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-21 20:54:41,007 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-21 20:54:41,007 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-21 20:54:41,008 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-21 20:54:41,008 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-21 20:54:41,009 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-21 20:54:41,009 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-21 20:54:41,010 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-21 20:54:41,011 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-21 20:54:41,011 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-21 20:54:41,011 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-21 20:54:41,012 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-21 20:54:41,012 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-21 20:54:41,012 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-21 20:54:41,013 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-21 20:54:41,014 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2021-12-21 20:54:41,027 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-21 20:54:41,027 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-21 20:54:41,027 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-21 20:54:41,028 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-21 20:54:41,028 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-21 20:54:41,028 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-21 20:54:41,029 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-21 20:54:41,029 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-21 20:54:41,029 INFO L138 SettingsManager]: * Use SBE=true [2021-12-21 20:54:41,029 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-21 20:54:41,029 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-21 20:54:41,029 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-21 20:54:41,030 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-21 20:54:41,030 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-21 20:54:41,043 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-21 20:54:41,043 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-21 20:54:41,044 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-21 20:54:41,044 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-21 20:54:41,044 INFO L138 SettingsManager]: * Check absence of signed integer overflows=true [2021-12-21 20:54:41,044 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-21 20:54:41,044 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-21 20:54:41,044 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-21 20:54:41,044 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-21 20:54:41,045 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-21 20:54:41,045 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-21 20:54:41,045 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-21 20:54:41,045 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-21 20:54:41,045 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-21 20:54:41,046 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-21 20:54:41,046 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-21 20:54:41,046 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-21 20:54:41,046 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-21 20:54:41,046 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-21 20:54:41,046 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-21 20:54:41,047 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 ! overflow) ) 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 -> 72c3cbe0b435a963730c7c79c0d825f3c978c53ad7cc61822ef9417e2e6ee67f [2021-12-21 20:54:41,181 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-21 20:54:41,206 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-21 20:54:41,208 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-21 20:54:41,209 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-21 20:54:41,210 INFO L275 PluginConnector]: CDTParser initialized [2021-12-21 20:54:41,211 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/uthash-2.0.2/uthash_FNV_test1-1.i [2021-12-21 20:54:41,268 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/248b12119/66b9ab9b78e440d8bbc0726cca61aa72/FLAG71266def6 [2021-12-21 20:54:41,696 INFO L306 CDTParser]: Found 1 translation units. [2021-12-21 20:54:41,696 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/uthash-2.0.2/uthash_FNV_test1-1.i [2021-12-21 20:54:41,716 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/248b12119/66b9ab9b78e440d8bbc0726cca61aa72/FLAG71266def6 [2021-12-21 20:54:42,034 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/248b12119/66b9ab9b78e440d8bbc0726cca61aa72 [2021-12-21 20:54:42,036 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-21 20:54:42,037 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-21 20:54:42,038 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-21 20:54:42,038 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-21 20:54:42,040 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-21 20:54:42,041 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,041 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@79a5584b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42, skipping insertion in model container [2021-12-21 20:54:42,041 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,046 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-21 20:54:42,087 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-21 20:54:42,374 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/uthash-2.0.2/uthash_FNV_test1-1.i[33021,33034] [2021-12-21 20:54:42,457 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 20:54:42,465 INFO L203 MainTranslator]: Completed pre-run [2021-12-21 20:54:42,495 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/uthash-2.0.2/uthash_FNV_test1-1.i[33021,33034] [2021-12-21 20:54:42,539 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 20:54:42,569 INFO L208 MainTranslator]: Completed translation [2021-12-21 20:54:42,569 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42 WrapperNode [2021-12-21 20:54:42,569 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-21 20:54:42,570 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-21 20:54:42,570 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-21 20:54:42,570 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-21 20:54:42,575 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,603 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,653 INFO L137 Inliner]: procedures = 177, calls = 186, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 627 [2021-12-21 20:54:42,657 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-21 20:54:42,657 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-21 20:54:42,658 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-21 20:54:42,658 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-21 20:54:42,663 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,664 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,679 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,681 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,713 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,728 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,732 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,739 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-21 20:54:42,744 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-21 20:54:42,744 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-21 20:54:42,745 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-21 20:54:42,746 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (1/1) ... [2021-12-21 20:54:42,751 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-21 20:54:42,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:42,784 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) [2021-12-21 20:54:42,786 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 [2021-12-21 20:54:42,812 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-12-21 20:54:42,812 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-21 20:54:42,813 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-21 20:54:42,813 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-12-21 20:54:42,813 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset [2021-12-21 20:54:42,813 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset [2021-12-21 20:54:42,814 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-21 20:54:42,814 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-21 20:54:42,814 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-21 20:54:42,817 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-21 20:54:42,817 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-21 20:54:42,818 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-21 20:54:42,818 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-21 20:54:42,818 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-21 20:54:42,818 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-21 20:54:42,917 INFO L234 CfgBuilder]: Building ICFG [2021-12-21 20:54:42,919 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-21 20:54:43,362 INFO L275 CfgBuilder]: Performing block encoding [2021-12-21 20:54:43,366 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-21 20:54:43,367 INFO L299 CfgBuilder]: Removed 31 assume(true) statements. [2021-12-21 20:54:43,368 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 08:54:43 BoogieIcfgContainer [2021-12-21 20:54:43,368 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-21 20:54:43,369 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-21 20:54:43,369 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-21 20:54:43,372 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-21 20:54:43,372 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.12 08:54:42" (1/3) ... [2021-12-21 20:54:43,372 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@588e0ce7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 08:54:43, skipping insertion in model container [2021-12-21 20:54:43,372 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 08:54:42" (2/3) ... [2021-12-21 20:54:43,373 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@588e0ce7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 08:54:43, skipping insertion in model container [2021-12-21 20:54:43,373 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 08:54:43" (3/3) ... [2021-12-21 20:54:43,373 INFO L111 eAbstractionObserver]: Analyzing ICFG uthash_FNV_test1-1.i [2021-12-21 20:54:43,377 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-21 20:54:43,377 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 6 error locations. [2021-12-21 20:54:43,403 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-21 20:54:43,407 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=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, mLoopAccelerationTechnique=FAST_UPR [2021-12-21 20:54:43,407 INFO L340 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2021-12-21 20:54:43,418 INFO L276 IsEmpty]: Start isEmpty. Operand has 138 states, 116 states have (on average 1.6810344827586208) internal successors, (195), 132 states have internal predecessors, (195), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 4 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-21 20:54:43,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2021-12-21 20:54:43,420 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:43,420 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2021-12-21 20:54:43,421 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:43,424 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:43,424 INFO L85 PathProgramCache]: Analyzing trace with hash 1126635289, now seen corresponding path program 1 times [2021-12-21 20:54:43,429 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:43,429 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [638828168] [2021-12-21 20:54:43,430 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:43,430 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:43,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:43,519 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:43,520 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:43,520 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [638828168] [2021-12-21 20:54:43,521 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [638828168] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:43,521 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:43,521 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 20:54:43,522 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2047034796] [2021-12-21 20:54:43,522 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:43,525 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-21 20:54:43,525 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:43,540 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-21 20:54:43,541 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-21 20:54:43,542 INFO L87 Difference]: Start difference. First operand has 138 states, 116 states have (on average 1.6810344827586208) internal successors, (195), 132 states have internal predecessors, (195), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 4 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:43,588 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:43,589 INFO L93 Difference]: Finished difference Result 366 states and 607 transitions. [2021-12-21 20:54:43,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-21 20:54:43,590 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2021-12-21 20:54:43,591 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:43,600 INFO L225 Difference]: With dead ends: 366 [2021-12-21 20:54:43,601 INFO L226 Difference]: Without dead ends: 226 [2021-12-21 20:54:43,607 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-21 20:54:43,610 INFO L933 BasicCegarLoop]: 211 mSDtfsCounter, 113 mSDsluCounter, 175 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 116 SdHoareTripleChecker+Valid, 386 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:43,610 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [116 Valid, 386 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:43,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2021-12-21 20:54:43,638 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 137. [2021-12-21 20:54:43,639 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 117 states have (on average 1.3504273504273505) internal successors, (158), 131 states have internal predecessors, (158), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 4 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-21 20:54:43,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 184 transitions. [2021-12-21 20:54:43,641 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 184 transitions. Word has length 6 [2021-12-21 20:54:43,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:43,641 INFO L470 AbstractCegarLoop]: Abstraction has 137 states and 184 transitions. [2021-12-21 20:54:43,642 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:43,642 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 184 transitions. [2021-12-21 20:54:43,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2021-12-21 20:54:43,644 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:43,644 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:43,644 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-12-21 20:54:43,644 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:43,645 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:43,645 INFO L85 PathProgramCache]: Analyzing trace with hash -1116651610, now seen corresponding path program 1 times [2021-12-21 20:54:43,645 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:43,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [309484041] [2021-12-21 20:54:43,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:43,645 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:43,778 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:43,778 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1680505352] [2021-12-21 20:54:43,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:43,779 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:43,779 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:43,796 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) [2021-12-21 20:54:43,814 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-21 20:54:44,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:44,257 INFO L263 TraceCheckSpWp]: Trace formula consists of 1511 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-21 20:54:44,265 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:44,379 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:44,380 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:54:44,380 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:44,380 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [309484041] [2021-12-21 20:54:44,380 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:44,381 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1680505352] [2021-12-21 20:54:44,381 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1680505352] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:44,381 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:44,381 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 20:54:44,382 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2029950947] [2021-12-21 20:54:44,382 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:44,382 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-21 20:54:44,383 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:44,383 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-21 20:54:44,383 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-21 20:54:44,383 INFO L87 Difference]: Start difference. First operand 137 states and 184 transitions. Second operand has 3 states, 3 states have (on average 18.666666666666668) internal successors, (56), 3 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:44,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:44,434 INFO L93 Difference]: Finished difference Result 289 states and 393 transitions. [2021-12-21 20:54:44,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-21 20:54:44,434 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 18.666666666666668) internal successors, (56), 3 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 56 [2021-12-21 20:54:44,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:44,436 INFO L225 Difference]: With dead ends: 289 [2021-12-21 20:54:44,436 INFO L226 Difference]: Without dead ends: 158 [2021-12-21 20:54:44,436 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-21 20:54:44,437 INFO L933 BasicCegarLoop]: 160 mSDtfsCounter, 9 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 305 SdHoareTripleChecker+Invalid, 72 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:44,438 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 305 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:44,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2021-12-21 20:54:44,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 157. [2021-12-21 20:54:44,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 137 states have (on average 1.2992700729927007) internal successors, (178), 151 states have internal predecessors, (178), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 4 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-21 20:54:44,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 204 transitions. [2021-12-21 20:54:44,446 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 204 transitions. Word has length 56 [2021-12-21 20:54:44,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:44,446 INFO L470 AbstractCegarLoop]: Abstraction has 157 states and 204 transitions. [2021-12-21 20:54:44,446 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 18.666666666666668) internal successors, (56), 3 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:44,446 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 204 transitions. [2021-12-21 20:54:44,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2021-12-21 20:54:44,447 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:44,447 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:44,491 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:44,667 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:44,667 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:44,668 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:44,668 INFO L85 PathProgramCache]: Analyzing trace with hash -1391411224, now seen corresponding path program 1 times [2021-12-21 20:54:44,668 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:44,668 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [108374823] [2021-12-21 20:54:44,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:44,669 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:44,775 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:44,776 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1645111569] [2021-12-21 20:54:44,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:44,776 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:44,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:44,794 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) [2021-12-21 20:54:44,843 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-21 20:54:45,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:45,278 INFO L263 TraceCheckSpWp]: Trace formula consists of 1513 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-21 20:54:45,281 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:45,350 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:45,350 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:54:45,350 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:45,350 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [108374823] [2021-12-21 20:54:45,350 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:45,351 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1645111569] [2021-12-21 20:54:45,351 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1645111569] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:45,351 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:45,351 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-21 20:54:45,351 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1531406266] [2021-12-21 20:54:45,351 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:45,352 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 20:54:45,352 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:45,352 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 20:54:45,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 20:54:45,352 INFO L87 Difference]: Start difference. First operand 157 states and 204 transitions. Second operand has 4 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:45,399 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:45,399 INFO L93 Difference]: Finished difference Result 299 states and 393 transitions. [2021-12-21 20:54:45,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 20:54:45,400 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 56 [2021-12-21 20:54:45,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:45,400 INFO L225 Difference]: With dead ends: 299 [2021-12-21 20:54:45,401 INFO L226 Difference]: Without dead ends: 148 [2021-12-21 20:54:45,401 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 20:54:45,402 INFO L933 BasicCegarLoop]: 161 mSDtfsCounter, 135 mSDsluCounter, 178 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 148 SdHoareTripleChecker+Valid, 339 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:45,402 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [148 Valid, 339 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:45,403 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2021-12-21 20:54:45,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 143. [2021-12-21 20:54:45,409 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 143 states, 123 states have (on average 1.2764227642276422) internal successors, (157), 137 states have internal predecessors, (157), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (13), 4 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-21 20:54:45,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 143 states to 143 states and 183 transitions. [2021-12-21 20:54:45,410 INFO L78 Accepts]: Start accepts. Automaton has 143 states and 183 transitions. Word has length 56 [2021-12-21 20:54:45,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:45,410 INFO L470 AbstractCegarLoop]: Abstraction has 143 states and 183 transitions. [2021-12-21 20:54:45,410 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 14.0) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:45,410 INFO L276 IsEmpty]: Start isEmpty. Operand 143 states and 183 transitions. [2021-12-21 20:54:45,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2021-12-21 20:54:45,411 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:45,411 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:45,435 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:45,633 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2021-12-21 20:54:45,633 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:45,634 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:45,634 INFO L85 PathProgramCache]: Analyzing trace with hash 632524954, now seen corresponding path program 1 times [2021-12-21 20:54:45,634 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:45,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1671734315] [2021-12-21 20:54:45,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:45,634 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:45,717 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:45,718 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [746174867] [2021-12-21 20:54:45,718 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:45,718 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:45,718 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:45,719 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) [2021-12-21 20:54:45,736 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-21 20:54:46,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:46,209 INFO L263 TraceCheckSpWp]: Trace formula consists of 1499 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-21 20:54:46,212 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:46,308 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:46,308 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:54:46,308 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:46,308 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1671734315] [2021-12-21 20:54:46,308 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:46,308 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [746174867] [2021-12-21 20:54:46,309 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [746174867] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:46,309 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:46,309 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 20:54:46,309 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [229735236] [2021-12-21 20:54:46,309 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:46,309 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 20:54:46,310 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:46,310 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 20:54:46,310 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 20:54:46,310 INFO L87 Difference]: Start difference. First operand 143 states and 183 transitions. Second operand has 4 states, 3 states have (on average 18.666666666666668) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:46,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:46,335 INFO L93 Difference]: Finished difference Result 238 states and 298 transitions. [2021-12-21 20:54:46,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 20:54:46,336 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 18.666666666666668) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 56 [2021-12-21 20:54:46,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:46,337 INFO L225 Difference]: With dead ends: 238 [2021-12-21 20:54:46,337 INFO L226 Difference]: Without dead ends: 237 [2021-12-21 20:54:46,337 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 20:54:46,338 INFO L933 BasicCegarLoop]: 168 mSDtfsCounter, 55 mSDsluCounter, 330 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 58 SdHoareTripleChecker+Valid, 498 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:46,338 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [58 Valid, 498 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:46,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 237 states. [2021-12-21 20:54:46,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 237 to 235. [2021-12-21 20:54:46,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 212 states have (on average 1.240566037735849) internal successors, (263), 226 states have internal predecessors, (263), 16 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (16), 7 states have call predecessors, (16), 16 states have call successors, (16) [2021-12-21 20:54:46,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 295 transitions. [2021-12-21 20:54:46,347 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 295 transitions. Word has length 56 [2021-12-21 20:54:46,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:46,347 INFO L470 AbstractCegarLoop]: Abstraction has 235 states and 295 transitions. [2021-12-21 20:54:46,347 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 18.666666666666668) internal successors, (56), 4 states have internal predecessors, (56), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:46,348 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 295 transitions. [2021-12-21 20:54:46,348 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2021-12-21 20:54:46,348 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:46,349 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:46,371 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:46,565 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:46,565 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr3ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:46,566 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:46,566 INFO L85 PathProgramCache]: Analyzing trace with hash -1866562491, now seen corresponding path program 1 times [2021-12-21 20:54:46,566 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:46,566 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1566570812] [2021-12-21 20:54:46,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:46,566 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:46,630 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:46,630 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [515942303] [2021-12-21 20:54:46,630 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:46,630 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:46,631 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:46,645 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) [2021-12-21 20:54:46,700 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-21 20:54:47,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:47,220 INFO L263 TraceCheckSpWp]: Trace formula consists of 1500 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-21 20:54:47,225 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:47,341 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:47,342 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:54:47,363 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:47,363 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1566570812] [2021-12-21 20:54:47,363 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:47,364 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [515942303] [2021-12-21 20:54:47,364 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [515942303] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:47,365 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:47,365 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 20:54:47,365 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [679328825] [2021-12-21 20:54:47,365 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:47,366 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 20:54:47,366 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:47,366 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 20:54:47,366 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 20:54:47,366 INFO L87 Difference]: Start difference. First operand 235 states and 295 transitions. Second operand has 4 states, 3 states have (on average 19.0) internal successors, (57), 4 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:47,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:47,450 INFO L93 Difference]: Finished difference Result 235 states and 295 transitions. [2021-12-21 20:54:47,467 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 20:54:47,467 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 19.0) internal successors, (57), 4 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 57 [2021-12-21 20:54:47,468 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:47,468 INFO L225 Difference]: With dead ends: 235 [2021-12-21 20:54:47,469 INFO L226 Difference]: Without dead ends: 234 [2021-12-21 20:54:47,469 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 20:54:47,471 INFO L933 BasicCegarLoop]: 162 mSDtfsCounter, 85 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 344 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:47,471 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [98 Valid, 344 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 20:54:47,472 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 234 states. [2021-12-21 20:54:47,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 234 to 234. [2021-12-21 20:54:47,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 234 states, 212 states have (on average 1.2358490566037736) internal successors, (262), 225 states have internal predecessors, (262), 16 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (16), 7 states have call predecessors, (16), 16 states have call successors, (16) [2021-12-21 20:54:47,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 234 states to 234 states and 294 transitions. [2021-12-21 20:54:47,488 INFO L78 Accepts]: Start accepts. Automaton has 234 states and 294 transitions. Word has length 57 [2021-12-21 20:54:47,488 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:47,491 INFO L470 AbstractCegarLoop]: Abstraction has 234 states and 294 transitions. [2021-12-21 20:54:47,491 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 19.0) internal successors, (57), 4 states have internal predecessors, (57), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:47,491 INFO L276 IsEmpty]: Start isEmpty. Operand 234 states and 294 transitions. [2021-12-21 20:54:47,492 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2021-12-21 20:54:47,492 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:47,492 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:47,515 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:47,711 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:47,711 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:47,712 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:47,712 INFO L85 PathProgramCache]: Analyzing trace with hash 1237589276, now seen corresponding path program 1 times [2021-12-21 20:54:47,712 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:47,712 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [362741393] [2021-12-21 20:54:47,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:47,712 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:47,788 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:47,789 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1086853593] [2021-12-21 20:54:47,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:47,789 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:47,789 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:47,790 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) [2021-12-21 20:54:47,811 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-21 20:54:48,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:48,470 INFO L263 TraceCheckSpWp]: Trace formula consists of 1523 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-21 20:54:48,472 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:48,588 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:48,588 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:54:48,685 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:48,685 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:48,685 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [362741393] [2021-12-21 20:54:48,685 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:48,685 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1086853593] [2021-12-21 20:54:48,685 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1086853593] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:54:48,686 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:54:48,686 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2021-12-21 20:54:48,686 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1470906978] [2021-12-21 20:54:48,686 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:54:48,686 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-21 20:54:48,686 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:48,687 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-21 20:54:48,687 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2021-12-21 20:54:48,687 INFO L87 Difference]: Start difference. First operand 234 states and 294 transitions. Second operand has 8 states, 8 states have (on average 14.75) internal successors, (118), 8 states have internal predecessors, (118), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:48,760 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:48,760 INFO L93 Difference]: Finished difference Result 367 states and 469 transitions. [2021-12-21 20:54:48,760 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 20:54:48,761 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 14.75) internal successors, (118), 8 states have internal predecessors, (118), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 61 [2021-12-21 20:54:48,761 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:48,762 INFO L225 Difference]: With dead ends: 367 [2021-12-21 20:54:48,762 INFO L226 Difference]: Without dead ends: 333 [2021-12-21 20:54:48,763 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=35, Invalid=55, Unknown=0, NotChecked=0, Total=90 [2021-12-21 20:54:48,763 INFO L933 BasicCegarLoop]: 199 mSDtfsCounter, 522 mSDsluCounter, 515 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 531 SdHoareTripleChecker+Valid, 714 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:48,763 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [531 Valid, 714 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:48,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2021-12-21 20:54:48,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 333. [2021-12-21 20:54:48,773 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 333 states, 308 states have (on average 1.2207792207792207) internal successors, (376), 321 states have internal predecessors, (376), 19 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (19), 10 states have call predecessors, (19), 19 states have call successors, (19) [2021-12-21 20:54:48,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 414 transitions. [2021-12-21 20:54:48,774 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 414 transitions. Word has length 61 [2021-12-21 20:54:48,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:48,775 INFO L470 AbstractCegarLoop]: Abstraction has 333 states and 414 transitions. [2021-12-21 20:54:48,775 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 14.75) internal successors, (118), 8 states have internal predecessors, (118), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:48,775 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 414 transitions. [2021-12-21 20:54:48,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2021-12-21 20:54:48,776 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:48,776 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:48,817 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:48,997 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:48,998 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:48,998 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:48,999 INFO L85 PathProgramCache]: Analyzing trace with hash 1237285228, now seen corresponding path program 1 times [2021-12-21 20:54:48,999 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:48,999 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [637114808] [2021-12-21 20:54:48,999 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:48,999 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:49,109 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:49,109 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [931804827] [2021-12-21 20:54:49,110 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:49,110 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:49,110 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:49,111 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) [2021-12-21 20:54:49,127 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-21 20:54:49,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:49,857 INFO L263 TraceCheckSpWp]: Trace formula consists of 1529 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-21 20:54:49,859 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:50,062 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:50,062 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:54:50,062 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:50,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [637114808] [2021-12-21 20:54:50,063 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:50,063 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [931804827] [2021-12-21 20:54:50,063 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [931804827] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:50,063 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:50,063 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 20:54:50,063 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [954289403] [2021-12-21 20:54:50,063 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:50,064 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-21 20:54:50,064 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:50,064 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-21 20:54:50,064 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-21 20:54:50,065 INFO L87 Difference]: Start difference. First operand 333 states and 414 transitions. Second operand has 3 states, 3 states have (on average 20.333333333333332) internal successors, (61), 3 states have internal predecessors, (61), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:50,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:50,109 INFO L93 Difference]: Finished difference Result 606 states and 760 transitions. [2021-12-21 20:54:50,114 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-21 20:54:50,115 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 20.333333333333332) internal successors, (61), 3 states have internal predecessors, (61), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 61 [2021-12-21 20:54:50,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:50,116 INFO L225 Difference]: With dead ends: 606 [2021-12-21 20:54:50,116 INFO L226 Difference]: Without dead ends: 331 [2021-12-21 20:54:50,117 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 59 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-21 20:54:50,117 INFO L933 BasicCegarLoop]: 171 mSDtfsCounter, 15 mSDsluCounter, 156 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 327 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:50,118 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 327 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:50,119 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 331 states. [2021-12-21 20:54:50,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 331 to 331. [2021-12-21 20:54:50,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 331 states, 306 states have (on average 1.2189542483660132) internal successors, (373), 319 states have internal predecessors, (373), 19 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (19), 10 states have call predecessors, (19), 19 states have call successors, (19) [2021-12-21 20:54:50,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 331 states to 331 states and 411 transitions. [2021-12-21 20:54:50,128 INFO L78 Accepts]: Start accepts. Automaton has 331 states and 411 transitions. Word has length 61 [2021-12-21 20:54:50,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:50,129 INFO L470 AbstractCegarLoop]: Abstraction has 331 states and 411 transitions. [2021-12-21 20:54:50,129 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 20.333333333333332) internal successors, (61), 3 states have internal predecessors, (61), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-21 20:54:50,129 INFO L276 IsEmpty]: Start isEmpty. Operand 331 states and 411 transitions. [2021-12-21 20:54:50,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2021-12-21 20:54:50,130 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:50,130 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:50,151 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:50,350 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:50,350 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:50,351 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:50,351 INFO L85 PathProgramCache]: Analyzing trace with hash -1438130325, now seen corresponding path program 1 times [2021-12-21 20:54:50,351 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:50,351 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1880581798] [2021-12-21 20:54:50,351 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:50,351 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:50,404 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:50,404 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [496883563] [2021-12-21 20:54:50,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:50,404 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:50,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:50,406 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) [2021-12-21 20:54:50,408 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-21 20:54:51,136 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:51,142 INFO L263 TraceCheckSpWp]: Trace formula consists of 666 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 20:54:51,144 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:51,314 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 20:54:51,315 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:54:51,315 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:51,319 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1880581798] [2021-12-21 20:54:51,319 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:51,319 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [496883563] [2021-12-21 20:54:51,319 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [496883563] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:51,319 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:51,320 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-21 20:54:51,320 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1599528878] [2021-12-21 20:54:51,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:51,320 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 20:54:51,320 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:51,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 20:54:51,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 20:54:51,321 INFO L87 Difference]: Start difference. First operand 331 states and 411 transitions. Second operand has 4 states, 4 states have (on average 18.0) internal successors, (72), 4 states have internal predecessors, (72), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 20:54:51,390 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:51,390 INFO L93 Difference]: Finished difference Result 613 states and 776 transitions. [2021-12-21 20:54:51,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 20:54:51,391 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 18.0) internal successors, (72), 4 states have internal predecessors, (72), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 76 [2021-12-21 20:54:51,391 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:51,394 INFO L225 Difference]: With dead ends: 613 [2021-12-21 20:54:51,395 INFO L226 Difference]: Without dead ends: 334 [2021-12-21 20:54:51,395 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 20:54:51,397 INFO L933 BasicCegarLoop]: 169 mSDtfsCounter, 2 mSDsluCounter, 334 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 503 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:51,397 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 503 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:51,398 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 334 states. [2021-12-21 20:54:51,424 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 334 to 334. [2021-12-21 20:54:51,431 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 334 states, 308 states have (on average 1.2207792207792207) internal successors, (376), 322 states have internal predecessors, (376), 19 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (22), 10 states have call predecessors, (22), 19 states have call successors, (22) [2021-12-21 20:54:51,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 334 states to 334 states and 417 transitions. [2021-12-21 20:54:51,435 INFO L78 Accepts]: Start accepts. Automaton has 334 states and 417 transitions. Word has length 76 [2021-12-21 20:54:51,436 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:51,436 INFO L470 AbstractCegarLoop]: Abstraction has 334 states and 417 transitions. [2021-12-21 20:54:51,437 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 18.0) internal successors, (72), 4 states have internal predecessors, (72), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 20:54:51,437 INFO L276 IsEmpty]: Start isEmpty. Operand 334 states and 417 transitions. [2021-12-21 20:54:51,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2021-12-21 20:54:51,441 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:51,441 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:51,494 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:51,663 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:51,663 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:51,664 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:51,664 INFO L85 PathProgramCache]: Analyzing trace with hash 766935497, now seen corresponding path program 1 times [2021-12-21 20:54:51,664 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:51,664 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1718225594] [2021-12-21 20:54:51,664 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:51,664 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:51,729 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:51,730 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [572567010] [2021-12-21 20:54:51,730 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:51,730 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:51,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:51,732 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) [2021-12-21 20:54:51,733 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-21 20:54:52,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:52,502 INFO L263 TraceCheckSpWp]: Trace formula consists of 696 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-21 20:54:52,504 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:52,621 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 20:54:52,621 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:54:52,783 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 10 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 20:54:52,783 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:52,784 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1718225594] [2021-12-21 20:54:52,784 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:52,784 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [572567010] [2021-12-21 20:54:52,784 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [572567010] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:54:52,789 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:54:52,789 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2021-12-21 20:54:52,791 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1087068954] [2021-12-21 20:54:52,791 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:54:52,792 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-21 20:54:52,792 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:52,792 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-21 20:54:52,792 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2021-12-21 20:54:52,792 INFO L87 Difference]: Start difference. First operand 334 states and 417 transitions. Second operand has 8 states, 8 states have (on average 9.875) internal successors, (79), 8 states have internal predecessors, (79), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-21 20:54:52,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:52,941 INFO L93 Difference]: Finished difference Result 627 states and 806 transitions. [2021-12-21 20:54:52,942 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-21 20:54:52,943 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 9.875) internal successors, (79), 8 states have internal predecessors, (79), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 78 [2021-12-21 20:54:52,943 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:52,944 INFO L225 Difference]: With dead ends: 627 [2021-12-21 20:54:52,944 INFO L226 Difference]: Without dead ends: 343 [2021-12-21 20:54:52,945 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 148 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=53, Invalid=79, Unknown=0, NotChecked=0, Total=132 [2021-12-21 20:54:52,947 INFO L933 BasicCegarLoop]: 168 mSDtfsCounter, 23 mSDsluCounter, 332 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 500 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:52,948 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [23 Valid, 500 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:52,949 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 343 states. [2021-12-21 20:54:52,955 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 343 to 343. [2021-12-21 20:54:52,956 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 343 states, 316 states have (on average 1.2278481012658229) internal successors, (388), 330 states have internal predecessors, (388), 19 states have call successors, (19), 3 states have call predecessors, (19), 4 states have return successors, (25), 10 states have call predecessors, (25), 19 states have call successors, (25) [2021-12-21 20:54:52,957 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 343 states to 343 states and 432 transitions. [2021-12-21 20:54:52,957 INFO L78 Accepts]: Start accepts. Automaton has 343 states and 432 transitions. Word has length 78 [2021-12-21 20:54:52,957 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:52,957 INFO L470 AbstractCegarLoop]: Abstraction has 343 states and 432 transitions. [2021-12-21 20:54:52,958 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 9.875) internal successors, (79), 8 states have internal predecessors, (79), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-21 20:54:52,958 INFO L276 IsEmpty]: Start isEmpty. Operand 343 states and 432 transitions. [2021-12-21 20:54:52,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2021-12-21 20:54:52,958 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:52,959 INFO L514 BasicCegarLoop]: trace histogram [6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:52,982 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2021-12-21 20:54:53,180 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2021-12-21 20:54:53,180 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:53,181 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:53,181 INFO L85 PathProgramCache]: Analyzing trace with hash -2047753493, now seen corresponding path program 2 times [2021-12-21 20:54:53,181 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:53,181 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1231350519] [2021-12-21 20:54:53,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:53,181 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:53,214 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:53,214 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2044734079] [2021-12-21 20:54:53,214 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-21 20:54:53,214 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:53,214 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:53,215 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) [2021-12-21 20:54:53,217 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-12-21 20:54:53,924 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-21 20:54:53,924 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 20:54:53,929 INFO L263 TraceCheckSpWp]: Trace formula consists of 756 conjuncts, 24 conjunts are in the unsatisfiable core [2021-12-21 20:54:53,931 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:54,096 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 6 proven. 25 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-21 20:54:54,097 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:54:54,346 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 21 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-21 20:54:54,346 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:54,346 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1231350519] [2021-12-21 20:54:54,346 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:54,346 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2044734079] [2021-12-21 20:54:54,347 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2044734079] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:54:54,347 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:54:54,347 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 15 [2021-12-21 20:54:54,347 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [173819863] [2021-12-21 20:54:54,347 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:54:54,347 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2021-12-21 20:54:54,348 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:54,348 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-12-21 20:54:54,348 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=147, Unknown=0, NotChecked=0, Total=210 [2021-12-21 20:54:54,348 INFO L87 Difference]: Start difference. First operand 343 states and 432 transitions. Second operand has 15 states, 15 states have (on average 5.8) internal successors, (87), 15 states have internal predecessors, (87), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-21 20:54:55,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:55,042 INFO L93 Difference]: Finished difference Result 686 states and 892 transitions. [2021-12-21 20:54:55,042 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2021-12-21 20:54:55,043 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 5.8) internal successors, (87), 15 states have internal predecessors, (87), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 82 [2021-12-21 20:54:55,043 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:55,045 INFO L225 Difference]: With dead ends: 686 [2021-12-21 20:54:55,045 INFO L226 Difference]: Without dead ends: 347 [2021-12-21 20:54:55,047 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 174 GetRequests, 147 SyntacticMatches, 2 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=234, Invalid=468, Unknown=0, NotChecked=0, Total=702 [2021-12-21 20:54:55,047 INFO L933 BasicCegarLoop]: 162 mSDtfsCounter, 186 mSDsluCounter, 1289 mSDsCounter, 0 mSdLazyCounter, 241 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 203 SdHoareTripleChecker+Valid, 1451 SdHoareTripleChecker+Invalid, 276 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 241 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:55,048 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [203 Valid, 1451 Invalid, 276 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 241 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-21 20:54:55,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 347 states. [2021-12-21 20:54:55,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 347 to 345. [2021-12-21 20:54:55,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 345 states, 317 states have (on average 1.2334384858044165) internal successors, (391), 332 states have internal predecessors, (391), 19 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (28), 10 states have call predecessors, (28), 19 states have call successors, (28) [2021-12-21 20:54:55,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 345 states to 345 states and 438 transitions. [2021-12-21 20:54:55,058 INFO L78 Accepts]: Start accepts. Automaton has 345 states and 438 transitions. Word has length 82 [2021-12-21 20:54:55,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:55,059 INFO L470 AbstractCegarLoop]: Abstraction has 345 states and 438 transitions. [2021-12-21 20:54:55,059 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 5.8) internal successors, (87), 15 states have internal predecessors, (87), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-21 20:54:55,059 INFO L276 IsEmpty]: Start isEmpty. Operand 345 states and 438 transitions. [2021-12-21 20:54:55,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2021-12-21 20:54:55,060 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:55,060 INFO L514 BasicCegarLoop]: trace histogram [12, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:55,097 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:55,282 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-12-21 20:54:55,282 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:55,282 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:55,282 INFO L85 PathProgramCache]: Analyzing trace with hash -257363413, now seen corresponding path program 3 times [2021-12-21 20:54:55,282 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:55,282 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1956775484] [2021-12-21 20:54:55,283 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:55,283 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:55,342 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:55,342 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1218795582] [2021-12-21 20:54:55,343 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-21 20:54:55,343 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:55,343 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:55,344 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) [2021-12-21 20:54:55,345 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-12-21 20:54:56,069 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2021-12-21 20:54:56,069 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 20:54:56,072 INFO L263 TraceCheckSpWp]: Trace formula consists of 369 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-21 20:54:56,074 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:56,236 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2021-12-21 20:54:56,236 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:54:56,236 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:56,236 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1956775484] [2021-12-21 20:54:56,236 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:56,237 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1218795582] [2021-12-21 20:54:56,237 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1218795582] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:54:56,237 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:54:56,237 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 20:54:56,237 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1496387224] [2021-12-21 20:54:56,237 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:54:56,237 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-21 20:54:56,238 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:56,238 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-21 20:54:56,238 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2021-12-21 20:54:56,238 INFO L87 Difference]: Start difference. First operand 345 states and 438 transitions. Second operand has 6 states, 5 states have (on average 14.0) internal successors, (70), 6 states have internal predecessors, (70), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 20:54:56,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:56,306 INFO L93 Difference]: Finished difference Result 345 states and 438 transitions. [2021-12-21 20:54:56,306 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 20:54:56,306 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 14.0) internal successors, (70), 6 states have internal predecessors, (70), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 88 [2021-12-21 20:54:56,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:56,308 INFO L225 Difference]: With dead ends: 345 [2021-12-21 20:54:56,308 INFO L226 Difference]: Without dead ends: 344 [2021-12-21 20:54:56,309 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 83 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2021-12-21 20:54:56,309 INFO L933 BasicCegarLoop]: 255 mSDtfsCounter, 304 mSDsluCounter, 398 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 318 SdHoareTripleChecker+Valid, 653 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:56,309 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [318 Valid, 653 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:54:56,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 344 states. [2021-12-21 20:54:56,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 344 to 344. [2021-12-21 20:54:56,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 344 states, 317 states have (on average 1.227129337539432) internal successors, (389), 331 states have internal predecessors, (389), 19 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (28), 10 states have call predecessors, (28), 19 states have call successors, (28) [2021-12-21 20:54:56,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 344 states to 344 states and 436 transitions. [2021-12-21 20:54:56,320 INFO L78 Accepts]: Start accepts. Automaton has 344 states and 436 transitions. Word has length 88 [2021-12-21 20:54:56,320 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:56,320 INFO L470 AbstractCegarLoop]: Abstraction has 344 states and 436 transitions. [2021-12-21 20:54:56,321 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 14.0) internal successors, (70), 6 states have internal predecessors, (70), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 20:54:56,321 INFO L276 IsEmpty]: Start isEmpty. Operand 344 states and 436 transitions. [2021-12-21 20:54:56,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 194 [2021-12-21 20:54:56,324 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:56,324 INFO L514 BasicCegarLoop]: trace histogram [12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:56,362 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:56,539 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-12-21 20:54:56,540 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:56,541 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:56,541 INFO L85 PathProgramCache]: Analyzing trace with hash 1528496987, now seen corresponding path program 1 times [2021-12-21 20:54:56,541 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:56,541 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1869759578] [2021-12-21 20:54:56,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:56,541 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:56,679 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:56,679 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [89959043] [2021-12-21 20:54:56,679 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:56,679 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:56,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:56,680 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) [2021-12-21 20:54:56,695 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-21 20:54:58,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:54:58,039 INFO L263 TraceCheckSpWp]: Trace formula consists of 3762 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 20:54:58,044 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:54:58,362 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 0 proven. 159 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2021-12-21 20:54:58,362 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:54:58,713 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 0 proven. 159 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2021-12-21 20:54:58,713 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:54:58,713 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1869759578] [2021-12-21 20:54:58,713 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:54:58,713 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [89959043] [2021-12-21 20:54:58,713 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [89959043] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:54:58,714 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:54:58,714 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 13 [2021-12-21 20:54:58,714 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [312416518] [2021-12-21 20:54:58,714 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:54:58,715 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-21 20:54:58,715 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:54:58,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-21 20:54:58,716 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2021-12-21 20:54:58,716 INFO L87 Difference]: Start difference. First operand 344 states and 436 transitions. Second operand has 14 states, 13 states have (on average 26.53846153846154) internal successors, (345), 14 states have internal predecessors, (345), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:54:58,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:54:58,854 INFO L93 Difference]: Finished difference Result 467 states and 603 transitions. [2021-12-21 20:54:58,855 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-21 20:54:58,855 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 26.53846153846154) internal successors, (345), 14 states have internal predecessors, (345), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 193 [2021-12-21 20:54:58,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:54:58,857 INFO L225 Difference]: With dead ends: 467 [2021-12-21 20:54:58,857 INFO L226 Difference]: Without dead ends: 466 [2021-12-21 20:54:58,857 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 388 GetRequests, 372 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=105, Invalid=201, Unknown=0, NotChecked=0, Total=306 [2021-12-21 20:54:58,857 INFO L933 BasicCegarLoop]: 177 mSDtfsCounter, 381 mSDsluCounter, 1346 mSDsCounter, 0 mSdLazyCounter, 119 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 409 SdHoareTripleChecker+Valid, 1523 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 119 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 20:54:58,857 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [409 Valid, 1523 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 119 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 20:54:58,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 466 states. [2021-12-21 20:54:58,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 466 to 343. [2021-12-21 20:54:58,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 343 states, 317 states have (on average 1.22397476340694) internal successors, (388), 330 states have internal predecessors, (388), 19 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (28), 10 states have call predecessors, (28), 19 states have call successors, (28) [2021-12-21 20:54:58,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 343 states to 343 states and 435 transitions. [2021-12-21 20:54:58,868 INFO L78 Accepts]: Start accepts. Automaton has 343 states and 435 transitions. Word has length 193 [2021-12-21 20:54:58,868 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:54:58,868 INFO L470 AbstractCegarLoop]: Abstraction has 343 states and 435 transitions. [2021-12-21 20:54:58,868 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 26.53846153846154) internal successors, (345), 14 states have internal predecessors, (345), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:54:58,869 INFO L276 IsEmpty]: Start isEmpty. Operand 343 states and 435 transitions. [2021-12-21 20:54:58,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2021-12-21 20:54:58,870 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:54:58,870 INFO L514 BasicCegarLoop]: trace histogram [12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:54:58,896 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-12-21 20:54:59,095 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-12-21 20:54:59,095 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:54:59,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:54:59,096 INFO L85 PathProgramCache]: Analyzing trace with hash 780876539, now seen corresponding path program 1 times [2021-12-21 20:54:59,096 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:54:59,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [673333146] [2021-12-21 20:54:59,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:59,096 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:54:59,226 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:54:59,227 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [672867858] [2021-12-21 20:54:59,227 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:54:59,227 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:54:59,227 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:54:59,228 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) [2021-12-21 20:54:59,229 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-12-21 20:55:00,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:55:00,681 INFO L263 TraceCheckSpWp]: Trace formula consists of 3786 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-21 20:55:00,685 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:00,995 INFO L134 CoverageAnalysis]: Checked inductivity of 258 backedges. 0 proven. 164 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2021-12-21 20:55:00,995 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:55:01,311 INFO L134 CoverageAnalysis]: Checked inductivity of 258 backedges. 0 proven. 164 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2021-12-21 20:55:01,311 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:01,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [673333146] [2021-12-21 20:55:01,311 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:01,311 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [672867858] [2021-12-21 20:55:01,311 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [672867858] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:55:01,311 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:55:01,311 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2021-12-21 20:55:01,311 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1341319643] [2021-12-21 20:55:01,311 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:55:01,312 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-12-21 20:55:01,312 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:01,312 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-12-21 20:55:01,312 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2021-12-21 20:55:01,313 INFO L87 Difference]: Start difference. First operand 343 states and 435 transitions. Second operand has 16 states, 16 states have (on average 22.0) internal successors, (352), 16 states have internal predecessors, (352), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:55:01,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:55:01,478 INFO L93 Difference]: Finished difference Result 752 states and 955 transitions. [2021-12-21 20:55:01,478 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-12-21 20:55:01,478 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 22.0) internal successors, (352), 16 states have internal predecessors, (352), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 198 [2021-12-21 20:55:01,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:55:01,482 INFO L225 Difference]: With dead ends: 752 [2021-12-21 20:55:01,491 INFO L226 Difference]: Without dead ends: 719 [2021-12-21 20:55:01,492 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 400 GetRequests, 380 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=151, Invalid=311, Unknown=0, NotChecked=0, Total=462 [2021-12-21 20:55:01,492 INFO L933 BasicCegarLoop]: 235 mSDtfsCounter, 1190 mSDsluCounter, 1894 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1209 SdHoareTripleChecker+Valid, 2129 SdHoareTripleChecker+Invalid, 164 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 20:55:01,493 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1209 Valid, 2129 Invalid, 164 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 117 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 20:55:01,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 719 states. [2021-12-21 20:55:01,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 719 to 719. [2021-12-21 20:55:01,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 719 states, 681 states have (on average 1.198237885462555) internal successors, (816), 694 states have internal predecessors, (816), 31 states have call successors, (31), 3 states have call predecessors, (31), 5 states have return successors, (52), 22 states have call predecessors, (52), 31 states have call successors, (52) [2021-12-21 20:55:01,531 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 719 states to 719 states and 899 transitions. [2021-12-21 20:55:01,547 INFO L78 Accepts]: Start accepts. Automaton has 719 states and 899 transitions. Word has length 198 [2021-12-21 20:55:01,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:55:01,548 INFO L470 AbstractCegarLoop]: Abstraction has 719 states and 899 transitions. [2021-12-21 20:55:01,548 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 22.0) internal successors, (352), 16 states have internal predecessors, (352), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:55:01,548 INFO L276 IsEmpty]: Start isEmpty. Operand 719 states and 899 transitions. [2021-12-21 20:55:01,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 419 [2021-12-21 20:55:01,553 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:55:01,553 INFO L514 BasicCegarLoop]: trace histogram [12, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:55:01,586 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2021-12-21 20:55:01,771 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-12-21 20:55:01,771 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:55:01,772 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:55:01,772 INFO L85 PathProgramCache]: Analyzing trace with hash 932289851, now seen corresponding path program 2 times [2021-12-21 20:55:01,772 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:55:01,772 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1157999065] [2021-12-21 20:55:01,772 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:01,772 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:55:02,145 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:55:02,145 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1591453525] [2021-12-21 20:55:02,145 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-21 20:55:02,146 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:02,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:55:02,164 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 20:55:02,165 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-12-21 20:55:03,832 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2021-12-21 20:55:03,832 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 20:55:03,838 INFO L263 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-21 20:55:03,871 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:04,393 INFO L134 CoverageAnalysis]: Checked inductivity of 1244 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1244 trivial. 0 not checked. [2021-12-21 20:55:04,393 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:55:04,393 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:04,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1157999065] [2021-12-21 20:55:04,393 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:04,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1591453525] [2021-12-21 20:55:04,393 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1591453525] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:55:04,393 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:55:04,393 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-21 20:55:04,393 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [26058319] [2021-12-21 20:55:04,394 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:55:04,394 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 20:55:04,394 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:04,394 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 20:55:04,394 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 20:55:04,394 INFO L87 Difference]: Start difference. First operand 719 states and 899 transitions. Second operand has 4 states, 3 states have (on average 24.333333333333332) internal successors, (73), 3 states have internal predecessors, (73), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 20:55:04,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:55:04,431 INFO L93 Difference]: Finished difference Result 745 states and 945 transitions. [2021-12-21 20:55:04,432 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 20:55:04,432 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 24.333333333333332) internal successors, (73), 3 states have internal predecessors, (73), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 418 [2021-12-21 20:55:04,432 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:55:04,434 INFO L225 Difference]: With dead ends: 745 [2021-12-21 20:55:04,435 INFO L226 Difference]: Without dead ends: 744 [2021-12-21 20:55:04,435 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 418 GetRequests, 415 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 20:55:04,435 INFO L933 BasicCegarLoop]: 163 mSDtfsCounter, 65 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:55:04,436 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [75 Valid, 364 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:55:04,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 744 states. [2021-12-21 20:55:04,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 744 to 721. [2021-12-21 20:55:04,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 721 states, 683 states have (on average 1.197657393850659) internal successors, (818), 696 states have internal predecessors, (818), 31 states have call successors, (31), 3 states have call predecessors, (31), 5 states have return successors, (52), 22 states have call predecessors, (52), 31 states have call successors, (52) [2021-12-21 20:55:04,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 721 states to 721 states and 901 transitions. [2021-12-21 20:55:04,454 INFO L78 Accepts]: Start accepts. Automaton has 721 states and 901 transitions. Word has length 418 [2021-12-21 20:55:04,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:55:04,455 INFO L470 AbstractCegarLoop]: Abstraction has 721 states and 901 transitions. [2021-12-21 20:55:04,455 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 24.333333333333332) internal successors, (73), 3 states have internal predecessors, (73), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 20:55:04,455 INFO L276 IsEmpty]: Start isEmpty. Operand 721 states and 901 transitions. [2021-12-21 20:55:04,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 420 [2021-12-21 20:55:04,459 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:55:04,460 INFO L514 BasicCegarLoop]: trace histogram [12, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:55:04,504 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-12-21 20:55:04,675 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-12-21 20:55:04,675 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:55:04,676 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:55:04,676 INFO L85 PathProgramCache]: Analyzing trace with hash -1163785260, now seen corresponding path program 1 times [2021-12-21 20:55:04,676 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:55:04,676 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [477788601] [2021-12-21 20:55:04,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:04,677 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:55:05,149 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:55:05,151 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1828571524] [2021-12-21 20:55:05,151 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:05,153 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:05,153 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:55:05,154 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 20:55:05,155 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-12-21 20:55:08,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:55:08,563 INFO L263 TraceCheckSpWp]: Trace formula consists of 9679 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-21 20:55:08,570 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:09,256 INFO L134 CoverageAnalysis]: Checked inductivity of 1244 backedges. 0 proven. 1150 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2021-12-21 20:55:09,257 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:55:09,979 INFO L134 CoverageAnalysis]: Checked inductivity of 1244 backedges. 0 proven. 1150 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2021-12-21 20:55:09,980 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:09,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [477788601] [2021-12-21 20:55:09,980 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:09,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1828571524] [2021-12-21 20:55:09,980 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1828571524] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:55:09,980 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:55:09,981 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 21 [2021-12-21 20:55:09,981 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [627430296] [2021-12-21 20:55:09,981 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:55:09,982 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-21 20:55:09,982 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:09,982 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-21 20:55:09,982 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=120, Invalid=300, Unknown=0, NotChecked=0, Total=420 [2021-12-21 20:55:09,983 INFO L87 Difference]: Start difference. First operand 721 states and 901 transitions. Second operand has 21 states, 21 states have (on average 24.80952380952381) internal successors, (521), 21 states have internal predecessors, (521), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:55:10,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:55:10,193 INFO L93 Difference]: Finished difference Result 1038 states and 1306 transitions. [2021-12-21 20:55:10,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2021-12-21 20:55:10,194 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 24.80952380952381) internal successors, (521), 21 states have internal predecessors, (521), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 419 [2021-12-21 20:55:10,195 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:55:10,198 INFO L225 Difference]: With dead ends: 1038 [2021-12-21 20:55:10,198 INFO L226 Difference]: Without dead ends: 1003 [2021-12-21 20:55:10,200 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 845 GetRequests, 816 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 119 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=273, Invalid=597, Unknown=0, NotChecked=0, Total=870 [2021-12-21 20:55:10,201 INFO L933 BasicCegarLoop]: 244 mSDtfsCounter, 1261 mSDsluCounter, 2167 mSDsCounter, 0 mSdLazyCounter, 167 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1287 SdHoareTripleChecker+Valid, 2411 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 167 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 20:55:10,201 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1287 Valid, 2411 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 167 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 20:55:10,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1003 states. [2021-12-21 20:55:10,234 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1003 to 1003. [2021-12-21 20:55:10,235 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1003 states, 956 states have (on average 1.1914225941422594) internal successors, (1139), 969 states have internal predecessors, (1139), 40 states have call successors, (40), 3 states have call predecessors, (40), 5 states have return successors, (70), 31 states have call predecessors, (70), 40 states have call successors, (70) [2021-12-21 20:55:10,238 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1003 states to 1003 states and 1249 transitions. [2021-12-21 20:55:10,239 INFO L78 Accepts]: Start accepts. Automaton has 1003 states and 1249 transitions. Word has length 419 [2021-12-21 20:55:10,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:55:10,240 INFO L470 AbstractCegarLoop]: Abstraction has 1003 states and 1249 transitions. [2021-12-21 20:55:10,240 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 24.80952380952381) internal successors, (521), 21 states have internal predecessors, (521), 2 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:55:10,240 INFO L276 IsEmpty]: Start isEmpty. Operand 1003 states and 1249 transitions. [2021-12-21 20:55:10,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 585 [2021-12-21 20:55:10,245 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:55:10,246 INFO L514 BasicCegarLoop]: trace histogram [12, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:55:10,290 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2021-12-21 20:55:10,471 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:10,471 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:55:10,472 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:55:10,472 INFO L85 PathProgramCache]: Analyzing trace with hash 465313109, now seen corresponding path program 2 times [2021-12-21 20:55:10,472 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:55:10,472 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1320504543] [2021-12-21 20:55:10,472 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:10,472 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:55:11,044 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:55:11,044 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1102296598] [2021-12-21 20:55:11,044 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-21 20:55:11,044 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:11,045 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:55:11,046 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 20:55:11,048 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2021-12-21 20:55:14,112 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2021-12-21 20:55:14,113 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 20:55:14,121 INFO L263 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-21 20:55:14,130 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:14,810 INFO L134 CoverageAnalysis]: Checked inductivity of 2561 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2561 trivial. 0 not checked. [2021-12-21 20:55:14,810 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:55:14,811 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:14,811 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1320504543] [2021-12-21 20:55:14,811 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:14,811 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1102296598] [2021-12-21 20:55:14,811 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1102296598] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:55:14,811 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:55:14,811 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-21 20:55:14,811 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1003315092] [2021-12-21 20:55:14,811 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:55:14,812 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 20:55:14,812 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:14,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 20:55:14,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 20:55:14,813 INFO L87 Difference]: Start difference. First operand 1003 states and 1249 transitions. Second operand has 4 states, 3 states have (on average 24.666666666666668) internal successors, (74), 3 states have internal predecessors, (74), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 20:55:14,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:55:14,858 INFO L93 Difference]: Finished difference Result 1003 states and 1249 transitions. [2021-12-21 20:55:14,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 20:55:14,859 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 24.666666666666668) internal successors, (74), 3 states have internal predecessors, (74), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 584 [2021-12-21 20:55:14,859 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:55:14,862 INFO L225 Difference]: With dead ends: 1003 [2021-12-21 20:55:14,862 INFO L226 Difference]: Without dead ends: 1002 [2021-12-21 20:55:14,862 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 584 GetRequests, 581 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 20:55:14,863 INFO L933 BasicCegarLoop]: 142 mSDtfsCounter, 100 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 100 SdHoareTripleChecker+Valid, 272 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 20:55:14,863 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [100 Valid, 272 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 20:55:14,864 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1002 states. [2021-12-21 20:55:14,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1002 to 1002. [2021-12-21 20:55:14,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1002 states, 956 states have (on average 1.1903765690376569) internal successors, (1138), 968 states have internal predecessors, (1138), 40 states have call successors, (40), 3 states have call predecessors, (40), 5 states have return successors, (70), 31 states have call predecessors, (70), 40 states have call successors, (70) [2021-12-21 20:55:14,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1002 states to 1002 states and 1248 transitions. [2021-12-21 20:55:14,886 INFO L78 Accepts]: Start accepts. Automaton has 1002 states and 1248 transitions. Word has length 584 [2021-12-21 20:55:14,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:55:14,887 INFO L470 AbstractCegarLoop]: Abstraction has 1002 states and 1248 transitions. [2021-12-21 20:55:14,887 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 24.666666666666668) internal successors, (74), 3 states have internal predecessors, (74), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 20:55:14,887 INFO L276 IsEmpty]: Start isEmpty. Operand 1002 states and 1248 transitions. [2021-12-21 20:55:14,891 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 596 [2021-12-21 20:55:14,892 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:55:14,892 INFO L514 BasicCegarLoop]: trace histogram [12, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:55:14,923 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2021-12-21 20:55:15,123 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2021-12-21 20:55:15,123 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:55:15,124 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:55:15,124 INFO L85 PathProgramCache]: Analyzing trace with hash -1635273478, now seen corresponding path program 1 times [2021-12-21 20:55:15,124 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:55:15,124 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [893505587] [2021-12-21 20:55:15,124 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:15,124 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:55:15,771 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:55:15,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [886408867] [2021-12-21 20:55:15,772 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:15,772 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:15,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:55:15,773 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 20:55:15,798 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2021-12-21 20:55:21,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:55:21,517 INFO L263 TraceCheckSpWp]: Trace formula consists of 14133 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-21 20:55:21,529 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:22,151 INFO L134 CoverageAnalysis]: Checked inductivity of 2563 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2561 trivial. 0 not checked. [2021-12-21 20:55:22,151 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:55:22,686 INFO L134 CoverageAnalysis]: Checked inductivity of 2563 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2561 trivial. 0 not checked. [2021-12-21 20:55:22,687 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:22,687 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [893505587] [2021-12-21 20:55:22,687 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:22,687 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [886408867] [2021-12-21 20:55:22,687 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [886408867] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:55:22,687 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:55:22,687 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 9 [2021-12-21 20:55:22,688 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1873101990] [2021-12-21 20:55:22,688 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:55:22,688 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-21 20:55:22,688 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:22,689 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-21 20:55:22,689 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2021-12-21 20:55:22,689 INFO L87 Difference]: Start difference. First operand 1002 states and 1248 transitions. Second operand has 10 states, 9 states have (on average 18.444444444444443) internal successors, (166), 10 states have internal predecessors, (166), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2021-12-21 20:55:22,913 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:55:22,913 INFO L93 Difference]: Finished difference Result 1094 states and 1399 transitions. [2021-12-21 20:55:22,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-12-21 20:55:22,914 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 18.444444444444443) internal successors, (166), 10 states have internal predecessors, (166), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 595 [2021-12-21 20:55:22,914 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:55:22,917 INFO L225 Difference]: With dead ends: 1094 [2021-12-21 20:55:22,918 INFO L226 Difference]: Without dead ends: 1093 [2021-12-21 20:55:22,918 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1195 GetRequests, 1180 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=99, Invalid=173, Unknown=0, NotChecked=0, Total=272 [2021-12-21 20:55:22,918 INFO L933 BasicCegarLoop]: 153 mSDtfsCounter, 367 mSDsluCounter, 286 mSDsCounter, 0 mSdLazyCounter, 278 mSolverCounterSat, 106 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 377 SdHoareTripleChecker+Valid, 439 SdHoareTripleChecker+Invalid, 384 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 106 IncrementalHoareTripleChecker+Valid, 278 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-21 20:55:22,919 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [377 Valid, 439 Invalid, 384 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [106 Valid, 278 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-21 20:55:22,919 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1093 states. [2021-12-21 20:55:22,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1093 to 1092. [2021-12-21 20:55:22,945 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1092 states, 1013 states have (on average 1.2092793682132281) internal successors, (1225), 1055 states have internal predecessors, (1225), 70 states have call successors, (70), 6 states have call predecessors, (70), 8 states have return successors, (100), 34 states have call predecessors, (100), 70 states have call successors, (100) [2021-12-21 20:55:22,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1092 states to 1092 states and 1395 transitions. [2021-12-21 20:55:22,947 INFO L78 Accepts]: Start accepts. Automaton has 1092 states and 1395 transitions. Word has length 595 [2021-12-21 20:55:22,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:55:22,948 INFO L470 AbstractCegarLoop]: Abstraction has 1092 states and 1395 transitions. [2021-12-21 20:55:22,948 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 18.444444444444443) internal successors, (166), 10 states have internal predecessors, (166), 4 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2021-12-21 20:55:22,948 INFO L276 IsEmpty]: Start isEmpty. Operand 1092 states and 1395 transitions. [2021-12-21 20:55:22,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 632 [2021-12-21 20:55:22,953 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:55:22,953 INFO L514 BasicCegarLoop]: trace histogram [12, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:55:23,012 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2021-12-21 20:55:23,167 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2021-12-21 20:55:23,167 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:55:23,168 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:55:23,168 INFO L85 PathProgramCache]: Analyzing trace with hash -1399067366, now seen corresponding path program 2 times [2021-12-21 20:55:23,168 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:55:23,168 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [985473818] [2021-12-21 20:55:23,168 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:23,168 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:55:23,756 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:55:23,756 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [921533047] [2021-12-21 20:55:23,757 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-21 20:55:23,757 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:23,757 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:55:23,758 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 20:55:23,759 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2021-12-21 20:55:30,285 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-21 20:55:30,285 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 20:55:30,381 INFO L263 TraceCheckSpWp]: Trace formula consists of 14241 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-21 20:55:30,390 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:31,255 INFO L134 CoverageAnalysis]: Checked inductivity of 2641 backedges. 0 proven. 80 refuted. 0 times theorem prover too weak. 2561 trivial. 0 not checked. [2021-12-21 20:55:31,255 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:55:32,216 INFO L134 CoverageAnalysis]: Checked inductivity of 2641 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 2585 trivial. 0 not checked. [2021-12-21 20:55:32,217 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:32,217 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [985473818] [2021-12-21 20:55:32,217 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:32,217 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [921533047] [2021-12-21 20:55:32,217 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [921533047] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:55:32,217 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:55:32,217 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 21 [2021-12-21 20:55:32,217 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [546806387] [2021-12-21 20:55:32,217 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:55:32,218 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2021-12-21 20:55:32,218 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:32,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2021-12-21 20:55:32,218 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=331, Unknown=0, NotChecked=0, Total=462 [2021-12-21 20:55:32,218 INFO L87 Difference]: Start difference. First operand 1092 states and 1395 transitions. Second operand has 22 states, 21 states have (on average 10.333333333333334) internal successors, (217), 22 states have internal predecessors, (217), 10 states have call successors, (12), 6 states have call predecessors, (12), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2021-12-21 20:55:32,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:55:32,982 INFO L93 Difference]: Finished difference Result 1274 states and 1696 transitions. [2021-12-21 20:55:32,983 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2021-12-21 20:55:32,983 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 10.333333333333334) internal successors, (217), 22 states have internal predecessors, (217), 10 states have call successors, (12), 6 states have call predecessors, (12), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) Word has length 631 [2021-12-21 20:55:32,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:55:32,987 INFO L225 Difference]: With dead ends: 1274 [2021-12-21 20:55:32,987 INFO L226 Difference]: Without dead ends: 1273 [2021-12-21 20:55:32,988 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 1279 GetRequests, 1240 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 289 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=549, Invalid=1091, Unknown=0, NotChecked=0, Total=1640 [2021-12-21 20:55:32,989 INFO L933 BasicCegarLoop]: 153 mSDtfsCounter, 1347 mSDsluCounter, 1201 mSDsCounter, 0 mSdLazyCounter, 904 mSolverCounterSat, 534 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1357 SdHoareTripleChecker+Valid, 1354 SdHoareTripleChecker+Invalid, 1438 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 534 IncrementalHoareTripleChecker+Valid, 904 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-21 20:55:32,989 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1357 Valid, 1354 Invalid, 1438 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [534 Valid, 904 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-21 20:55:32,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1273 states. [2021-12-21 20:55:33,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1273 to 1272. [2021-12-21 20:55:33,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1272 states, 1127 states have (on average 1.241348713398403) internal successors, (1399), 1229 states have internal predecessors, (1399), 130 states have call successors, (130), 12 states have call predecessors, (130), 14 states have return successors, (160), 40 states have call predecessors, (160), 130 states have call successors, (160) [2021-12-21 20:55:33,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1272 states to 1272 states and 1689 transitions. [2021-12-21 20:55:33,027 INFO L78 Accepts]: Start accepts. Automaton has 1272 states and 1689 transitions. Word has length 631 [2021-12-21 20:55:33,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:55:33,028 INFO L470 AbstractCegarLoop]: Abstraction has 1272 states and 1689 transitions. [2021-12-21 20:55:33,028 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 10.333333333333334) internal successors, (217), 22 states have internal predecessors, (217), 10 states have call successors, (12), 6 states have call predecessors, (12), 6 states have return successors, (12), 10 states have call predecessors, (12), 10 states have call successors, (12) [2021-12-21 20:55:33,028 INFO L276 IsEmpty]: Start isEmpty. Operand 1272 states and 1689 transitions. [2021-12-21 20:55:33,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 704 [2021-12-21 20:55:33,034 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:55:33,035 INFO L514 BasicCegarLoop]: trace histogram [12, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:55:33,105 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2021-12-21 20:55:33,251 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2021-12-21 20:55:33,252 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:55:33,252 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:55:33,252 INFO L85 PathProgramCache]: Analyzing trace with hash 34057562, now seen corresponding path program 3 times [2021-12-21 20:55:33,252 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:55:33,252 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [187465157] [2021-12-21 20:55:33,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:33,252 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:55:33,887 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:55:33,887 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1030227294] [2021-12-21 20:55:33,887 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-21 20:55:33,888 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:33,888 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:55:33,888 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 20:55:33,891 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2021-12-21 20:55:39,291 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2021-12-21 20:55:39,291 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 20:55:39,309 INFO L263 TraceCheckSpWp]: Trace formula consists of 1559 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-21 20:55:39,319 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:39,915 INFO L134 CoverageAnalysis]: Checked inductivity of 3121 backedges. 101 proven. 0 refuted. 0 times theorem prover too weak. 3020 trivial. 0 not checked. [2021-12-21 20:55:39,915 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 20:55:39,916 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:39,916 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [187465157] [2021-12-21 20:55:39,916 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:39,916 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1030227294] [2021-12-21 20:55:39,916 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1030227294] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 20:55:39,916 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 20:55:39,916 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-21 20:55:39,917 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1130922237] [2021-12-21 20:55:39,917 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 20:55:39,918 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 20:55:39,918 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:39,919 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 20:55:39,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-12-21 20:55:39,919 INFO L87 Difference]: Start difference. First operand 1272 states and 1689 transitions. Second operand has 5 states, 4 states have (on average 22.75) internal successors, (91), 5 states have internal predecessors, (91), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:55:40,035 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 20:55:40,036 INFO L93 Difference]: Finished difference Result 1589 states and 2176 transitions. [2021-12-21 20:55:40,036 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 20:55:40,036 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 22.75) internal successors, (91), 5 states have internal predecessors, (91), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 703 [2021-12-21 20:55:40,037 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 20:55:40,042 INFO L225 Difference]: With dead ends: 1589 [2021-12-21 20:55:40,042 INFO L226 Difference]: Without dead ends: 1588 [2021-12-21 20:55:40,043 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 706 GetRequests, 701 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2021-12-21 20:55:40,044 INFO L933 BasicCegarLoop]: 144 mSDtfsCounter, 146 mSDsluCounter, 213 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 147 SdHoareTripleChecker+Valid, 357 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 20:55:40,044 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [147 Valid, 357 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 20:55:40,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1588 states. [2021-12-21 20:55:40,234 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1588 to 1515. [2021-12-21 20:55:40,236 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1515 states, 1298 states have (on average 1.2788906009244991) internal successors, (1660), 1454 states have internal predecessors, (1660), 193 states have call successors, (193), 21 states have call predecessors, (193), 23 states have return successors, (223), 49 states have call predecessors, (223), 193 states have call successors, (223) [2021-12-21 20:55:40,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1515 states to 1515 states and 2076 transitions. [2021-12-21 20:55:40,255 INFO L78 Accepts]: Start accepts. Automaton has 1515 states and 2076 transitions. Word has length 703 [2021-12-21 20:55:40,256 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 20:55:40,256 INFO L470 AbstractCegarLoop]: Abstraction has 1515 states and 2076 transitions. [2021-12-21 20:55:40,256 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 22.75) internal successors, (91), 5 states have internal predecessors, (91), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 20:55:40,256 INFO L276 IsEmpty]: Start isEmpty. Operand 1515 states and 2076 transitions. [2021-12-21 20:55:40,263 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 705 [2021-12-21 20:55:40,263 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 20:55:40,263 INFO L514 BasicCegarLoop]: trace histogram [12, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 20:55:40,359 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2021-12-21 20:55:40,477 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:40,477 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2021-12-21 20:55:40,477 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 20:55:40,477 INFO L85 PathProgramCache]: Analyzing trace with hash 2099048977, now seen corresponding path program 1 times [2021-12-21 20:55:40,477 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 20:55:40,477 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [12289262] [2021-12-21 20:55:40,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:40,478 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 20:55:40,997 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 20:55:40,998 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [714172517] [2021-12-21 20:55:40,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 20:55:40,998 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 20:55:40,998 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 20:55:40,999 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 20:55:41,001 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2021-12-21 20:55:48,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 20:55:48,646 INFO L263 TraceCheckSpWp]: Trace formula consists of 14459 conjuncts, 23 conjunts are in the unsatisfiable core [2021-12-21 20:55:48,658 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 20:55:49,590 INFO L134 CoverageAnalysis]: Checked inductivity of 3112 backedges. 0 proven. 551 refuted. 0 times theorem prover too weak. 2561 trivial. 0 not checked. [2021-12-21 20:55:49,591 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 20:55:50,513 INFO L134 CoverageAnalysis]: Checked inductivity of 3112 backedges. 0 proven. 371 refuted. 0 times theorem prover too weak. 2741 trivial. 0 not checked. [2021-12-21 20:55:50,513 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 20:55:50,514 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [12289262] [2021-12-21 20:55:50,514 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 20:55:50,514 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [714172517] [2021-12-21 20:55:50,514 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [714172517] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 20:55:50,514 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 20:55:50,514 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 23] total 45 [2021-12-21 20:55:50,514 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [352952051] [2021-12-21 20:55:50,515 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 20:55:50,515 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2021-12-21 20:55:50,516 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 20:55:50,516 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2021-12-21 20:55:50,517 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=551, Invalid=1519, Unknown=0, NotChecked=0, Total=2070 [2021-12-21 20:55:50,517 INFO L87 Difference]: Start difference. First operand 1515 states and 2076 transitions. Second operand has 46 states, 45 states have (on average 7.133333333333334) internal successors, (321), 46 states have internal predecessors, (321), 22 states have call successors, (24), 12 states have call predecessors, (24), 12 states have return successors, (24), 22 states have call predecessors, (24), 22 states have call successors, (24)