./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/uthash-2.0.2/uthash_SAX_test6-1.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version c3fed411 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_SAX_test6-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 ff5be3465740cb655882704e7eef418c95d0bbd56a2060e741c7d3e996e58af7 --- Real Ultimate output --- This is Ultimate 0.2.2-tmp.no-commuhash-c3fed41 [2021-12-19 16:26:45,000 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-19 16:26:45,001 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-19 16:26:45,022 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-19 16:26:45,023 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-19 16:26:45,024 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-19 16:26:45,024 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-19 16:26:45,026 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-19 16:26:45,027 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-19 16:26:45,027 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-19 16:26:45,028 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-19 16:26:45,029 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-19 16:26:45,029 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-19 16:26:45,030 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-19 16:26:45,030 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-19 16:26:45,031 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-19 16:26:45,032 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-19 16:26:45,032 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-19 16:26:45,034 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-19 16:26:45,035 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-19 16:26:45,036 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-19 16:26:45,043 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-19 16:26:45,047 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-19 16:26:45,048 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-19 16:26:45,052 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-19 16:26:45,052 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-19 16:26:45,052 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-19 16:26:45,053 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-19 16:26:45,053 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-19 16:26:45,054 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-19 16:26:45,054 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-19 16:26:45,055 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-19 16:26:45,055 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-19 16:26:45,056 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-19 16:26:45,056 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-19 16:26:45,056 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-19 16:26:45,057 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-19 16:26:45,057 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-19 16:26:45,057 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-19 16:26:45,058 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-19 16:26:45,058 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-19 16:26:45,071 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2021-12-19 16:26:45,093 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-19 16:26:45,096 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-19 16:26:45,097 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-19 16:26:45,097 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-19 16:26:45,098 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-19 16:26:45,098 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-19 16:26:45,099 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-19 16:26:45,099 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-19 16:26:45,099 INFO L138 SettingsManager]: * Use SBE=true [2021-12-19 16:26:45,099 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-19 16:26:45,100 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-19 16:26:45,100 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-19 16:26:45,100 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-19 16:26:45,100 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-19 16:26:45,100 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-19 16:26:45,100 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-19 16:26:45,101 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-19 16:26:45,101 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-19 16:26:45,101 INFO L138 SettingsManager]: * Check absence of signed integer overflows=true [2021-12-19 16:26:45,101 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-19 16:26:45,101 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-19 16:26:45,101 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-19 16:26:45,101 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-19 16:26:45,102 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-19 16:26:45,102 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-19 16:26:45,102 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-19 16:26:45,102 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-19 16:26:45,102 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-19 16:26:45,102 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-19 16:26:45,102 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-19 16:26:45,103 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-19 16:26:45,103 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-19 16:26:45,103 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-19 16:26:45,103 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-19 16:26:45,103 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 -> ff5be3465740cb655882704e7eef418c95d0bbd56a2060e741c7d3e996e58af7 [2021-12-19 16:26:45,319 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-19 16:26:45,345 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-19 16:26:45,347 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-19 16:26:45,348 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-19 16:26:45,348 INFO L275 PluginConnector]: CDTParser initialized [2021-12-19 16:26:45,349 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/uthash-2.0.2/uthash_SAX_test6-1.i [2021-12-19 16:26:45,397 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4923bc656/044f0f5f157c490f87c4ceb6b42c54ea/FLAG5333978fa [2021-12-19 16:26:45,860 INFO L306 CDTParser]: Found 1 translation units. [2021-12-19 16:26:45,861 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/uthash-2.0.2/uthash_SAX_test6-1.i [2021-12-19 16:26:45,874 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4923bc656/044f0f5f157c490f87c4ceb6b42c54ea/FLAG5333978fa [2021-12-19 16:26:45,890 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4923bc656/044f0f5f157c490f87c4ceb6b42c54ea [2021-12-19 16:26:45,892 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-19 16:26:45,893 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-19 16:26:45,895 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-19 16:26:45,895 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-19 16:26:45,897 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-19 16:26:45,898 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 04:26:45" (1/1) ... [2021-12-19 16:26:45,899 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@fb4dff6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:45, skipping insertion in model container [2021-12-19 16:26:45,900 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 04:26:45" (1/1) ... [2021-12-19 16:26:45,905 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-19 16:26:45,944 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-19 16:26:46,222 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_SAX_test6-1.i[44118,44131] [2021-12-19 16:26:46,232 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_SAX_test6-1.i[44660,44673] [2021-12-19 16:26:46,299 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_SAX_test6-1.i[56247,56260] [2021-12-19 16:26:46,300 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_SAX_test6-1.i[56368,56381] [2021-12-19 16:26:46,308 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-19 16:26:46,314 INFO L203 MainTranslator]: Completed pre-run [2021-12-19 16:26:46,330 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_SAX_test6-1.i[44118,44131] [2021-12-19 16:26:46,333 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_SAX_test6-1.i[44660,44673] [2021-12-19 16:26:46,404 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_SAX_test6-1.i[56247,56260] [2021-12-19 16:26:46,404 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_SAX_test6-1.i[56368,56381] [2021-12-19 16:26:46,410 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-19 16:26:46,451 INFO L208 MainTranslator]: Completed translation [2021-12-19 16:26:46,451 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46 WrapperNode [2021-12-19 16:26:46,451 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-19 16:26:46,452 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-19 16:26:46,452 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-19 16:26:46,452 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-19 16:26:46,457 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,487 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,541 INFO L137 Inliner]: procedures = 282, calls = 294, calls flagged for inlining = 6, calls inlined = 6, statements flattened = 1050 [2021-12-19 16:26:46,542 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-19 16:26:46,543 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-19 16:26:46,543 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-19 16:26:46,543 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-19 16:26:46,549 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,549 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,556 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,557 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,591 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,612 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,615 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,621 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-19 16:26:46,622 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-19 16:26:46,622 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-19 16:26:46,623 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-19 16:26:46,623 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (1/1) ... [2021-12-19 16:26:46,628 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-19 16:26:46,645 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:46,672 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-19 16:26:46,690 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-19 16:26:46,711 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-19 16:26:46,712 INFO L130 BoogieDeclarations]: Found specification of procedure memcmp [2021-12-19 16:26:46,712 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-19 16:26:46,712 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-19 16:26:46,712 INFO L130 BoogieDeclarations]: Found specification of procedure alt_bzero [2021-12-19 16:26:46,712 INFO L138 BoogieDeclarations]: Found implementation of procedure alt_bzero [2021-12-19 16:26:46,712 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-12-19 16:26:46,712 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-19 16:26:46,712 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-19 16:26:46,713 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-12-19 16:26:46,713 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-19 16:26:46,713 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-19 16:26:46,713 INFO L130 BoogieDeclarations]: Found specification of procedure alt_malloc [2021-12-19 16:26:46,713 INFO L138 BoogieDeclarations]: Found implementation of procedure alt_malloc [2021-12-19 16:26:46,713 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-19 16:26:46,713 INFO L130 BoogieDeclarations]: Found specification of procedure alt_free [2021-12-19 16:26:46,713 INFO L138 BoogieDeclarations]: Found implementation of procedure alt_free [2021-12-19 16:26:46,714 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-19 16:26:46,714 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-19 16:26:46,714 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-19 16:26:46,924 INFO L236 CfgBuilder]: Building ICFG [2021-12-19 16:26:46,926 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-19 16:26:47,635 INFO L277 CfgBuilder]: Performing block encoding [2021-12-19 16:26:47,641 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-19 16:26:47,641 INFO L301 CfgBuilder]: Removed 63 assume(true) statements. [2021-12-19 16:26:47,643 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 04:26:47 BoogieIcfgContainer [2021-12-19 16:26:47,643 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-19 16:26:47,644 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-19 16:26:47,644 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-19 16:26:47,647 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-19 16:26:47,647 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 19.12 04:26:45" (1/3) ... [2021-12-19 16:26:47,648 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c1d07b8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.12 04:26:47, skipping insertion in model container [2021-12-19 16:26:47,648 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 04:26:46" (2/3) ... [2021-12-19 16:26:47,648 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c1d07b8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 19.12 04:26:47, skipping insertion in model container [2021-12-19 16:26:47,648 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 04:26:47" (3/3) ... [2021-12-19 16:26:47,649 INFO L111 eAbstractionObserver]: Analyzing ICFG uthash_SAX_test6-1.i [2021-12-19 16:26:47,654 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-19 16:26:47,655 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 14 error locations. [2021-12-19 16:26:47,698 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-19 16:26:47,703 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-19 16:26:47,703 INFO L340 AbstractCegarLoop]: Starting to check reachability of 14 error locations. [2021-12-19 16:26:47,721 INFO L276 IsEmpty]: Start isEmpty. Operand has 245 states, 213 states have (on average 1.6525821596244132) internal successors, (352), 227 states have internal predecessors, (352), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2021-12-19 16:26:47,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2021-12-19 16:26:47,725 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:47,725 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 16:26:47,726 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:47,729 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:47,729 INFO L85 PathProgramCache]: Analyzing trace with hash 1831503788, now seen corresponding path program 1 times [2021-12-19 16:26:47,736 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:47,736 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [742571739] [2021-12-19 16:26:47,737 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:47,738 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:47,830 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:47,885 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-19 16:26:47,885 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:47,886 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [742571739] [2021-12-19 16:26:47,887 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [742571739] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:47,887 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:47,887 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-19 16:26:47,888 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1863087203] [2021-12-19 16:26:47,889 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:47,892 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-19 16:26:47,893 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:47,916 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-19 16:26:47,916 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-19 16:26:47,918 INFO L87 Difference]: Start difference. First operand has 245 states, 213 states have (on average 1.6525821596244132) internal successors, (352), 227 states have internal predecessors, (352), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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-19 16:26:47,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:47,955 INFO L93 Difference]: Finished difference Result 485 states and 764 transitions. [2021-12-19 16:26:47,956 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-19 16:26:47,957 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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 8 [2021-12-19 16:26:47,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:47,964 INFO L225 Difference]: With dead ends: 485 [2021-12-19 16:26:47,964 INFO L226 Difference]: Without dead ends: 233 [2021-12-19 16:26:47,968 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-19 16:26:47,970 INFO L933 BasicCegarLoop]: 305 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 305 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:47,971 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 305 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-19 16:26:47,988 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2021-12-19 16:26:48,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 233. [2021-12-19 16:26:48,027 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 205 states have (on average 1.3317073170731708) internal successors, (273), 219 states have internal predecessors, (273), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-12-19 16:26:48,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 293 transitions. [2021-12-19 16:26:48,032 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 293 transitions. Word has length 8 [2021-12-19 16:26:48,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:48,032 INFO L470 AbstractCegarLoop]: Abstraction has 233 states and 293 transitions. [2021-12-19 16:26:48,032 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 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-19 16:26:48,032 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 293 transitions. [2021-12-19 16:26:48,033 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2021-12-19 16:26:48,033 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:48,033 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 16:26:48,034 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-12-19 16:26:48,034 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:48,035 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:48,035 INFO L85 PathProgramCache]: Analyzing trace with hash 1831505710, now seen corresponding path program 1 times [2021-12-19 16:26:48,035 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:48,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [275382179] [2021-12-19 16:26:48,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:48,036 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:48,056 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:48,056 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1213472938] [2021-12-19 16:26:48,056 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:48,059 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:48,060 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:48,061 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-19 16:26:48,062 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-19 16:26:48,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:48,179 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-19 16:26:48,183 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:48,220 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-19 16:26:48,225 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-12-19 16:26:48,251 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-19 16:26:48,252 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-12-19 16:26:48,287 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-19 16:26:48,289 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2021-12-19 16:26:48,298 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-19 16:26:48,298 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:48,298 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:48,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [275382179] [2021-12-19 16:26:48,299 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:48,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1213472938] [2021-12-19 16:26:48,299 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1213472938] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:48,299 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:48,299 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-19 16:26:48,300 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [469215200] [2021-12-19 16:26:48,300 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:48,300 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-19 16:26:48,301 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:48,301 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-19 16:26:48,301 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-19 16:26:48,301 INFO L87 Difference]: Start difference. First operand 233 states and 293 transitions. Second operand has 6 states, 5 states have (on average 1.6) internal successors, (8), 6 states have internal predecessors, (8), 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-19 16:26:48,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:48,841 INFO L93 Difference]: Finished difference Result 357 states and 457 transitions. [2021-12-19 16:26:48,842 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-19 16:26:48,842 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 1.6) internal successors, (8), 6 states have internal predecessors, (8), 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 8 [2021-12-19 16:26:48,842 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:48,845 INFO L225 Difference]: With dead ends: 357 [2021-12-19 16:26:48,845 INFO L226 Difference]: Without dead ends: 355 [2021-12-19 16:26:48,845 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2021-12-19 16:26:48,846 INFO L933 BasicCegarLoop]: 257 mSDtfsCounter, 242 mSDsluCounter, 882 mSDsCounter, 0 mSdLazyCounter, 382 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 242 SdHoareTripleChecker+Valid, 1139 SdHoareTripleChecker+Invalid, 400 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 382 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:48,846 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [242 Valid, 1139 Invalid, 400 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 382 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-19 16:26:48,847 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 355 states. [2021-12-19 16:26:48,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 355 to 240. [2021-12-19 16:26:48,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 240 states, 212 states have (on average 1.3254716981132075) internal successors, (281), 226 states have internal predecessors, (281), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-12-19 16:26:48,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 240 states to 240 states and 301 transitions. [2021-12-19 16:26:48,858 INFO L78 Accepts]: Start accepts. Automaton has 240 states and 301 transitions. Word has length 8 [2021-12-19 16:26:48,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:48,858 INFO L470 AbstractCegarLoop]: Abstraction has 240 states and 301 transitions. [2021-12-19 16:26:48,858 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 1.6) internal successors, (8), 6 states have internal predecessors, (8), 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-19 16:26:48,858 INFO L276 IsEmpty]: Start isEmpty. Operand 240 states and 301 transitions. [2021-12-19 16:26:48,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-12-19 16:26:48,859 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:48,859 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] [2021-12-19 16:26:48,882 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-19 16:26:49,079 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-19 16:26:49,080 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:49,080 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:49,081 INFO L85 PathProgramCache]: Analyzing trace with hash 1327424248, now seen corresponding path program 1 times [2021-12-19 16:26:49,081 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:49,081 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [256497229] [2021-12-19 16:26:49,081 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:49,081 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:49,106 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:49,106 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [523122510] [2021-12-19 16:26:49,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:49,107 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:49,107 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:49,108 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-19 16:26:49,109 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-19 16:26:49,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:49,254 INFO L263 TraceCheckSpWp]: Trace formula consists of 256 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-19 16:26:49,257 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:49,314 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-19 16:26:49,315 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:49,315 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:49,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [256497229] [2021-12-19 16:26:49,315 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:49,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [523122510] [2021-12-19 16:26:49,315 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [523122510] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:49,315 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:49,316 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-19 16:26:49,316 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [765462662] [2021-12-19 16:26:49,316 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:49,316 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-19 16:26:49,316 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:49,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-19 16:26:49,317 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-19 16:26:49,317 INFO L87 Difference]: Start difference. First operand 240 states and 301 transitions. Second operand has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:49,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:49,359 INFO L93 Difference]: Finished difference Result 492 states and 623 transitions. [2021-12-19 16:26:49,360 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-19 16:26:49,360 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 45 [2021-12-19 16:26:49,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:49,361 INFO L225 Difference]: With dead ends: 492 [2021-12-19 16:26:49,361 INFO L226 Difference]: Without dead ends: 261 [2021-12-19 16:26:49,362 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 43 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-19 16:26:49,380 INFO L933 BasicCegarLoop]: 273 mSDtfsCounter, 9 mSDsluCounter, 258 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 531 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-19 16:26:49,380 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 531 Invalid, 72 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-19 16:26:49,381 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 261 states. [2021-12-19 16:26:49,387 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 261 to 260. [2021-12-19 16:26:49,387 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 232 states have (on average 1.2974137931034482) internal successors, (301), 246 states have internal predecessors, (301), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-12-19 16:26:49,388 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 321 transitions. [2021-12-19 16:26:49,389 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 321 transitions. Word has length 45 [2021-12-19 16:26:49,389 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:49,389 INFO L470 AbstractCegarLoop]: Abstraction has 260 states and 321 transitions. [2021-12-19 16:26:49,389 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:49,389 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 321 transitions. [2021-12-19 16:26:49,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-12-19 16:26:49,390 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:49,390 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] [2021-12-19 16:26:49,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-19 16:26:49,607 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-19 16:26:49,608 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:49,608 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:49,608 INFO L85 PathProgramCache]: Analyzing trace with hash 485811060, now seen corresponding path program 1 times [2021-12-19 16:26:49,608 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:49,608 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [60663401] [2021-12-19 16:26:49,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:49,608 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:49,625 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:49,630 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2000051575] [2021-12-19 16:26:49,630 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:49,630 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:49,630 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:49,631 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-19 16:26:49,632 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-19 16:26:49,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:49,789 INFO L263 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-19 16:26:49,792 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:49,860 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-19 16:26:49,861 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:49,861 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:49,862 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [60663401] [2021-12-19 16:26:49,862 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:49,862 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2000051575] [2021-12-19 16:26:49,862 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2000051575] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:49,862 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:49,862 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-19 16:26:49,863 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1056342257] [2021-12-19 16:26:49,863 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:49,863 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-19 16:26:49,866 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:49,866 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-19 16:26:49,866 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-19 16:26:49,867 INFO L87 Difference]: Start difference. First operand 260 states and 321 transitions. Second operand has 4 states, 4 states have (on average 11.0) internal successors, (44), 4 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:49,922 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:49,922 INFO L93 Difference]: Finished difference Result 596 states and 746 transitions. [2021-12-19 16:26:49,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-19 16:26:49,923 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 11.0) internal successors, (44), 4 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 45 [2021-12-19 16:26:49,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:49,928 INFO L225 Difference]: With dead ends: 596 [2021-12-19 16:26:49,928 INFO L226 Difference]: Without dead ends: 345 [2021-12-19 16:26:49,930 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 42 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-19 16:26:49,933 INFO L933 BasicCegarLoop]: 401 mSDtfsCounter, 232 mSDsluCounter, 565 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 241 SdHoareTripleChecker+Valid, 966 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-19 16:26:49,934 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [241 Valid, 966 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-19 16:26:49,934 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 345 states. [2021-12-19 16:26:49,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 345 to 246. [2021-12-19 16:26:49,940 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 246 states, 218 states have (on average 1.2844036697247707) internal successors, (280), 232 states have internal predecessors, (280), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-12-19 16:26:49,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 246 states to 246 states and 300 transitions. [2021-12-19 16:26:49,942 INFO L78 Accepts]: Start accepts. Automaton has 246 states and 300 transitions. Word has length 45 [2021-12-19 16:26:49,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:49,942 INFO L470 AbstractCegarLoop]: Abstraction has 246 states and 300 transitions. [2021-12-19 16:26:49,942 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 11.0) internal successors, (44), 4 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:49,942 INFO L276 IsEmpty]: Start isEmpty. Operand 246 states and 300 transitions. [2021-12-19 16:26:49,943 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-12-19 16:26:49,943 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:49,943 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] [2021-12-19 16:26:49,963 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-19 16:26:50,160 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-19 16:26:50,161 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:50,161 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:50,161 INFO L85 PathProgramCache]: Analyzing trace with hash 1565710722, now seen corresponding path program 1 times [2021-12-19 16:26:50,162 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:50,162 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [392119742] [2021-12-19 16:26:50,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:50,162 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:50,178 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:50,178 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1964795120] [2021-12-19 16:26:50,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:50,179 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:50,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:50,179 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-19 16:26:50,180 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-19 16:26:50,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:50,317 INFO L263 TraceCheckSpWp]: Trace formula consists of 246 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-19 16:26:50,325 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:50,419 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-19 16:26:50,420 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:50,420 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:50,420 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [392119742] [2021-12-19 16:26:50,420 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:50,420 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1964795120] [2021-12-19 16:26:50,420 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1964795120] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:50,420 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:50,421 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-19 16:26:50,421 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [161105370] [2021-12-19 16:26:50,421 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:50,421 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-19 16:26:50,421 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:50,422 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-19 16:26:50,422 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-19 16:26:50,422 INFO L87 Difference]: Start difference. First operand 246 states and 300 transitions. Second operand has 4 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:50,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:50,451 INFO L93 Difference]: Finished difference Result 427 states and 522 transitions. [2021-12-19 16:26:50,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-19 16:26:50,451 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 45 [2021-12-19 16:26:50,452 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:50,454 INFO L225 Difference]: With dead ends: 427 [2021-12-19 16:26:50,454 INFO L226 Difference]: Without dead ends: 425 [2021-12-19 16:26:50,455 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 45 GetRequests, 42 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-19 16:26:50,457 INFO L933 BasicCegarLoop]: 283 mSDtfsCounter, 171 mSDsluCounter, 560 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 171 SdHoareTripleChecker+Valid, 843 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:50,457 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [171 Valid, 843 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-19 16:26:50,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 425 states. [2021-12-19 16:26:50,467 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 425 to 415. [2021-12-19 16:26:50,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 415 states, 382 states have (on average 1.2827225130890052) internal successors, (490), 397 states have internal predecessors, (490), 14 states have call successors, (14), 6 states have call predecessors, (14), 5 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2021-12-19 16:26:50,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 415 states to 415 states and 518 transitions. [2021-12-19 16:26:50,471 INFO L78 Accepts]: Start accepts. Automaton has 415 states and 518 transitions. Word has length 45 [2021-12-19 16:26:50,471 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:50,472 INFO L470 AbstractCegarLoop]: Abstraction has 415 states and 518 transitions. [2021-12-19 16:26:50,472 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:50,472 INFO L276 IsEmpty]: Start isEmpty. Operand 415 states and 518 transitions. [2021-12-19 16:26:50,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-12-19 16:26:50,475 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:50,475 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] [2021-12-19 16:26:50,495 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-19 16:26:50,691 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-19 16:26:50,691 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:50,692 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:50,692 INFO L85 PathProgramCache]: Analyzing trace with hash 1292392160, now seen corresponding path program 1 times [2021-12-19 16:26:50,692 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:50,692 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [884362828] [2021-12-19 16:26:50,692 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:50,692 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:50,709 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:50,713 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1723948512] [2021-12-19 16:26:50,713 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:50,714 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:50,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:50,715 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-19 16:26:50,716 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-19 16:26:50,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:50,856 INFO L263 TraceCheckSpWp]: Trace formula consists of 247 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-19 16:26:50,857 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:50,926 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-19 16:26:50,927 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:50,927 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:50,931 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [884362828] [2021-12-19 16:26:50,931 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:50,931 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1723948512] [2021-12-19 16:26:50,931 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1723948512] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:50,932 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:50,932 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-19 16:26:50,932 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1949999131] [2021-12-19 16:26:50,932 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:50,932 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-19 16:26:50,932 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:50,933 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-19 16:26:50,933 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-19 16:26:50,933 INFO L87 Difference]: Start difference. First operand 415 states and 518 transitions. Second operand has 4 states, 3 states have (on average 15.0) internal successors, (45), 3 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:50,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:50,962 INFO L93 Difference]: Finished difference Result 723 states and 914 transitions. [2021-12-19 16:26:50,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-19 16:26:50,963 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 15.0) internal successors, (45), 3 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 46 [2021-12-19 16:26:50,963 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:50,965 INFO L225 Difference]: With dead ends: 723 [2021-12-19 16:26:50,965 INFO L226 Difference]: Without dead ends: 721 [2021-12-19 16:26:50,966 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 43 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-19 16:26:50,966 INFO L933 BasicCegarLoop]: 288 mSDtfsCounter, 226 mSDsluCounter, 560 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 226 SdHoareTripleChecker+Valid, 848 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:50,967 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [226 Valid, 848 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-19 16:26:50,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 721 states. [2021-12-19 16:26:50,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 721 to 710. [2021-12-19 16:26:50,979 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 710 states, 666 states have (on average 1.2942942942942943) internal successors, (862), 682 states have internal predecessors, (862), 23 states have call successors, (23), 10 states have call predecessors, (23), 7 states have return successors, (26), 18 states have call predecessors, (26), 23 states have call successors, (26) [2021-12-19 16:26:50,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 710 states to 710 states and 911 transitions. [2021-12-19 16:26:50,981 INFO L78 Accepts]: Start accepts. Automaton has 710 states and 911 transitions. Word has length 46 [2021-12-19 16:26:50,982 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:50,982 INFO L470 AbstractCegarLoop]: Abstraction has 710 states and 911 transitions. [2021-12-19 16:26:50,982 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 15.0) internal successors, (45), 3 states have internal predecessors, (45), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-19 16:26:50,982 INFO L276 IsEmpty]: Start isEmpty. Operand 710 states and 911 transitions. [2021-12-19 16:26:50,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2021-12-19 16:26:50,983 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:50,983 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] [2021-12-19 16:26:51,000 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-19 16:26:51,200 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-19 16:26:51,200 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:51,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:51,201 INFO L85 PathProgramCache]: Analyzing trace with hash -2118750223, now seen corresponding path program 1 times [2021-12-19 16:26:51,201 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:51,201 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2143283890] [2021-12-19 16:26:51,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:51,201 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:51,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:51,248 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-19 16:26:51,249 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:51,249 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2143283890] [2021-12-19 16:26:51,249 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2143283890] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:51,249 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:51,249 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-19 16:26:51,249 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [763213078] [2021-12-19 16:26:51,249 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:51,250 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-19 16:26:51,250 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:51,250 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-19 16:26:51,250 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-19 16:26:51,250 INFO L87 Difference]: Start difference. First operand 710 states and 911 transitions. Second operand has 4 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 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-19 16:26:51,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:51,433 INFO L93 Difference]: Finished difference Result 1147 states and 1491 transitions. [2021-12-19 16:26:51,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-19 16:26:51,433 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 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 49 [2021-12-19 16:26:51,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:51,436 INFO L225 Difference]: With dead ends: 1147 [2021-12-19 16:26:51,436 INFO L226 Difference]: Without dead ends: 954 [2021-12-19 16:26:51,437 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 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-19 16:26:51,437 INFO L933 BasicCegarLoop]: 277 mSDtfsCounter, 108 mSDsluCounter, 484 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 110 SdHoareTripleChecker+Valid, 761 SdHoareTripleChecker+Invalid, 144 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:51,438 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [110 Valid, 761 Invalid, 144 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 141 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-19 16:26:51,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 954 states. [2021-12-19 16:26:51,455 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 954 to 710. [2021-12-19 16:26:51,456 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 710 states, 666 states have (on average 1.2927927927927927) internal successors, (861), 682 states have internal predecessors, (861), 23 states have call successors, (23), 10 states have call predecessors, (23), 7 states have return successors, (26), 18 states have call predecessors, (26), 23 states have call successors, (26) [2021-12-19 16:26:51,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 710 states to 710 states and 910 transitions. [2021-12-19 16:26:51,459 INFO L78 Accepts]: Start accepts. Automaton has 710 states and 910 transitions. Word has length 49 [2021-12-19 16:26:51,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:51,459 INFO L470 AbstractCegarLoop]: Abstraction has 710 states and 910 transitions. [2021-12-19 16:26:51,459 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 12.25) internal successors, (49), 4 states have internal predecessors, (49), 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-19 16:26:51,459 INFO L276 IsEmpty]: Start isEmpty. Operand 710 states and 910 transitions. [2021-12-19 16:26:51,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2021-12-19 16:26:51,461 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:51,461 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] [2021-12-19 16:26:51,461 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2021-12-19 16:26:51,462 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting alt_bzeroErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:51,462 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:51,462 INFO L85 PathProgramCache]: Analyzing trace with hash 1422172071, now seen corresponding path program 1 times [2021-12-19 16:26:51,462 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:51,462 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1058566326] [2021-12-19 16:26:51,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:51,463 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:51,484 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:51,484 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [618150786] [2021-12-19 16:26:51,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:51,484 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:51,485 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:51,485 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-19 16:26:51,527 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-19 16:26:51,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:51,680 INFO L263 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-19 16:26:51,682 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:51,771 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-19 16:26:51,771 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:51,771 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:51,771 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1058566326] [2021-12-19 16:26:51,772 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:51,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [618150786] [2021-12-19 16:26:51,772 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [618150786] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:51,772 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:51,772 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2021-12-19 16:26:51,772 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1258892360] [2021-12-19 16:26:51,772 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:51,773 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-19 16:26:51,773 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:51,773 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-19 16:26:51,773 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-19 16:26:51,773 INFO L87 Difference]: Start difference. First operand 710 states and 910 transitions. Second operand has 3 states, 2 states have (on average 26.0) internal successors, (52), 2 states have internal predecessors, (52), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-19 16:26:51,790 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:51,790 INFO L93 Difference]: Finished difference Result 739 states and 933 transitions. [2021-12-19 16:26:51,790 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-19 16:26:51,790 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 26.0) internal successors, (52), 2 states have internal predecessors, (52), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 55 [2021-12-19 16:26:51,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:51,793 INFO L225 Difference]: With dead ends: 739 [2021-12-19 16:26:51,794 INFO L226 Difference]: Without dead ends: 738 [2021-12-19 16:26:51,794 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 53 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-19 16:26:51,795 INFO L933 BasicCegarLoop]: 290 mSDtfsCounter, 179 mSDsluCounter, 282 mSDsCounter, 0 mSdLazyCounter, 6 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 179 SdHoareTripleChecker+Valid, 572 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 6 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:51,795 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [179 Valid, 572 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 6 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-19 16:26:51,796 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 738 states. [2021-12-19 16:26:51,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 738 to 728. [2021-12-19 16:26:51,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 728 states, 679 states have (on average 1.288659793814433) internal successors, (875), 696 states have internal predecessors, (875), 26 states have call successors, (26), 12 states have call predecessors, (26), 9 states have return successors, (29), 21 states have call predecessors, (29), 26 states have call successors, (29) [2021-12-19 16:26:51,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 728 states to 728 states and 930 transitions. [2021-12-19 16:26:51,812 INFO L78 Accepts]: Start accepts. Automaton has 728 states and 930 transitions. Word has length 55 [2021-12-19 16:26:51,812 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:51,813 INFO L470 AbstractCegarLoop]: Abstraction has 728 states and 930 transitions. [2021-12-19 16:26:51,813 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 26.0) internal successors, (52), 2 states have internal predecessors, (52), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-19 16:26:51,813 INFO L276 IsEmpty]: Start isEmpty. Operand 728 states and 930 transitions. [2021-12-19 16:26:51,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2021-12-19 16:26:51,813 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:51,814 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-19 16:26:51,839 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-19 16:26:52,020 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:52,020 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting alt_bzeroErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:52,020 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:52,021 INFO L85 PathProgramCache]: Analyzing trace with hash 1137661302, now seen corresponding path program 1 times [2021-12-19 16:26:52,021 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:52,021 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1792207316] [2021-12-19 16:26:52,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:52,021 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:52,036 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:52,036 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [689619100] [2021-12-19 16:26:52,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:52,037 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:52,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:52,038 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-19 16:26:52,039 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-19 16:26:52,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:52,198 INFO L263 TraceCheckSpWp]: Trace formula consists of 324 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-19 16:26:52,200 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:52,299 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-19 16:26:52,299 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:52,299 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:52,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1792207316] [2021-12-19 16:26:52,299 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:52,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [689619100] [2021-12-19 16:26:52,299 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [689619100] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:52,299 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:52,299 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2021-12-19 16:26:52,299 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [45479406] [2021-12-19 16:26:52,299 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:52,300 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-19 16:26:52,300 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:52,300 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-19 16:26:52,300 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-19 16:26:52,300 INFO L87 Difference]: Start difference. First operand 728 states and 930 transitions. Second operand has 3 states, 2 states have (on average 26.5) internal successors, (53), 2 states have internal predecessors, (53), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-19 16:26:52,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:52,317 INFO L93 Difference]: Finished difference Result 728 states and 930 transitions. [2021-12-19 16:26:52,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-19 16:26:52,317 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 26.5) internal successors, (53), 2 states have internal predecessors, (53), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 56 [2021-12-19 16:26:52,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:52,323 INFO L225 Difference]: With dead ends: 728 [2021-12-19 16:26:52,324 INFO L226 Difference]: Without dead ends: 727 [2021-12-19 16:26:52,324 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-19 16:26:52,326 INFO L933 BasicCegarLoop]: 282 mSDtfsCounter, 229 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 229 SdHoareTripleChecker+Valid, 282 SdHoareTripleChecker+Invalid, 4 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:52,326 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [229 Valid, 282 Invalid, 4 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-19 16:26:52,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 727 states. [2021-12-19 16:26:52,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 727 to 727. [2021-12-19 16:26:52,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 727 states, 679 states have (on average 1.2857142857142858) internal successors, (873), 695 states have internal predecessors, (873), 26 states have call successors, (26), 12 states have call predecessors, (26), 9 states have return successors, (29), 21 states have call predecessors, (29), 26 states have call successors, (29) [2021-12-19 16:26:52,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 727 states to 727 states and 928 transitions. [2021-12-19 16:26:52,346 INFO L78 Accepts]: Start accepts. Automaton has 727 states and 928 transitions. Word has length 56 [2021-12-19 16:26:52,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:52,346 INFO L470 AbstractCegarLoop]: Abstraction has 727 states and 928 transitions. [2021-12-19 16:26:52,346 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 26.5) internal successors, (53), 2 states have internal predecessors, (53), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-19 16:26:52,347 INFO L276 IsEmpty]: Start isEmpty. Operand 727 states and 928 transitions. [2021-12-19 16:26:52,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2021-12-19 16:26:52,347 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:52,347 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] [2021-12-19 16:26:52,366 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-19 16:26:52,565 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:52,566 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:52,566 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:52,566 INFO L85 PathProgramCache]: Analyzing trace with hash -906147032, now seen corresponding path program 1 times [2021-12-19 16:26:52,566 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:52,566 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [971826827] [2021-12-19 16:26:52,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:52,566 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:52,631 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:52,631 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [138175206] [2021-12-19 16:26:52,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:52,631 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:52,632 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:52,636 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-19 16:26:52,637 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-19 16:26:53,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:53,024 INFO L263 TraceCheckSpWp]: Trace formula consists of 1551 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-19 16:26:53,026 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:53,197 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-19 16:26:53,198 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:53,198 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:53,198 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [971826827] [2021-12-19 16:26:53,198 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:53,198 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [138175206] [2021-12-19 16:26:53,198 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [138175206] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:53,198 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:53,198 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-19 16:26:53,199 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [480179276] [2021-12-19 16:26:53,199 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:53,199 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-19 16:26:53,199 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:53,199 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-19 16:26:53,200 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-19 16:26:53,200 INFO L87 Difference]: Start difference. First operand 727 states and 928 transitions. Second operand has 3 states, 3 states have (on average 19.333333333333332) internal successors, (58), 3 states have internal predecessors, (58), 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-19 16:26:53,283 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:53,283 INFO L93 Difference]: Finished difference Result 1367 states and 1741 transitions. [2021-12-19 16:26:53,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-19 16:26:53,283 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 19.333333333333332) internal successors, (58), 3 states have internal predecessors, (58), 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 58 [2021-12-19 16:26:53,284 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:53,286 INFO L225 Difference]: With dead ends: 1367 [2021-12-19 16:26:53,286 INFO L226 Difference]: Without dead ends: 649 [2021-12-19 16:26:53,287 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 56 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-19 16:26:53,288 INFO L933 BasicCegarLoop]: 327 mSDtfsCounter, 103 mSDsluCounter, 252 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 579 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:53,289 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [109 Valid, 579 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-19 16:26:53,290 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 649 states. [2021-12-19 16:26:53,300 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 649 to 640. [2021-12-19 16:26:53,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 640 states, 598 states have (on average 1.2775919732441472) internal successors, (764), 613 states have internal predecessors, (764), 21 states have call successors, (21), 10 states have call predecessors, (21), 8 states have return successors, (24), 18 states have call predecessors, (24), 21 states have call successors, (24) [2021-12-19 16:26:53,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 640 states to 640 states and 809 transitions. [2021-12-19 16:26:53,304 INFO L78 Accepts]: Start accepts. Automaton has 640 states and 809 transitions. Word has length 58 [2021-12-19 16:26:53,304 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:53,305 INFO L470 AbstractCegarLoop]: Abstraction has 640 states and 809 transitions. [2021-12-19 16:26:53,305 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 19.333333333333332) internal successors, (58), 3 states have internal predecessors, (58), 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-19 16:26:53,305 INFO L276 IsEmpty]: Start isEmpty. Operand 640 states and 809 transitions. [2021-12-19 16:26:53,305 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2021-12-19 16:26:53,305 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:53,305 INFO L514 BasicCegarLoop]: trace histogram [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] [2021-12-19 16:26:53,328 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-12-19 16:26:53,520 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,SelfDestructingSolverStorable9 [2021-12-19 16:26:53,520 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:53,521 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:53,521 INFO L85 PathProgramCache]: Analyzing trace with hash 804842726, now seen corresponding path program 1 times [2021-12-19 16:26:53,521 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:53,521 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [702482719] [2021-12-19 16:26:53,521 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:53,521 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:53,552 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:53,554 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1858916229] [2021-12-19 16:26:53,554 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:53,554 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:53,554 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:53,555 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-19 16:26:53,556 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-19 16:26:53,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:53,818 INFO L263 TraceCheckSpWp]: Trace formula consists of 493 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-19 16:26:53,820 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:53,937 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 16:26:53,937 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 16:26:54,123 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 16:26:54,124 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:54,124 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [702482719] [2021-12-19 16:26:54,124 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:54,124 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1858916229] [2021-12-19 16:26:54,124 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1858916229] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 16:26:54,124 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-19 16:26:54,124 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7] total 13 [2021-12-19 16:26:54,124 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1619694090] [2021-12-19 16:26:54,124 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-19 16:26:54,124 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-19 16:26:54,125 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:54,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-19 16:26:54,125 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2021-12-19 16:26:54,125 INFO L87 Difference]: Start difference. First operand 640 states and 809 transitions. Second operand has 14 states, 13 states have (on average 9.076923076923077) internal successors, (118), 12 states have internal predecessors, (118), 4 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-19 16:26:54,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:54,635 INFO L93 Difference]: Finished difference Result 2064 states and 2645 transitions. [2021-12-19 16:26:54,635 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2021-12-19 16:26:54,635 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 9.076923076923077) internal successors, (118), 12 states have internal predecessors, (118), 4 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Word has length 64 [2021-12-19 16:26:54,636 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:54,641 INFO L225 Difference]: With dead ends: 2064 [2021-12-19 16:26:54,641 INFO L226 Difference]: Without dead ends: 2062 [2021-12-19 16:26:54,641 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 144 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=273, Invalid=597, Unknown=0, NotChecked=0, Total=870 [2021-12-19 16:26:54,642 INFO L933 BasicCegarLoop]: 621 mSDtfsCounter, 1422 mSDsluCounter, 3722 mSDsCounter, 0 mSdLazyCounter, 487 mSolverCounterSat, 111 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1429 SdHoareTripleChecker+Valid, 4343 SdHoareTripleChecker+Invalid, 598 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 111 IncrementalHoareTripleChecker+Valid, 487 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:54,642 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1429 Valid, 4343 Invalid, 598 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [111 Valid, 487 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-19 16:26:54,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2062 states. [2021-12-19 16:26:54,671 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2062 to 1830. [2021-12-19 16:26:54,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1830 states, 1738 states have (on average 1.2836593785960875) internal successors, (2231), 1755 states have internal predecessors, (2231), 60 states have call successors, (60), 24 states have call predecessors, (60), 19 states have return successors, (81), 51 states have call predecessors, (81), 60 states have call successors, (81) [2021-12-19 16:26:54,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1830 states to 1830 states and 2372 transitions. [2021-12-19 16:26:54,678 INFO L78 Accepts]: Start accepts. Automaton has 1830 states and 2372 transitions. Word has length 64 [2021-12-19 16:26:54,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:54,678 INFO L470 AbstractCegarLoop]: Abstraction has 1830 states and 2372 transitions. [2021-12-19 16:26:54,678 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 9.076923076923077) internal successors, (118), 12 states have internal predecessors, (118), 4 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-19 16:26:54,679 INFO L276 IsEmpty]: Start isEmpty. Operand 1830 states and 2372 transitions. [2021-12-19 16:26:54,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2021-12-19 16:26:54,679 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:54,679 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] [2021-12-19 16:26:54,699 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2021-12-19 16:26:54,892 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:54,892 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting alt_bzeroErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:54,893 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:54,893 INFO L85 PathProgramCache]: Analyzing trace with hash -1176759637, now seen corresponding path program 1 times [2021-12-19 16:26:54,893 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:54,893 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [962696270] [2021-12-19 16:26:54,893 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:54,893 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:54,920 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:54,920 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1988715420] [2021-12-19 16:26:54,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:54,920 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:54,921 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:54,921 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-19 16:26:54,947 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-19 16:26:55,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:55,216 INFO L263 TraceCheckSpWp]: Trace formula consists of 630 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-19 16:26:55,219 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:55,330 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 16:26:55,330 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 16:26:55,497 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2021-12-19 16:26:55,497 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:55,497 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [962696270] [2021-12-19 16:26:55,497 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:55,497 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1988715420] [2021-12-19 16:26:55,497 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1988715420] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 16:26:55,497 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-19 16:26:55,498 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 9 [2021-12-19 16:26:55,498 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1654719210] [2021-12-19 16:26:55,498 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-19 16:26:55,498 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-19 16:26:55,498 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:55,498 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-19 16:26:55,498 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=55, Unknown=0, NotChecked=0, Total=90 [2021-12-19 16:26:55,499 INFO L87 Difference]: Start difference. First operand 1830 states and 2372 transitions. Second operand has 10 states, 9 states have (on average 14.222222222222221) internal successors, (128), 10 states have internal predecessors, (128), 4 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2021-12-19 16:26:55,798 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:55,799 INFO L93 Difference]: Finished difference Result 3333 states and 4309 transitions. [2021-12-19 16:26:55,799 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-12-19 16:26:55,799 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 14.222222222222221) internal successors, (128), 10 states have internal predecessors, (128), 4 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) Word has length 74 [2021-12-19 16:26:55,799 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:55,808 INFO L225 Difference]: With dead ends: 3333 [2021-12-19 16:26:55,808 INFO L226 Difference]: Without dead ends: 3332 [2021-12-19 16:26:55,810 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=107, Invalid=165, Unknown=0, NotChecked=0, Total=272 [2021-12-19 16:26:55,810 INFO L933 BasicCegarLoop]: 287 mSDtfsCounter, 715 mSDsluCounter, 1712 mSDsCounter, 0 mSdLazyCounter, 296 mSolverCounterSat, 60 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 724 SdHoareTripleChecker+Valid, 1999 SdHoareTripleChecker+Invalid, 356 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 60 IncrementalHoareTripleChecker+Valid, 296 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:55,810 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [724 Valid, 1999 Invalid, 356 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [60 Valid, 296 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-19 16:26:55,813 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3332 states. [2021-12-19 16:26:55,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3332 to 2995. [2021-12-19 16:26:55,866 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2995 states, 2839 states have (on average 1.280028178936245) internal successors, (3634), 2856 states have internal predecessors, (3634), 102 states have call successors, (102), 51 states have call predecessors, (102), 41 states have return successors, (135), 88 states have call predecessors, (135), 102 states have call successors, (135) [2021-12-19 16:26:55,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2995 states to 2995 states and 3871 transitions. [2021-12-19 16:26:55,874 INFO L78 Accepts]: Start accepts. Automaton has 2995 states and 3871 transitions. Word has length 74 [2021-12-19 16:26:55,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:55,875 INFO L470 AbstractCegarLoop]: Abstraction has 2995 states and 3871 transitions. [2021-12-19 16:26:55,875 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 14.222222222222221) internal successors, (128), 10 states have internal predecessors, (128), 4 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2021-12-19 16:26:55,875 INFO L276 IsEmpty]: Start isEmpty. Operand 2995 states and 3871 transitions. [2021-12-19 16:26:55,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2021-12-19 16:26:55,876 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:55,876 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 16:26:55,911 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2021-12-19 16:26:56,095 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,SelfDestructingSolverStorable11 [2021-12-19 16:26:56,095 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:56,096 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:56,096 INFO L85 PathProgramCache]: Analyzing trace with hash 573613648, now seen corresponding path program 1 times [2021-12-19 16:26:56,096 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:56,096 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2124803466] [2021-12-19 16:26:56,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:56,096 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:56,121 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:56,121 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [512695039] [2021-12-19 16:26:56,121 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:56,122 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:56,122 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:56,123 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-19 16:26:56,124 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-19 16:26:56,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:56,436 INFO L263 TraceCheckSpWp]: Trace formula consists of 760 conjuncts, 19 conjunts are in the unsatisfiable core [2021-12-19 16:26:56,438 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:56,592 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2021-12-19 16:26:56,592 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:56,592 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:56,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2124803466] [2021-12-19 16:26:56,593 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:56,593 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [512695039] [2021-12-19 16:26:56,593 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [512695039] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:56,593 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:56,593 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-12-19 16:26:56,593 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1226686535] [2021-12-19 16:26:56,593 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:56,594 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-19 16:26:56,594 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:56,594 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-19 16:26:56,594 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2021-12-19 16:26:56,594 INFO L87 Difference]: Start difference. First operand 2995 states and 3871 transitions. Second operand has 7 states, 7 states have (on average 11.714285714285714) internal successors, (82), 5 states have internal predecessors, (82), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-19 16:26:56,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:56,713 INFO L93 Difference]: Finished difference Result 5929 states and 7675 transitions. [2021-12-19 16:26:56,714 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-19 16:26:56,714 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 11.714285714285714) internal successors, (82), 5 states have internal predecessors, (82), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 96 [2021-12-19 16:26:56,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:56,722 INFO L225 Difference]: With dead ends: 5929 [2021-12-19 16:26:56,723 INFO L226 Difference]: Without dead ends: 2995 [2021-12-19 16:26:56,727 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 90 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2021-12-19 16:26:56,728 INFO L933 BasicCegarLoop]: 273 mSDtfsCounter, 40 mSDsluCounter, 994 mSDsCounter, 0 mSdLazyCounter, 127 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 1267 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:56,728 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 1267 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-19 16:26:56,730 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2995 states. [2021-12-19 16:26:56,774 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2995 to 2995. [2021-12-19 16:26:56,777 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2995 states, 2839 states have (on average 1.2796759422331807) internal successors, (3633), 2855 states have internal predecessors, (3633), 102 states have call successors, (102), 51 states have call predecessors, (102), 41 states have return successors, (135), 88 states have call predecessors, (135), 102 states have call successors, (135) [2021-12-19 16:26:56,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2995 states to 2995 states and 3870 transitions. [2021-12-19 16:26:56,784 INFO L78 Accepts]: Start accepts. Automaton has 2995 states and 3870 transitions. Word has length 96 [2021-12-19 16:26:56,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:56,784 INFO L470 AbstractCegarLoop]: Abstraction has 2995 states and 3870 transitions. [2021-12-19 16:26:56,784 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 11.714285714285714) internal successors, (82), 5 states have internal predecessors, (82), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-19 16:26:56,784 INFO L276 IsEmpty]: Start isEmpty. Operand 2995 states and 3870 transitions. [2021-12-19 16:26:56,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2021-12-19 16:26:56,785 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:56,785 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 16:26:56,809 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-19 16:26:56,999 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,SelfDestructingSolverStorable12 [2021-12-19 16:26:56,999 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:57,000 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:57,000 INFO L85 PathProgramCache]: Analyzing trace with hash 120930980, now seen corresponding path program 1 times [2021-12-19 16:26:57,000 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:57,000 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1960698976] [2021-12-19 16:26:57,000 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:57,000 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:57,024 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:57,024 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2038564401] [2021-12-19 16:26:57,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:57,024 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:57,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:57,025 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-19 16:26:57,026 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-19 16:26:57,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:57,399 INFO L263 TraceCheckSpWp]: Trace formula consists of 770 conjuncts, 24 conjunts are in the unsatisfiable core [2021-12-19 16:26:57,419 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:57,607 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 16:26:57,607 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-19 16:26:57,607 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:57,607 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1960698976] [2021-12-19 16:26:57,607 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:57,607 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2038564401] [2021-12-19 16:26:57,607 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2038564401] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 16:26:57,607 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 16:26:57,607 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2021-12-19 16:26:57,608 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [48741562] [2021-12-19 16:26:57,608 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 16:26:57,608 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2021-12-19 16:26:57,608 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:57,608 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-12-19 16:26:57,608 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2021-12-19 16:26:57,608 INFO L87 Difference]: Start difference. First operand 2995 states and 3870 transitions. Second operand has 11 states, 11 states have (on average 8.272727272727273) internal successors, (91), 11 states have internal predecessors, (91), 3 states have call successors, (5), 2 states have call predecessors, (5), 4 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-19 16:26:58,095 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:58,096 INFO L93 Difference]: Finished difference Result 4984 states and 6449 transitions. [2021-12-19 16:26:58,096 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-19 16:26:58,096 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 8.272727272727273) internal successors, (91), 11 states have internal predecessors, (91), 3 states have call successors, (5), 2 states have call predecessors, (5), 4 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 101 [2021-12-19 16:26:58,097 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:58,102 INFO L225 Difference]: With dead ends: 4984 [2021-12-19 16:26:58,103 INFO L226 Difference]: Without dead ends: 2031 [2021-12-19 16:26:58,107 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 92 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2021-12-19 16:26:58,108 INFO L933 BasicCegarLoop]: 242 mSDtfsCounter, 493 mSDsluCounter, 1729 mSDsCounter, 0 mSdLazyCounter, 416 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 494 SdHoareTripleChecker+Valid, 1971 SdHoareTripleChecker+Invalid, 443 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 416 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:58,108 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [494 Valid, 1971 Invalid, 443 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 416 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-19 16:26:58,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2031 states. [2021-12-19 16:26:58,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2031 to 2029. [2021-12-19 16:26:58,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2029 states, 1914 states have (on average 1.2795193312434692) internal successors, (2449), 1931 states have internal predecessors, (2449), 63 states have call successors, (63), 43 states have call predecessors, (63), 39 states have return successors, (75), 54 states have call predecessors, (75), 63 states have call successors, (75) [2021-12-19 16:26:58,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2029 states to 2029 states and 2587 transitions. [2021-12-19 16:26:58,153 INFO L78 Accepts]: Start accepts. Automaton has 2029 states and 2587 transitions. Word has length 101 [2021-12-19 16:26:58,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:26:58,153 INFO L470 AbstractCegarLoop]: Abstraction has 2029 states and 2587 transitions. [2021-12-19 16:26:58,153 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 8.272727272727273) internal successors, (91), 11 states have internal predecessors, (91), 3 states have call successors, (5), 2 states have call predecessors, (5), 4 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-19 16:26:58,153 INFO L276 IsEmpty]: Start isEmpty. Operand 2029 states and 2587 transitions. [2021-12-19 16:26:58,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2021-12-19 16:26:58,154 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:26:58,154 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 16:26:58,175 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-19 16:26:58,367 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,SelfDestructingSolverStorable13 [2021-12-19 16:26:58,367 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:26:58,368 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:26:58,368 INFO L85 PathProgramCache]: Analyzing trace with hash -1967918926, now seen corresponding path program 1 times [2021-12-19 16:26:58,368 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:26:58,368 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [114475153] [2021-12-19 16:26:58,368 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:58,368 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:26:58,397 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:26:58,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [199622862] [2021-12-19 16:26:58,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:26:58,398 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:26:58,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:26:58,404 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-19 16:26:58,404 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-19 16:26:58,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 16:26:58,825 INFO L263 TraceCheckSpWp]: Trace formula consists of 800 conjuncts, 30 conjunts are in the unsatisfiable core [2021-12-19 16:26:58,827 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:26:58,992 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 17 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-19 16:26:58,993 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 16:26:59,213 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2021-12-19 16:26:59,214 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:26:59,214 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [114475153] [2021-12-19 16:26:59,214 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:26:59,214 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [199622862] [2021-12-19 16:26:59,214 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [199622862] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 16:26:59,214 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-19 16:26:59,214 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 6] total 16 [2021-12-19 16:26:59,214 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [467861739] [2021-12-19 16:26:59,214 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-19 16:26:59,215 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-12-19 16:26:59,215 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:26:59,215 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-12-19 16:26:59,215 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2021-12-19 16:26:59,215 INFO L87 Difference]: Start difference. First operand 2029 states and 2587 transitions. Second operand has 16 states, 16 states have (on average 7.875) internal successors, (126), 16 states have internal predecessors, (126), 3 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-12-19 16:26:59,934 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:26:59,934 INFO L93 Difference]: Finished difference Result 4098 states and 5264 transitions. [2021-12-19 16:26:59,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-12-19 16:26:59,935 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 7.875) internal successors, (126), 16 states have internal predecessors, (126), 3 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 103 [2021-12-19 16:26:59,935 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:26:59,941 INFO L225 Difference]: With dead ends: 4098 [2021-12-19 16:26:59,941 INFO L226 Difference]: Without dead ends: 2120 [2021-12-19 16:26:59,946 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 193 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=144, Invalid=612, Unknown=0, NotChecked=0, Total=756 [2021-12-19 16:26:59,946 INFO L933 BasicCegarLoop]: 245 mSDtfsCounter, 519 mSDsluCounter, 1994 mSDsCounter, 0 mSdLazyCounter, 535 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 519 SdHoareTripleChecker+Valid, 2239 SdHoareTripleChecker+Invalid, 577 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 535 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2021-12-19 16:26:59,947 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [519 Valid, 2239 Invalid, 577 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 535 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2021-12-19 16:26:59,948 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2120 states. [2021-12-19 16:26:59,997 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2120 to 2087. [2021-12-19 16:27:00,000 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2087 states, 1970 states have (on average 1.2857868020304568) internal successors, (2533), 1983 states have internal predecessors, (2533), 63 states have call successors, (63), 49 states have call predecessors, (63), 41 states have return successors, (71), 54 states have call predecessors, (71), 63 states have call successors, (71) [2021-12-19 16:27:00,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2087 states to 2087 states and 2667 transitions. [2021-12-19 16:27:00,004 INFO L78 Accepts]: Start accepts. Automaton has 2087 states and 2667 transitions. Word has length 103 [2021-12-19 16:27:00,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:27:00,004 INFO L470 AbstractCegarLoop]: Abstraction has 2087 states and 2667 transitions. [2021-12-19 16:27:00,005 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 7.875) internal successors, (126), 16 states have internal predecessors, (126), 3 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-12-19 16:27:00,005 INFO L276 IsEmpty]: Start isEmpty. Operand 2087 states and 2667 transitions. [2021-12-19 16:27:00,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2021-12-19 16:27:00,007 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:27:00,007 INFO L514 BasicCegarLoop]: trace histogram [6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 16:27:00,028 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-19 16:27:00,227 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,SelfDestructingSolverStorable14 [2021-12-19 16:27:00,228 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:27:00,228 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:27:00,228 INFO L85 PathProgramCache]: Analyzing trace with hash -183406268, now seen corresponding path program 2 times [2021-12-19 16:27:00,228 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:27:00,228 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [25138933] [2021-12-19 16:27:00,228 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:27:00,228 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:27:00,263 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:27:00,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [431626308] [2021-12-19 16:27:00,264 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-19 16:27:00,264 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:27:00,264 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:27:00,265 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-19 16:27:00,266 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-19 16:28:29,585 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-19 16:28:29,585 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-19 16:28:29,663 INFO L263 TraceCheckSpWp]: Trace formula consists of 860 conjuncts, 29 conjunts are in the unsatisfiable core [2021-12-19 16:28:29,666 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 16:28:29,899 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 28 proven. 10 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2021-12-19 16:28:29,900 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 16:28:30,216 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2021-12-19 16:28:30,216 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 16:28:30,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [25138933] [2021-12-19 16:28:30,216 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-19 16:28:30,216 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [431626308] [2021-12-19 16:28:30,216 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [431626308] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 16:28:30,216 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-19 16:28:30,216 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 9] total 21 [2021-12-19 16:28:30,217 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [597569903] [2021-12-19 16:28:30,217 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-19 16:28:30,217 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-19 16:28:30,217 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 16:28:30,217 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-19 16:28:30,218 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=342, Unknown=0, NotChecked=0, Total=420 [2021-12-19 16:28:30,218 INFO L87 Difference]: Start difference. First operand 2087 states and 2667 transitions. Second operand has 21 states, 21 states have (on average 5.9523809523809526) internal successors, (125), 21 states have internal predecessors, (125), 3 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-12-19 16:28:31,176 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 16:28:31,177 INFO L93 Difference]: Finished difference Result 4354 states and 5607 transitions. [2021-12-19 16:28:31,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2021-12-19 16:28:31,177 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 5.9523809523809526) internal successors, (125), 21 states have internal predecessors, (125), 3 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 107 [2021-12-19 16:28:31,178 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-19 16:28:31,183 INFO L225 Difference]: With dead ends: 4354 [2021-12-19 16:28:31,183 INFO L226 Difference]: Without dead ends: 2213 [2021-12-19 16:28:31,187 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 195 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 241 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=411, Invalid=1481, Unknown=0, NotChecked=0, Total=1892 [2021-12-19 16:28:31,187 INFO L933 BasicCegarLoop]: 275 mSDtfsCounter, 350 mSDsluCounter, 2755 mSDsCounter, 0 mSdLazyCounter, 561 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 364 SdHoareTripleChecker+Valid, 3030 SdHoareTripleChecker+Invalid, 628 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 561 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-19 16:28:31,187 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [364 Valid, 3030 Invalid, 628 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 561 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-19 16:28:31,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2213 states. [2021-12-19 16:28:31,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2213 to 2126. [2021-12-19 16:28:31,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2126 states, 2009 states have (on average 1.2797411647585863) internal successors, (2571), 2022 states have internal predecessors, (2571), 63 states have call successors, (63), 49 states have call predecessors, (63), 41 states have return successors, (71), 54 states have call predecessors, (71), 63 states have call successors, (71) [2021-12-19 16:28:31,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2126 states to 2126 states and 2705 transitions. [2021-12-19 16:28:31,232 INFO L78 Accepts]: Start accepts. Automaton has 2126 states and 2705 transitions. Word has length 107 [2021-12-19 16:28:31,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-19 16:28:31,232 INFO L470 AbstractCegarLoop]: Abstraction has 2126 states and 2705 transitions. [2021-12-19 16:28:31,232 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 5.9523809523809526) internal successors, (125), 21 states have internal predecessors, (125), 3 states have call successors, (8), 2 states have call predecessors, (8), 6 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2021-12-19 16:28:31,232 INFO L276 IsEmpty]: Start isEmpty. Operand 2126 states and 2705 transitions. [2021-12-19 16:28:31,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2021-12-19 16:28:31,233 INFO L506 BasicCegarLoop]: Found error trace [2021-12-19 16:28:31,233 INFO L514 BasicCegarLoop]: trace histogram [15, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-19 16:28:31,291 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2021-12-19 16:28:31,447 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:28:31,447 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [alt_mallocErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_mallocErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, alt_freeErr0ASSERT_VIOLATIONINTEGER_OVERFLOW (and 11 more)] === [2021-12-19 16:28:31,448 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 16:28:31,448 INFO L85 PathProgramCache]: Analyzing trace with hash -1355245281, now seen corresponding path program 3 times [2021-12-19 16:28:31,448 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 16:28:31,448 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [143242834] [2021-12-19 16:28:31,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 16:28:31,448 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 16:28:31,478 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-19 16:28:31,479 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [614387983] [2021-12-19 16:28:31,479 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-19 16:28:31,479 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 16:28:31,479 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 16:28:31,480 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-19 16:28:31,483 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process Killed by 15