./Ultimate.py --spec ../sv-benchmarks/c/properties/valid-memsafety.prp --file ../sv-benchmarks/c/ldv-memsafety/memleaks_test12-2.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version ff03de63 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerMemDerefMemtrack.xml -i ../sv-benchmarks/c/ldv-memsafety/memleaks_test12-2.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-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 valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 7f08d75c904d21d6573220c7737d451cd978e8a22a153e855f8d685d88a1eb60 --- Real Ultimate output --- This is Ultimate 0.2.2-dev-ff03de6 [2021-12-21 18:09:09,035 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-21 18:09:09,064 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-21 18:09:09,109 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-21 18:09:09,109 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-21 18:09:09,112 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-21 18:09:09,114 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-21 18:09:09,117 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-21 18:09:09,118 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-21 18:09:09,123 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-21 18:09:09,124 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-21 18:09:09,124 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-21 18:09:09,125 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-21 18:09:09,126 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-21 18:09:09,128 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-21 18:09:09,128 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-21 18:09:09,129 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-21 18:09:09,130 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-21 18:09:09,134 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-21 18:09:09,135 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-21 18:09:09,136 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-21 18:09:09,136 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-21 18:09:09,137 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-21 18:09:09,138 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-21 18:09:09,139 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-21 18:09:09,139 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-21 18:09:09,139 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-21 18:09:09,140 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-21 18:09:09,140 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-21 18:09:09,141 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-21 18:09:09,141 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-21 18:09:09,141 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-21 18:09:09,142 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-21 18:09:09,142 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-21 18:09:09,143 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-21 18:09:09,143 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-21 18:09:09,144 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-21 18:09:09,145 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-21 18:09:09,145 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-21 18:09:09,145 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-21 18:09:09,146 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-21 18:09:09,147 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-32bit-Automizer_Default.epf [2021-12-21 18:09:09,170 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-21 18:09:09,170 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-21 18:09:09,171 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-21 18:09:09,171 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-21 18:09:09,171 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-21 18:09:09,172 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-21 18:09:09,172 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-21 18:09:09,172 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-21 18:09:09,172 INFO L138 SettingsManager]: * Use SBE=true [2021-12-21 18:09:09,173 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-21 18:09:09,173 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-21 18:09:09,173 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-21 18:09:09,174 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-21 18:09:09,174 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-21 18:09:09,174 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-21 18:09:09,174 INFO L138 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2021-12-21 18:09:09,174 INFO L138 SettingsManager]: * Bitprecise bitfields=true [2021-12-21 18:09:09,174 INFO L138 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2021-12-21 18:09:09,175 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-21 18:09:09,175 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2021-12-21 18:09:09,175 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-21 18:09:09,175 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-21 18:09:09,175 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-21 18:09:09,175 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-21 18:09:09,176 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-21 18:09:09,176 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-21 18:09:09,176 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-21 18:09:09,176 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-21 18:09:09,176 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-21 18:09:09,176 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-21 18:09:09,176 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-21 18:09:09,177 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 valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) 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 -> 7f08d75c904d21d6573220c7737d451cd978e8a22a153e855f8d685d88a1eb60 [2021-12-21 18:09:09,367 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-21 18:09:09,403 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-21 18:09:09,405 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-21 18:09:09,406 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-21 18:09:09,407 INFO L275 PluginConnector]: CDTParser initialized [2021-12-21 18:09:09,408 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/ldv-memsafety/memleaks_test12-2.i [2021-12-21 18:09:09,463 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2b954f71b/63ca4992981145e5b1504e70ab59d224/FLAG7cd842066 [2021-12-21 18:09:09,881 INFO L306 CDTParser]: Found 1 translation units. [2021-12-21 18:09:09,887 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-memsafety/memleaks_test12-2.i [2021-12-21 18:09:09,909 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2b954f71b/63ca4992981145e5b1504e70ab59d224/FLAG7cd842066 [2021-12-21 18:09:09,920 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2b954f71b/63ca4992981145e5b1504e70ab59d224 [2021-12-21 18:09:09,922 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-21 18:09:09,924 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-21 18:09:09,925 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-21 18:09:09,926 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-21 18:09:09,928 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-21 18:09:09,928 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 06:09:09" (1/1) ... [2021-12-21 18:09:09,929 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@43251379 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:09, skipping insertion in model container [2021-12-21 18:09:09,929 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 06:09:09" (1/1) ... [2021-12-21 18:09:09,934 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-21 18:09:09,985 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-21 18:09:10,268 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 18:09:10,283 ERROR L326 MainTranslator]: Unsupported Syntax: Found a cast between two array/pointer types where the value type is smaller than the cast-to type while using memory model HoenickeLindenmann_Original (while Not using bitvector translation) [2021-12-21 18:09:10,284 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.CACSL2BoogieTranslatorObserver@4f8d5352 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:10, skipping insertion in model container [2021-12-21 18:09:10,284 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-21 18:09:10,284 INFO L184 ToolchainWalker]: Toolchain execution was canceled (user or tool) before executing de.uni_freiburg.informatik.ultimate.boogie.procedureinliner [2021-12-21 18:09:10,285 INFO L158 Benchmark]: Toolchain (without parser) took 360.93ms. Allocated memory is still 100.7MB. Free memory was 68.5MB in the beginning and 70.0MB in the end (delta: -1.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-21 18:09:10,286 INFO L158 Benchmark]: CDTParser took 0.34ms. Allocated memory is still 83.9MB. Free memory was 40.7MB in the beginning and 40.7MB in the end (delta: 75.6kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-21 18:09:10,286 INFO L158 Benchmark]: CACSL2BoogieTranslator took 358.61ms. Allocated memory is still 100.7MB. Free memory was 68.0MB in the beginning and 70.0MB in the end (delta: -2.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-21 18:09:10,287 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.34ms. Allocated memory is still 83.9MB. Free memory was 40.7MB in the beginning and 40.7MB in the end (delta: 75.6kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 358.61ms. Allocated memory is still 100.7MB. Free memory was 68.0MB in the beginning and 70.0MB in the end (delta: -2.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - UnsupportedSyntaxResult [Line: 576]: Unsupported Syntax Found a cast between two array/pointer types where the value type is smaller than the cast-to type while using memory model HoenickeLindenmann_Original (while Not using bitvector translation) RESULT: Ultimate could not prove your program: Toolchain returned no result. Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### 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/AutomizerMemDerefMemtrack.xml -i ../sv-benchmarks/c/ldv-memsafety/memleaks_test12-2.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-32bit-Automizer_Bitvector.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 valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 7f08d75c904d21d6573220c7737d451cd978e8a22a153e855f8d685d88a1eb60 --- Real Ultimate output --- This is Ultimate 0.2.2-dev-ff03de6 [2021-12-21 18:09:11,801 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-21 18:09:11,803 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-21 18:09:11,835 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-21 18:09:11,836 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-21 18:09:11,838 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-21 18:09:11,840 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-21 18:09:11,843 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-21 18:09:11,845 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-21 18:09:11,848 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-21 18:09:11,849 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-21 18:09:11,856 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-21 18:09:11,856 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-21 18:09:11,857 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-21 18:09:11,858 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-21 18:09:11,860 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-21 18:09:11,861 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-21 18:09:11,861 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-21 18:09:11,863 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-21 18:09:11,867 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-21 18:09:11,868 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-21 18:09:11,869 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-21 18:09:11,870 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-21 18:09:11,871 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-21 18:09:11,876 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-21 18:09:11,876 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-21 18:09:11,877 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-21 18:09:11,878 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-21 18:09:11,878 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-21 18:09:11,879 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-21 18:09:11,879 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-21 18:09:11,880 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-21 18:09:11,881 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-21 18:09:11,881 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-21 18:09:11,882 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-21 18:09:11,882 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-21 18:09:11,883 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-21 18:09:11,883 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-21 18:09:11,883 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-21 18:09:11,884 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-21 18:09:11,885 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-21 18:09:11,888 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-32bit-Automizer_Bitvector.epf [2021-12-21 18:09:11,917 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-21 18:09:11,918 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-21 18:09:11,919 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-21 18:09:11,919 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-21 18:09:11,920 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-21 18:09:11,920 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-21 18:09:11,921 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-21 18:09:11,921 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-21 18:09:11,921 INFO L138 SettingsManager]: * Use SBE=true [2021-12-21 18:09:11,922 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-21 18:09:11,922 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-21 18:09:11,922 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-21 18:09:11,923 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-21 18:09:11,923 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-21 18:09:11,923 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-21 18:09:11,923 INFO L138 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2021-12-21 18:09:11,923 INFO L138 SettingsManager]: * Bitprecise bitfields=true [2021-12-21 18:09:11,923 INFO L138 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2021-12-21 18:09:11,924 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-21 18:09:11,924 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2021-12-21 18:09:11,924 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2021-12-21 18:09:11,924 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2021-12-21 18:09:11,924 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-21 18:09:11,924 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-21 18:09:11,925 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-21 18:09:11,925 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-21 18:09:11,932 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-21 18:09:11,932 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-21 18:09:11,933 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-21 18:09:11,933 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-21 18:09:11,933 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2021-12-21 18:09:11,933 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2021-12-21 18:09:11,934 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-21 18:09:11,934 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-12-21 18:09:11,934 INFO L138 SettingsManager]: * Logic for external solver=AUFBV 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 valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) 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 -> 7f08d75c904d21d6573220c7737d451cd978e8a22a153e855f8d685d88a1eb60 [2021-12-21 18:09:12,225 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-21 18:09:12,269 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-21 18:09:12,271 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-21 18:09:12,273 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-21 18:09:12,273 INFO L275 PluginConnector]: CDTParser initialized [2021-12-21 18:09:12,275 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/ldv-memsafety/memleaks_test12-2.i [2021-12-21 18:09:12,318 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1963e5b28/b6877f700da84d90bd1ebb3018bc30d4/FLAG389c6cc01 [2021-12-21 18:09:12,761 INFO L306 CDTParser]: Found 1 translation units. [2021-12-21 18:09:12,761 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-memsafety/memleaks_test12-2.i [2021-12-21 18:09:12,774 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1963e5b28/b6877f700da84d90bd1ebb3018bc30d4/FLAG389c6cc01 [2021-12-21 18:09:12,785 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1963e5b28/b6877f700da84d90bd1ebb3018bc30d4 [2021-12-21 18:09:12,788 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-21 18:09:12,789 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-21 18:09:12,791 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-21 18:09:12,792 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-21 18:09:12,794 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-21 18:09:12,795 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 06:09:12" (1/1) ... [2021-12-21 18:09:12,796 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@538fad2c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:12, skipping insertion in model container [2021-12-21 18:09:12,796 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 06:09:12" (1/1) ... [2021-12-21 18:09:12,801 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-21 18:09:12,846 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-21 18:09:13,265 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 18:09:13,282 INFO L200 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2021-12-21 18:09:13,293 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-21 18:09:13,350 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 18:09:13,361 INFO L203 MainTranslator]: Completed pre-run [2021-12-21 18:09:13,401 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 18:09:13,440 INFO L208 MainTranslator]: Completed translation [2021-12-21 18:09:13,441 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13 WrapperNode [2021-12-21 18:09:13,447 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-21 18:09:13,453 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-21 18:09:13,453 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-21 18:09:13,453 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-21 18:09:13,459 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,481 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,538 INFO L137 Inliner]: procedures = 179, calls = 145, calls flagged for inlining = 33, calls inlined = 20, statements flattened = 332 [2021-12-21 18:09:13,541 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-21 18:09:13,541 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-21 18:09:13,541 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-21 18:09:13,542 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-21 18:09:13,549 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,549 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,556 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,557 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,576 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,600 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,603 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,608 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-21 18:09:13,611 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-21 18:09:13,612 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-21 18:09:13,612 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-21 18:09:13,613 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (1/1) ... [2021-12-21 18:09:13,626 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-21 18:09:13,635 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 18:09:13,647 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-12-21 18:09:13,672 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-12-21 18:09:13,698 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE1 [2021-12-21 18:09:13,698 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE4 [2021-12-21 18:09:13,699 INFO L130 BoogieDeclarations]: Found specification of procedure read~unchecked~$Pointer$ [2021-12-21 18:09:13,699 INFO L130 BoogieDeclarations]: Found specification of procedure write~unchecked~$Pointer$ [2021-12-21 18:09:13,699 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memcpy [2021-12-21 18:09:13,699 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memcpy [2021-12-21 18:09:13,699 INFO L130 BoogieDeclarations]: Found specification of procedure LDV_INIT_LIST_HEAD [2021-12-21 18:09:13,699 INFO L138 BoogieDeclarations]: Found implementation of procedure LDV_INIT_LIST_HEAD [2021-12-21 18:09:13,699 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2021-12-21 18:09:13,700 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2021-12-21 18:09:13,700 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_malloc [2021-12-21 18:09:13,700 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_malloc [2021-12-21 18:09:13,700 INFO L130 BoogieDeclarations]: Found specification of procedure write~unchecked~intINTTYPE4 [2021-12-21 18:09:13,701 INFO L130 BoogieDeclarations]: Found specification of procedure write~unchecked~intINTTYPE1 [2021-12-21 18:09:13,701 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-21 18:09:13,701 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-21 18:09:13,701 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_msg_free [2021-12-21 18:09:13,701 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_msg_free [2021-12-21 18:09:13,701 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-21 18:09:13,702 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-21 18:09:13,702 INFO L130 BoogieDeclarations]: Found specification of procedure read~unchecked~intINTTYPE4 [2021-12-21 18:09:13,702 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-21 18:09:13,702 INFO L130 BoogieDeclarations]: Found specification of procedure write~intINTTYPE1 [2021-12-21 18:09:13,702 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-21 18:09:13,702 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2021-12-21 18:09:13,703 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE4 [2021-12-21 18:09:13,703 INFO L130 BoogieDeclarations]: Found specification of procedure read~unchecked~intINTTYPE1 [2021-12-21 18:09:13,703 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-21 18:09:13,703 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-21 18:09:13,870 INFO L234 CfgBuilder]: Building ICFG [2021-12-21 18:09:13,871 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-21 18:09:13,877 WARN L813 $ProcedureCfgBuilder]: Label in the middle of a codeblock. [2021-12-21 18:09:14,832 INFO L275 CfgBuilder]: Performing block encoding [2021-12-21 18:09:14,839 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-21 18:09:14,839 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2021-12-21 18:09:14,841 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 06:09:14 BoogieIcfgContainer [2021-12-21 18:09:14,841 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-21 18:09:14,842 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-21 18:09:14,842 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-21 18:09:14,845 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-21 18:09:14,845 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.12 06:09:12" (1/3) ... [2021-12-21 18:09:14,846 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2bc43b4a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 06:09:14, skipping insertion in model container [2021-12-21 18:09:14,846 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 06:09:13" (2/3) ... [2021-12-21 18:09:14,846 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2bc43b4a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 06:09:14, skipping insertion in model container [2021-12-21 18:09:14,846 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 06:09:14" (3/3) ... [2021-12-21 18:09:14,848 INFO L111 eAbstractionObserver]: Analyzing ICFG memleaks_test12-2.i [2021-12-21 18:09:14,852 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-21 18:09:14,852 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 124 error locations. [2021-12-21 18:09:14,888 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-21 18:09:14,893 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=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR [2021-12-21 18:09:14,894 INFO L340 AbstractCegarLoop]: Starting to check reachability of 124 error locations. [2021-12-21 18:09:14,916 INFO L276 IsEmpty]: Start isEmpty. Operand has 313 states, 171 states have (on average 1.8654970760233918) internal successors, (319), 294 states have internal predecessors, (319), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2021-12-21 18:09:14,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-12-21 18:09:14,923 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:14,924 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:14,924 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr89REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:14,929 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:14,930 INFO L85 PathProgramCache]: Analyzing trace with hash -297378988, now seen corresponding path program 1 times [2021-12-21 18:09:14,939 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:14,940 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1098679383] [2021-12-21 18:09:14,941 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:14,941 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:14,942 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:14,955 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:14,965 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Waiting until timeout for monitored process [2021-12-21 18:09:15,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:15,112 INFO L263 TraceCheckSpWp]: Trace formula consists of 34 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-21 18:09:15,119 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:15,284 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:15,284 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:15,285 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:15,285 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1098679383] [2021-12-21 18:09:15,286 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1098679383] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:15,286 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:15,286 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-21 18:09:15,288 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1904227638] [2021-12-21 18:09:15,289 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:15,292 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 18:09:15,292 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:15,314 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 18:09:15,315 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 18:09:15,319 INFO L87 Difference]: Start difference. First operand has 313 states, 171 states have (on average 1.8654970760233918) internal successors, (319), 294 states have internal predecessors, (319), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) Second operand has 4 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:15,897 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:15,897 INFO L93 Difference]: Finished difference Result 412 states and 459 transitions. [2021-12-21 18:09:15,898 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 18:09:15,899 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-12-21 18:09:15,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:15,909 INFO L225 Difference]: With dead ends: 412 [2021-12-21 18:09:15,910 INFO L226 Difference]: Without dead ends: 408 [2021-12-21 18:09:15,914 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:15,920 INFO L933 BasicCegarLoop]: 234 mSDtfsCounter, 299 mSDsluCounter, 288 mSDsCounter, 0 mSdLazyCounter, 309 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 304 SdHoareTripleChecker+Valid, 522 SdHoareTripleChecker+Invalid, 336 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 309 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:15,920 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [304 Valid, 522 Invalid, 336 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 309 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-21 18:09:15,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 408 states. [2021-12-21 18:09:15,981 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 408 to 344. [2021-12-21 18:09:15,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 344 states, 200 states have (on average 1.83) internal successors, (366), 321 states have internal predecessors, (366), 17 states have call successors, (17), 7 states have call predecessors, (17), 7 states have return successors, (19), 17 states have call predecessors, (19), 17 states have call successors, (19) [2021-12-21 18:09:15,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 344 states to 344 states and 402 transitions. [2021-12-21 18:09:15,985 INFO L78 Accepts]: Start accepts. Automaton has 344 states and 402 transitions. Word has length 11 [2021-12-21 18:09:15,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:15,985 INFO L470 AbstractCegarLoop]: Abstraction has 344 states and 402 transitions. [2021-12-21 18:09:15,985 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:15,986 INFO L276 IsEmpty]: Start isEmpty. Operand 344 states and 402 transitions. [2021-12-21 18:09:15,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-12-21 18:09:15,986 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:15,986 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:15,993 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Ended with exit code 0 [2021-12-21 18:09:16,193 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:16,194 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr90REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:16,195 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:16,195 INFO L85 PathProgramCache]: Analyzing trace with hash -297378987, now seen corresponding path program 1 times [2021-12-21 18:09:16,195 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:16,195 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [559169907] [2021-12-21 18:09:16,195 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:16,196 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:16,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:16,197 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:16,198 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Waiting until timeout for monitored process [2021-12-21 18:09:16,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:16,270 INFO L263 TraceCheckSpWp]: Trace formula consists of 34 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-21 18:09:16,273 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:16,386 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:16,386 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:16,386 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:16,386 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [559169907] [2021-12-21 18:09:16,387 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [559169907] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:16,390 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:16,390 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-21 18:09:16,390 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1544227966] [2021-12-21 18:09:16,390 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:16,391 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 18:09:16,392 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:16,392 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 18:09:16,392 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 18:09:16,392 INFO L87 Difference]: Start difference. First operand 344 states and 402 transitions. Second operand has 4 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:17,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:17,070 INFO L93 Difference]: Finished difference Result 476 states and 564 transitions. [2021-12-21 18:09:17,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 18:09:17,071 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-12-21 18:09:17,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:17,074 INFO L225 Difference]: With dead ends: 476 [2021-12-21 18:09:17,074 INFO L226 Difference]: Without dead ends: 476 [2021-12-21 18:09:17,074 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:17,075 INFO L933 BasicCegarLoop]: 370 mSDtfsCounter, 131 mSDsluCounter, 479 mSDsCounter, 0 mSdLazyCounter, 306 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 132 SdHoareTripleChecker+Valid, 849 SdHoareTripleChecker+Invalid, 315 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 306 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:17,075 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [132 Valid, 849 Invalid, 315 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 306 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2021-12-21 18:09:17,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 476 states. [2021-12-21 18:09:17,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 476 to 407. [2021-12-21 18:09:17,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 407 states, 256 states have (on average 1.83203125) internal successors, (469), 376 states have internal predecessors, (469), 22 states have call successors, (22), 9 states have call predecessors, (22), 9 states have return successors, (29), 23 states have call predecessors, (29), 22 states have call successors, (29) [2021-12-21 18:09:17,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 407 states to 407 states and 520 transitions. [2021-12-21 18:09:17,091 INFO L78 Accepts]: Start accepts. Automaton has 407 states and 520 transitions. Word has length 11 [2021-12-21 18:09:17,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:17,091 INFO L470 AbstractCegarLoop]: Abstraction has 407 states and 520 transitions. [2021-12-21 18:09:17,091 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:17,092 INFO L276 IsEmpty]: Start isEmpty. Operand 407 states and 520 transitions. [2021-12-21 18:09:17,092 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-12-21 18:09:17,092 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:17,092 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:17,109 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (3)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:17,303 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:17,306 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr90REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:17,306 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:17,306 INFO L85 PathProgramCache]: Analyzing trace with hash -1184882668, now seen corresponding path program 1 times [2021-12-21 18:09:17,307 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:17,307 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1276963341] [2021-12-21 18:09:17,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:17,307 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:17,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:17,324 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:17,331 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Waiting until timeout for monitored process [2021-12-21 18:09:17,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:17,396 INFO L263 TraceCheckSpWp]: Trace formula consists of 40 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-21 18:09:17,397 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:17,430 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:17,430 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:17,430 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:17,431 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1276963341] [2021-12-21 18:09:17,431 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1276963341] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:17,431 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:17,431 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 18:09:17,431 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1291485784] [2021-12-21 18:09:17,431 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:17,431 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:17,432 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:17,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:17,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:17,432 INFO L87 Difference]: Start difference. First operand 407 states and 520 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:17,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:17,567 INFO L93 Difference]: Finished difference Result 649 states and 797 transitions. [2021-12-21 18:09:17,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:09:17,568 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2021-12-21 18:09:17,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:17,571 INFO L225 Difference]: With dead ends: 649 [2021-12-21 18:09:17,572 INFO L226 Difference]: Without dead ends: 649 [2021-12-21 18:09:17,572 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:17,573 INFO L933 BasicCegarLoop]: 390 mSDtfsCounter, 259 mSDsluCounter, 1111 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 277 SdHoareTripleChecker+Valid, 1501 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:17,573 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [277 Valid, 1501 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 18:09:17,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 649 states. [2021-12-21 18:09:17,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 649 to 392. [2021-12-21 18:09:17,589 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 392 states, 241 states have (on average 1.8215767634854771) internal successors, (439), 362 states have internal predecessors, (439), 21 states have call successors, (21), 9 states have call predecessors, (21), 10 states have return successors, (34), 22 states have call predecessors, (34), 21 states have call successors, (34) [2021-12-21 18:09:17,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 392 states to 392 states and 494 transitions. [2021-12-21 18:09:17,591 INFO L78 Accepts]: Start accepts. Automaton has 392 states and 494 transitions. Word has length 11 [2021-12-21 18:09:17,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:17,592 INFO L470 AbstractCegarLoop]: Abstraction has 392 states and 494 transitions. [2021-12-21 18:09:17,592 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:17,592 INFO L276 IsEmpty]: Start isEmpty. Operand 392 states and 494 transitions. [2021-12-21 18:09:17,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2021-12-21 18:09:17,593 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:17,593 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:17,607 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Ended with exit code 0 [2021-12-21 18:09:17,802 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:17,803 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr91REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:17,804 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:17,804 INFO L85 PathProgramCache]: Analyzing trace with hash 1981613461, now seen corresponding path program 1 times [2021-12-21 18:09:17,804 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:17,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1310602574] [2021-12-21 18:09:17,805 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:17,805 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:17,805 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:17,820 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:17,861 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Waiting until timeout for monitored process [2021-12-21 18:09:17,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:17,932 INFO L263 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-21 18:09:17,933 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:18,092 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:09:18,122 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:18,123 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:18,123 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:18,123 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1310602574] [2021-12-21 18:09:18,124 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1310602574] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:18,124 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:18,124 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-21 18:09:18,124 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [119286082] [2021-12-21 18:09:18,124 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:18,124 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-21 18:09:18,125 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:18,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-21 18:09:18,125 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-21 18:09:18,125 INFO L87 Difference]: Start difference. First operand 392 states and 494 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:19,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:19,043 INFO L93 Difference]: Finished difference Result 436 states and 541 transitions. [2021-12-21 18:09:19,045 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 18:09:19,045 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2021-12-21 18:09:19,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:19,047 INFO L225 Difference]: With dead ends: 436 [2021-12-21 18:09:19,047 INFO L226 Difference]: Without dead ends: 436 [2021-12-21 18:09:19,047 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2021-12-21 18:09:19,048 INFO L933 BasicCegarLoop]: 323 mSDtfsCounter, 59 mSDsluCounter, 829 mSDsCounter, 0 mSdLazyCounter, 562 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 1152 SdHoareTripleChecker+Invalid, 567 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 562 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:19,048 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 1152 Invalid, 567 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 562 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2021-12-21 18:09:19,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 436 states. [2021-12-21 18:09:19,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 436 to 404. [2021-12-21 18:09:19,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 404 states, 250 states have (on average 1.804) internal successors, (451), 372 states have internal predecessors, (451), 21 states have call successors, (21), 11 states have call predecessors, (21), 13 states have return successors, (34), 22 states have call predecessors, (34), 21 states have call successors, (34) [2021-12-21 18:09:19,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 404 states to 404 states and 506 transitions. [2021-12-21 18:09:19,058 INFO L78 Accepts]: Start accepts. Automaton has 404 states and 506 transitions. Word has length 13 [2021-12-21 18:09:19,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:19,059 INFO L470 AbstractCegarLoop]: Abstraction has 404 states and 506 transitions. [2021-12-21 18:09:19,059 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:19,061 INFO L276 IsEmpty]: Start isEmpty. Operand 404 states and 506 transitions. [2021-12-21 18:09:19,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2021-12-21 18:09:19,061 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:19,061 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:19,073 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (5)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:19,268 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:19,268 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr92REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:19,268 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:19,269 INFO L85 PathProgramCache]: Analyzing trace with hash 1981613462, now seen corresponding path program 1 times [2021-12-21 18:09:19,269 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:19,269 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [998877681] [2021-12-21 18:09:19,269 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:19,269 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:19,269 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:19,270 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:19,271 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Waiting until timeout for monitored process [2021-12-21 18:09:19,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:19,333 INFO L263 TraceCheckSpWp]: Trace formula consists of 44 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-21 18:09:19,334 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:19,514 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:09:19,521 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:09:19,550 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:19,550 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:19,550 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:19,550 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [998877681] [2021-12-21 18:09:19,550 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [998877681] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:19,550 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:19,550 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-21 18:09:19,551 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [802827403] [2021-12-21 18:09:19,551 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:19,551 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-21 18:09:19,551 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:19,551 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-21 18:09:19,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-21 18:09:19,551 INFO L87 Difference]: Start difference. First operand 404 states and 506 transitions. Second operand has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:20,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:20,482 INFO L93 Difference]: Finished difference Result 424 states and 522 transitions. [2021-12-21 18:09:20,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-21 18:09:20,483 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2021-12-21 18:09:20,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:20,485 INFO L225 Difference]: With dead ends: 424 [2021-12-21 18:09:20,485 INFO L226 Difference]: Without dead ends: 424 [2021-12-21 18:09:20,486 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2021-12-21 18:09:20,486 INFO L933 BasicCegarLoop]: 349 mSDtfsCounter, 33 mSDsluCounter, 943 mSDsCounter, 0 mSdLazyCounter, 489 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 1292 SdHoareTripleChecker+Invalid, 493 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 489 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:20,487 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 1292 Invalid, 493 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 489 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2021-12-21 18:09:20,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 424 states. [2021-12-21 18:09:20,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 424 to 413. [2021-12-21 18:09:20,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 413 states, 259 states have (on average 1.7915057915057915) internal successors, (464), 381 states have internal predecessors, (464), 21 states have call successors, (21), 11 states have call predecessors, (21), 13 states have return successors, (34), 22 states have call predecessors, (34), 21 states have call successors, (34) [2021-12-21 18:09:20,496 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 413 states to 413 states and 519 transitions. [2021-12-21 18:09:20,496 INFO L78 Accepts]: Start accepts. Automaton has 413 states and 519 transitions. Word has length 13 [2021-12-21 18:09:20,496 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:20,496 INFO L470 AbstractCegarLoop]: Abstraction has 413 states and 519 transitions. [2021-12-21 18:09:20,497 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.2) internal successors, (11), 5 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:20,497 INFO L276 IsEmpty]: Start isEmpty. Operand 413 states and 519 transitions. [2021-12-21 18:09:20,497 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-12-21 18:09:20,497 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:20,498 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:20,506 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (6)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:20,704 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:20,705 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr86ASSERT_VIOLATIONMEMORY_FREE === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:20,706 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:20,706 INFO L85 PathProgramCache]: Analyzing trace with hash 1895308392, now seen corresponding path program 1 times [2021-12-21 18:09:20,707 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:20,707 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1443527588] [2021-12-21 18:09:20,707 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:20,707 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:20,707 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:20,708 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:20,709 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Waiting until timeout for monitored process [2021-12-21 18:09:20,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:20,762 INFO L263 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 18:09:20,763 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:20,824 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:20,824 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:20,824 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:20,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1443527588] [2021-12-21 18:09:20,824 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1443527588] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:20,824 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:20,824 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 18:09:20,825 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1584834789] [2021-12-21 18:09:20,825 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:20,825 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:20,825 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:20,825 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:20,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:20,825 INFO L87 Difference]: Start difference. First operand 413 states and 519 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:20,868 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:20,868 INFO L93 Difference]: Finished difference Result 351 states and 397 transitions. [2021-12-21 18:09:20,869 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:09:20,870 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2021-12-21 18:09:20,870 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:20,871 INFO L225 Difference]: With dead ends: 351 [2021-12-21 18:09:20,871 INFO L226 Difference]: Without dead ends: 351 [2021-12-21 18:09:20,871 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:20,872 INFO L933 BasicCegarLoop]: 343 mSDtfsCounter, 10 mSDsluCounter, 1007 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 1350 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:20,874 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 1350 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 18:09:20,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 351 states. [2021-12-21 18:09:20,881 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 351 to 345. [2021-12-21 18:09:20,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 345 states, 199 states have (on average 1.7688442211055277) internal successors, (352), 320 states have internal predecessors, (352), 16 states have call successors, (16), 9 states have call predecessors, (16), 10 states have return successors, (19), 17 states have call predecessors, (19), 16 states have call successors, (19) [2021-12-21 18:09:20,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 345 states to 345 states and 387 transitions. [2021-12-21 18:09:20,885 INFO L78 Accepts]: Start accepts. Automaton has 345 states and 387 transitions. Word has length 17 [2021-12-21 18:09:20,885 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:20,885 INFO L470 AbstractCegarLoop]: Abstraction has 345 states and 387 transitions. [2021-12-21 18:09:20,886 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:20,886 INFO L276 IsEmpty]: Start isEmpty. Operand 345 states and 387 transitions. [2021-12-21 18:09:20,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-12-21 18:09:20,886 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:20,887 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:20,907 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (7)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:21,097 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:21,100 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr86ASSERT_VIOLATIONMEMORY_FREE === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:21,100 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:21,100 INFO L85 PathProgramCache]: Analyzing trace with hash -2106255897, now seen corresponding path program 1 times [2021-12-21 18:09:21,100 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:21,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1171892552] [2021-12-21 18:09:21,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:21,101 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:21,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:21,103 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:21,104 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Waiting until timeout for monitored process [2021-12-21 18:09:21,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:21,168 INFO L263 TraceCheckSpWp]: Trace formula consists of 54 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-21 18:09:21,170 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:21,201 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:21,201 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:21,248 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:21,248 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:21,248 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1171892552] [2021-12-21 18:09:21,249 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1171892552] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 18:09:21,249 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:21,249 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2021-12-21 18:09:21,249 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [596566366] [2021-12-21 18:09:21,249 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:21,249 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:21,263 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:21,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:21,264 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:21,264 INFO L87 Difference]: Start difference. First operand 345 states and 387 transitions. Second operand has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:21,316 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:21,318 INFO L93 Difference]: Finished difference Result 344 states and 386 transitions. [2021-12-21 18:09:21,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:09:21,328 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2021-12-21 18:09:21,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:21,336 INFO L225 Difference]: With dead ends: 344 [2021-12-21 18:09:21,336 INFO L226 Difference]: Without dead ends: 344 [2021-12-21 18:09:21,337 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:21,337 INFO L933 BasicCegarLoop]: 332 mSDtfsCounter, 256 mSDsluCounter, 728 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 269 SdHoareTripleChecker+Valid, 1060 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:21,337 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [269 Valid, 1060 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 18:09:21,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 344 states. [2021-12-21 18:09:21,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 344 to 344. [2021-12-21 18:09:21,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 344 states, 199 states have (on average 1.763819095477387) internal successors, (351), 319 states have internal predecessors, (351), 16 states have call successors, (16), 9 states have call predecessors, (16), 10 states have return successors, (19), 17 states have call predecessors, (19), 16 states have call successors, (19) [2021-12-21 18:09:21,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 344 states to 344 states and 386 transitions. [2021-12-21 18:09:21,343 INFO L78 Accepts]: Start accepts. Automaton has 344 states and 386 transitions. Word has length 17 [2021-12-21 18:09:21,343 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:21,344 INFO L470 AbstractCegarLoop]: Abstraction has 344 states and 386 transitions. [2021-12-21 18:09:21,344 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:21,344 INFO L276 IsEmpty]: Start isEmpty. Operand 344 states and 386 transitions. [2021-12-21 18:09:21,344 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-12-21 18:09:21,344 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:21,344 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:21,352 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Ended with exit code 0 [2021-12-21 18:09:21,549 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:21,549 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:21,549 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:21,549 INFO L85 PathProgramCache]: Analyzing trace with hash -2106256148, now seen corresponding path program 1 times [2021-12-21 18:09:21,550 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:21,550 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [413063324] [2021-12-21 18:09:21,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:21,550 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:21,550 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:21,551 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:21,551 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (9)] Waiting until timeout for monitored process [2021-12-21 18:09:21,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:21,606 INFO L263 TraceCheckSpWp]: Trace formula consists of 53 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 18:09:21,607 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:21,657 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:21,657 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:21,657 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:21,657 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [413063324] [2021-12-21 18:09:21,657 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [413063324] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:21,657 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:21,657 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 18:09:21,658 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [514707921] [2021-12-21 18:09:21,658 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:21,658 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:21,658 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:21,658 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:21,658 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:21,658 INFO L87 Difference]: Start difference. First operand 344 states and 386 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:21,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:21,704 INFO L93 Difference]: Finished difference Result 388 states and 436 transitions. [2021-12-21 18:09:21,705 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:09:21,705 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2021-12-21 18:09:21,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:21,708 INFO L225 Difference]: With dead ends: 388 [2021-12-21 18:09:21,708 INFO L226 Difference]: Without dead ends: 388 [2021-12-21 18:09:21,708 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:21,709 INFO L933 BasicCegarLoop]: 352 mSDtfsCounter, 40 mSDsluCounter, 1031 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 1383 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:21,709 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 1383 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 18:09:21,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 388 states. [2021-12-21 18:09:21,714 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 388 to 346. [2021-12-21 18:09:21,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 346 states, 201 states have (on average 1.756218905472637) internal successors, (353), 320 states have internal predecessors, (353), 16 states have call successors, (16), 9 states have call predecessors, (16), 10 states have return successors, (19), 18 states have call predecessors, (19), 16 states have call successors, (19) [2021-12-21 18:09:21,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 346 states to 346 states and 388 transitions. [2021-12-21 18:09:21,717 INFO L78 Accepts]: Start accepts. Automaton has 346 states and 388 transitions. Word has length 17 [2021-12-21 18:09:21,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:21,717 INFO L470 AbstractCegarLoop]: Abstraction has 346 states and 388 transitions. [2021-12-21 18:09:21,717 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:21,717 INFO L276 IsEmpty]: Start isEmpty. Operand 346 states and 388 transitions. [2021-12-21 18:09:21,720 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-12-21 18:09:21,720 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:21,720 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:21,738 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (9)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:21,927 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:21,929 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:21,929 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:21,929 INFO L85 PathProgramCache]: Analyzing trace with hash -2134885299, now seen corresponding path program 1 times [2021-12-21 18:09:21,930 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:21,930 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1232053250] [2021-12-21 18:09:21,930 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:21,930 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:21,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:21,931 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:21,931 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Waiting until timeout for monitored process [2021-12-21 18:09:21,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:21,992 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-21 18:09:21,994 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:22,012 INFO L387 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-21 18:09:22,146 INFO L353 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-12-21 18:09:22,146 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 24 [2021-12-21 18:09:22,158 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:22,158 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:24,399 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:24,399 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:24,399 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1232053250] [2021-12-21 18:09:24,399 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1232053250] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 18:09:24,400 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:24,400 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 7 [2021-12-21 18:09:24,400 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1995351510] [2021-12-21 18:09:24,400 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:24,400 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-21 18:09:24,400 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:24,401 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-21 18:09:24,401 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=40, Unknown=1, NotChecked=0, Total=56 [2021-12-21 18:09:24,401 INFO L87 Difference]: Start difference. First operand 346 states and 388 transitions. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 2 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-21 18:09:24,892 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:24,892 INFO L93 Difference]: Finished difference Result 353 states and 399 transitions. [2021-12-21 18:09:24,893 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 18:09:24,893 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 2 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 17 [2021-12-21 18:09:24,893 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:24,894 INFO L225 Difference]: With dead ends: 353 [2021-12-21 18:09:24,894 INFO L226 Difference]: Without dead ends: 353 [2021-12-21 18:09:24,894 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 23 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=20, Invalid=51, Unknown=1, NotChecked=0, Total=72 [2021-12-21 18:09:24,895 INFO L933 BasicCegarLoop]: 341 mSDtfsCounter, 20 mSDsluCounter, 842 mSDsCounter, 0 mSdLazyCounter, 416 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 1183 SdHoareTripleChecker+Invalid, 583 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 416 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 163 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:24,895 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 1183 Invalid, 583 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 416 Invalid, 0 Unknown, 163 Unchecked, 0.5s Time] [2021-12-21 18:09:24,896 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2021-12-21 18:09:24,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 350. [2021-12-21 18:09:24,900 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 350 states, 205 states have (on average 1.7414634146341463) internal successors, (357), 324 states have internal predecessors, (357), 16 states have call successors, (16), 9 states have call predecessors, (16), 11 states have return successors, (19), 18 states have call predecessors, (19), 16 states have call successors, (19) [2021-12-21 18:09:24,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 350 states to 350 states and 392 transitions. [2021-12-21 18:09:24,901 INFO L78 Accepts]: Start accepts. Automaton has 350 states and 392 transitions. Word has length 17 [2021-12-21 18:09:24,901 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:24,901 INFO L470 AbstractCegarLoop]: Abstraction has 350 states and 392 transitions. [2021-12-21 18:09:24,901 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 7 states have internal predecessors, (16), 2 states have call successors, (3), 3 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-21 18:09:24,901 INFO L276 IsEmpty]: Start isEmpty. Operand 350 states and 392 transitions. [2021-12-21 18:09:24,902 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2021-12-21 18:09:24,902 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:24,902 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:24,910 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:25,108 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:25,109 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:25,109 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:25,109 INFO L85 PathProgramCache]: Analyzing trace with hash -2134885298, now seen corresponding path program 1 times [2021-12-21 18:09:25,109 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:25,109 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1932680976] [2021-12-21 18:09:25,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:25,109 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:25,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:25,110 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:25,113 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (11)] Waiting until timeout for monitored process [2021-12-21 18:09:25,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:25,171 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjunts are in the unsatisfiable core [2021-12-21 18:09:25,173 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:25,192 INFO L387 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-21 18:09:25,197 INFO L387 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-21 18:09:27,370 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-21 18:09:27,371 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2021-12-21 18:09:27,378 INFO L353 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-21 18:09:27,379 INFO L387 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-21 18:09:27,405 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:27,405 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:27,609 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:27,609 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1932680976] [2021-12-21 18:09:27,609 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1932680976] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:09:27,609 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [891929582] [2021-12-21 18:09:27,610 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:27,610 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-21 18:09:27,610 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-21 18:09:27,611 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-21 18:09:27,612 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Waiting until timeout for monitored process [2021-12-21 18:09:27,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:27,728 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjunts are in the unsatisfiable core [2021-12-21 18:09:27,729 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:27,743 INFO L387 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-21 18:09:27,749 INFO L387 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-21 18:09:27,853 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-21 18:09:27,853 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2021-12-21 18:09:27,859 INFO L353 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-21 18:09:27,860 INFO L387 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-21 18:09:27,870 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:27,870 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:30,128 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [891929582] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:09:30,128 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:30,128 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2021-12-21 18:09:30,128 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [373281519] [2021-12-21 18:09:30,128 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:30,129 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2021-12-21 18:09:30,129 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:30,129 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-12-21 18:09:30,129 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=86, Unknown=1, NotChecked=0, Total=110 [2021-12-21 18:09:30,129 INFO L87 Difference]: Start difference. First operand 350 states and 392 transitions. Second operand has 9 states, 8 states have (on average 1.625) internal successors, (13), 8 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:35,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:35,117 INFO L93 Difference]: Finished difference Result 634 states and 720 transitions. [2021-12-21 18:09:35,117 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-21 18:09:35,117 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 1.625) internal successors, (13), 8 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 17 [2021-12-21 18:09:35,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:35,119 INFO L225 Difference]: With dead ends: 634 [2021-12-21 18:09:35,119 INFO L226 Difference]: Without dead ends: 634 [2021-12-21 18:09:35,120 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=32, Invalid=122, Unknown=2, NotChecked=0, Total=156 [2021-12-21 18:09:35,120 INFO L933 BasicCegarLoop]: 205 mSDtfsCounter, 328 mSDsluCounter, 1098 mSDsCounter, 0 mSdLazyCounter, 1390 mSolverCounterSat, 51 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 336 SdHoareTripleChecker+Valid, 1303 SdHoareTripleChecker+Invalid, 1762 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 51 IncrementalHoareTripleChecker+Valid, 1390 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 321 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:35,120 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [336 Valid, 1303 Invalid, 1762 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [51 Valid, 1390 Invalid, 0 Unknown, 321 Unchecked, 2.9s Time] [2021-12-21 18:09:35,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 634 states. [2021-12-21 18:09:35,126 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 634 to 364. [2021-12-21 18:09:35,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 364 states, 216 states have (on average 1.7222222222222223) internal successors, (372), 335 states have internal predecessors, (372), 18 states have call successors, (18), 9 states have call predecessors, (18), 13 states have return successors, (30), 21 states have call predecessors, (30), 18 states have call successors, (30) [2021-12-21 18:09:35,127 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 364 states to 364 states and 420 transitions. [2021-12-21 18:09:35,127 INFO L78 Accepts]: Start accepts. Automaton has 364 states and 420 transitions. Word has length 17 [2021-12-21 18:09:35,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:35,128 INFO L470 AbstractCegarLoop]: Abstraction has 364 states and 420 transitions. [2021-12-21 18:09:35,128 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 1.625) internal successors, (13), 8 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:35,128 INFO L276 IsEmpty]: Start isEmpty. Operand 364 states and 420 transitions. [2021-12-21 18:09:35,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2021-12-21 18:09:35,128 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:35,128 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:35,136 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (11)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:35,337 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:35,535 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3,12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2021-12-21 18:09:35,535 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr87ASSERT_VIOLATIONMEMORY_FREE === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:35,535 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:35,536 INFO L85 PathProgramCache]: Analyzing trace with hash -869422937, now seen corresponding path program 1 times [2021-12-21 18:09:35,536 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:35,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [218339429] [2021-12-21 18:09:35,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:35,536 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:35,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:35,537 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:35,539 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Waiting until timeout for monitored process [2021-12-21 18:09:35,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:35,593 INFO L263 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-21 18:09:35,594 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:35,750 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:35,750 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:35,845 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:35,845 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:35,845 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [218339429] [2021-12-21 18:09:35,845 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [218339429] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 18:09:35,845 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:35,845 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 9 [2021-12-21 18:09:35,845 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1338790238] [2021-12-21 18:09:35,845 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:35,846 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-21 18:09:35,846 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:35,846 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-21 18:09:35,846 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2021-12-21 18:09:35,846 INFO L87 Difference]: Start difference. First operand 364 states and 420 transitions. Second operand has 10 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-21 18:09:36,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:36,339 INFO L93 Difference]: Finished difference Result 367 states and 421 transitions. [2021-12-21 18:09:36,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-21 18:09:36,340 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 18 [2021-12-21 18:09:36,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:36,341 INFO L225 Difference]: With dead ends: 367 [2021-12-21 18:09:36,341 INFO L226 Difference]: Without dead ends: 367 [2021-12-21 18:09:36,342 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2021-12-21 18:09:36,342 INFO L933 BasicCegarLoop]: 306 mSDtfsCounter, 578 mSDsluCounter, 1026 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 592 SdHoareTripleChecker+Valid, 1332 SdHoareTripleChecker+Invalid, 368 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 27 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:36,342 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [592 Valid, 1332 Invalid, 368 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 319 Invalid, 0 Unknown, 27 Unchecked, 0.4s Time] [2021-12-21 18:09:36,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 367 states. [2021-12-21 18:09:36,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 367 to 363. [2021-12-21 18:09:36,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 363 states, 216 states have (on average 1.712962962962963) internal successors, (370), 334 states have internal predecessors, (370), 18 states have call successors, (18), 9 states have call predecessors, (18), 13 states have return successors, (30), 21 states have call predecessors, (30), 18 states have call successors, (30) [2021-12-21 18:09:36,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 418 transitions. [2021-12-21 18:09:36,348 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 418 transitions. Word has length 18 [2021-12-21 18:09:36,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:36,348 INFO L470 AbstractCegarLoop]: Abstraction has 363 states and 418 transitions. [2021-12-21 18:09:36,348 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-21 18:09:36,348 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 418 transitions. [2021-12-21 18:09:36,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2021-12-21 18:09:36,349 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:36,349 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:36,358 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (13)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:36,549 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:36,549 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr103ASSERT_VIOLATIONMEMORY_LEAK === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:36,550 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:36,550 INFO L85 PathProgramCache]: Analyzing trace with hash 1883109288, now seen corresponding path program 1 times [2021-12-21 18:09:36,550 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:36,550 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [475648882] [2021-12-21 18:09:36,550 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:36,550 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:36,550 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:36,552 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:36,553 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Waiting until timeout for monitored process [2021-12-21 18:09:36,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:36,611 INFO L263 TraceCheckSpWp]: Trace formula consists of 58 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-21 18:09:36,612 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:36,650 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:36,650 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:36,650 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:36,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [475648882] [2021-12-21 18:09:36,650 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [475648882] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:36,650 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:36,650 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 18:09:36,651 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [240651796] [2021-12-21 18:09:36,651 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:36,651 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 18:09:36,651 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:36,651 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 18:09:36,651 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 18:09:36,651 INFO L87 Difference]: Start difference. First operand 363 states and 418 transitions. Second operand has 4 states, 3 states have (on average 5.333333333333333) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:37,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:37,193 INFO L93 Difference]: Finished difference Result 366 states and 420 transitions. [2021-12-21 18:09:37,194 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 18:09:37,194 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 5.333333333333333) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 18 [2021-12-21 18:09:37,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:37,195 INFO L225 Difference]: With dead ends: 366 [2021-12-21 18:09:37,195 INFO L226 Difference]: Without dead ends: 353 [2021-12-21 18:09:37,196 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 18:09:37,196 INFO L933 BasicCegarLoop]: 320 mSDtfsCounter, 41 mSDsluCounter, 359 mSDsCounter, 0 mSdLazyCounter, 285 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 679 SdHoareTripleChecker+Invalid, 299 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 285 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:37,196 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 679 Invalid, 299 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 285 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-21 18:09:37,197 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2021-12-21 18:09:37,202 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 353. [2021-12-21 18:09:37,202 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 353 states, 207 states have (on average 1.7391304347826086) internal successors, (360), 325 states have internal predecessors, (360), 18 states have call successors, (18), 9 states have call predecessors, (18), 12 states have return successors, (29), 20 states have call predecessors, (29), 18 states have call successors, (29) [2021-12-21 18:09:37,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 353 states to 353 states and 407 transitions. [2021-12-21 18:09:37,204 INFO L78 Accepts]: Start accepts. Automaton has 353 states and 407 transitions. Word has length 18 [2021-12-21 18:09:37,204 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:37,204 INFO L470 AbstractCegarLoop]: Abstraction has 353 states and 407 transitions. [2021-12-21 18:09:37,204 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 5.333333333333333) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-21 18:09:37,204 INFO L276 IsEmpty]: Start isEmpty. Operand 353 states and 407 transitions. [2021-12-21 18:09:37,205 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2021-12-21 18:09:37,205 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:37,205 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:37,212 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Ended with exit code 0 [2021-12-21 18:09:37,411 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:37,412 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr89REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:37,412 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:37,412 INFO L85 PathProgramCache]: Analyzing trace with hash 1969475052, now seen corresponding path program 1 times [2021-12-21 18:09:37,412 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:37,413 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [964116519] [2021-12-21 18:09:37,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:37,413 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:37,413 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:37,414 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:37,415 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (15)] Waiting until timeout for monitored process [2021-12-21 18:09:37,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:37,471 INFO L263 TraceCheckSpWp]: Trace formula consists of 60 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-21 18:09:37,480 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:37,571 INFO L353 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-12-21 18:09:37,571 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 24 [2021-12-21 18:09:37,690 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2021-12-21 18:09:37,698 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:37,699 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:37,757 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:37,758 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [964116519] [2021-12-21 18:09:37,758 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [964116519] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:09:37,758 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [588233937] [2021-12-21 18:09:37,758 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:37,758 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-21 18:09:37,758 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-21 18:09:37,759 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-21 18:09:37,760 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (16)] Waiting until timeout for monitored process [2021-12-21 18:09:37,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:37,865 INFO L263 TraceCheckSpWp]: Trace formula consists of 60 conjuncts, 13 conjunts are in the unsatisfiable core [2021-12-21 18:09:37,866 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:37,874 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2021-12-21 18:09:37,954 INFO L353 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-12-21 18:09:37,954 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 24 [2021-12-21 18:09:38,052 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2021-12-21 18:09:38,065 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:38,065 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:38,124 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [588233937] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:09:38,124 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:38,133 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2021-12-21 18:09:38,133 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [196464162] [2021-12-21 18:09:38,133 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:38,133 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-21 18:09:38,134 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:38,134 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-21 18:09:38,134 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2021-12-21 18:09:38,134 INFO L87 Difference]: Start difference. First operand 353 states and 407 transitions. Second operand has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:38,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:38,649 INFO L93 Difference]: Finished difference Result 403 states and 459 transitions. [2021-12-21 18:09:38,650 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 18:09:38,650 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2021-12-21 18:09:38,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:38,651 INFO L225 Difference]: With dead ends: 403 [2021-12-21 18:09:38,651 INFO L226 Difference]: Without dead ends: 403 [2021-12-21 18:09:38,652 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 46 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2021-12-21 18:09:38,652 INFO L933 BasicCegarLoop]: 312 mSDtfsCounter, 99 mSDsluCounter, 624 mSDsCounter, 0 mSdLazyCounter, 345 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 936 SdHoareTripleChecker+Invalid, 539 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 345 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 185 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:38,652 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [99 Valid, 936 Invalid, 539 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 345 Invalid, 0 Unknown, 185 Unchecked, 0.5s Time] [2021-12-21 18:09:38,653 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 403 states. [2021-12-21 18:09:38,660 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 403 to 358. [2021-12-21 18:09:38,660 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 358 states, 212 states have (on average 1.7264150943396226) internal successors, (366), 330 states have internal predecessors, (366), 18 states have call successors, (18), 9 states have call predecessors, (18), 12 states have return successors, (29), 20 states have call predecessors, (29), 18 states have call successors, (29) [2021-12-21 18:09:38,661 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 358 states to 358 states and 413 transitions. [2021-12-21 18:09:38,661 INFO L78 Accepts]: Start accepts. Automaton has 358 states and 413 transitions. Word has length 21 [2021-12-21 18:09:38,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:38,662 INFO L470 AbstractCegarLoop]: Abstraction has 358 states and 413 transitions. [2021-12-21 18:09:38,662 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:38,662 INFO L276 IsEmpty]: Start isEmpty. Operand 358 states and 413 transitions. [2021-12-21 18:09:38,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2021-12-21 18:09:38,662 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:38,662 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:38,664 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (16)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:38,872 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (15)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:39,065 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:39,065 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr90REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:39,065 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:39,065 INFO L85 PathProgramCache]: Analyzing trace with hash 1969475053, now seen corresponding path program 1 times [2021-12-21 18:09:39,066 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:39,066 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1644502227] [2021-12-21 18:09:39,066 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:39,066 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:39,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:39,067 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:39,069 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (17)] Waiting until timeout for monitored process [2021-12-21 18:09:39,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:39,131 INFO L263 TraceCheckSpWp]: Trace formula consists of 60 conjuncts, 13 conjunts are in the unsatisfiable core [2021-12-21 18:09:39,132 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:41,279 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-21 18:09:41,280 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2021-12-21 18:09:43,417 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:43,417 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:43,732 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:43,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1644502227] [2021-12-21 18:09:43,732 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1644502227] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:09:43,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1168474636] [2021-12-21 18:09:43,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:43,733 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-21 18:09:43,733 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-21 18:09:43,734 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-21 18:09:43,734 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (18)] Waiting until timeout for monitored process [2021-12-21 18:09:43,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:43,826 INFO L263 TraceCheckSpWp]: Trace formula consists of 60 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-21 18:09:43,827 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:43,839 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2021-12-21 18:09:45,941 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-21 18:09:45,942 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2021-12-21 18:09:46,085 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-21 18:09:46,086 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:46,447 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1168474636] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:09:46,447 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:46,447 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2021-12-21 18:09:46,447 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1058804092] [2021-12-21 18:09:46,448 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:46,448 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-21 18:09:46,448 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:46,448 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-21 18:09:46,448 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=61, Unknown=2, NotChecked=0, Total=90 [2021-12-21 18:09:46,449 INFO L87 Difference]: Start difference. First operand 358 states and 413 transitions. Second operand has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:51,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:51,411 INFO L93 Difference]: Finished difference Result 449 states and 506 transitions. [2021-12-21 18:09:51,411 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-21 18:09:51,411 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 21 [2021-12-21 18:09:51,412 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:51,413 INFO L225 Difference]: With dead ends: 449 [2021-12-21 18:09:51,413 INFO L226 Difference]: Without dead ends: 449 [2021-12-21 18:09:51,416 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 59 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 10.4s TimeCoverageRelationStatistics Valid=60, Invalid=118, Unknown=4, NotChecked=0, Total=182 [2021-12-21 18:09:51,416 INFO L933 BasicCegarLoop]: 310 mSDtfsCounter, 151 mSDsluCounter, 785 mSDsCounter, 0 mSdLazyCounter, 499 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 153 SdHoareTripleChecker+Valid, 1095 SdHoareTripleChecker+Invalid, 719 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 499 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 205 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:51,417 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [153 Valid, 1095 Invalid, 719 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 499 Invalid, 0 Unknown, 205 Unchecked, 0.9s Time] [2021-12-21 18:09:51,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 449 states. [2021-12-21 18:09:51,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 449 to 384. [2021-12-21 18:09:51,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 384 states, 236 states have (on average 1.7415254237288136) internal successors, (411), 354 states have internal predecessors, (411), 19 states have call successors, (19), 10 states have call predecessors, (19), 13 states have return successors, (30), 21 states have call predecessors, (30), 19 states have call successors, (30) [2021-12-21 18:09:51,429 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 384 states to 384 states and 460 transitions. [2021-12-21 18:09:51,430 INFO L78 Accepts]: Start accepts. Automaton has 384 states and 460 transitions. Word has length 21 [2021-12-21 18:09:51,431 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:51,431 INFO L470 AbstractCegarLoop]: Abstraction has 384 states and 460 transitions. [2021-12-21 18:09:51,431 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 6 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-21 18:09:51,432 INFO L276 IsEmpty]: Start isEmpty. Operand 384 states and 460 transitions. [2021-12-21 18:09:51,433 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2021-12-21 18:09:51,433 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:51,433 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:51,449 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (17)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:51,640 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (18)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:51,838 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3,18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2021-12-21 18:09:51,838 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr89REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:51,838 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:51,839 INFO L85 PathProgramCache]: Analyzing trace with hash -2128978739, now seen corresponding path program 1 times [2021-12-21 18:09:51,839 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:51,839 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1776768076] [2021-12-21 18:09:51,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:51,839 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:51,839 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:51,840 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:51,841 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (19)] Waiting until timeout for monitored process [2021-12-21 18:09:51,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:51,903 INFO L263 TraceCheckSpWp]: Trace formula consists of 66 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-21 18:09:51,903 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:51,945 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:51,946 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:51,946 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:51,946 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1776768076] [2021-12-21 18:09:51,946 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1776768076] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:51,946 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:51,946 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 18:09:51,949 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [404688485] [2021-12-21 18:09:51,949 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:51,949 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:51,949 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:51,950 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:51,950 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:51,950 INFO L87 Difference]: Start difference. First operand 384 states and 460 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:51,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:51,985 INFO L93 Difference]: Finished difference Result 397 states and 459 transitions. [2021-12-21 18:09:51,986 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:09:51,986 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2021-12-21 18:09:51,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:51,987 INFO L225 Difference]: With dead ends: 397 [2021-12-21 18:09:51,987 INFO L226 Difference]: Without dead ends: 397 [2021-12-21 18:09:51,987 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:51,988 INFO L933 BasicCegarLoop]: 375 mSDtfsCounter, 252 mSDsluCounter, 855 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 265 SdHoareTripleChecker+Valid, 1230 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:51,988 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [265 Valid, 1230 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 18:09:51,989 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 397 states. [2021-12-21 18:09:51,992 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 397 to 381. [2021-12-21 18:09:51,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 381 states, 233 states have (on average 1.7467811158798283) internal successors, (407), 351 states have internal predecessors, (407), 19 states have call successors, (19), 10 states have call predecessors, (19), 13 states have return successors, (30), 21 states have call predecessors, (30), 19 states have call successors, (30) [2021-12-21 18:09:51,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 381 states to 381 states and 456 transitions. [2021-12-21 18:09:51,994 INFO L78 Accepts]: Start accepts. Automaton has 381 states and 456 transitions. Word has length 21 [2021-12-21 18:09:51,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:51,994 INFO L470 AbstractCegarLoop]: Abstraction has 381 states and 456 transitions. [2021-12-21 18:09:51,994 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (2), 1 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:51,994 INFO L276 IsEmpty]: Start isEmpty. Operand 381 states and 456 transitions. [2021-12-21 18:09:51,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2021-12-21 18:09:51,994 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:51,995 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:52,003 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (19)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:52,201 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:52,201 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr91REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:52,201 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:52,201 INFO L85 PathProgramCache]: Analyzing trace with hash -1415040467, now seen corresponding path program 1 times [2021-12-21 18:09:52,201 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:52,201 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1100184190] [2021-12-21 18:09:52,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:52,202 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:52,202 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:52,202 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:52,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (20)] Waiting until timeout for monitored process [2021-12-21 18:09:52,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:52,265 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-21 18:09:52,266 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:52,313 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:09:52,326 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-21 18:09:52,326 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:52,326 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:52,327 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1100184190] [2021-12-21 18:09:52,327 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1100184190] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:52,327 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:52,327 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 18:09:52,327 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1095619818] [2021-12-21 18:09:52,327 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:52,327 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:52,327 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:52,327 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:52,327 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:52,328 INFO L87 Difference]: Start difference. First operand 381 states and 456 transitions. Second operand has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:52,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:52,997 INFO L93 Difference]: Finished difference Result 422 states and 500 transitions. [2021-12-21 18:09:52,998 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-21 18:09:52,999 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2021-12-21 18:09:52,999 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:53,000 INFO L225 Difference]: With dead ends: 422 [2021-12-21 18:09:53,000 INFO L226 Difference]: Without dead ends: 422 [2021-12-21 18:09:53,001 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-12-21 18:09:53,001 INFO L933 BasicCegarLoop]: 325 mSDtfsCounter, 57 mSDsluCounter, 709 mSDsCounter, 0 mSdLazyCounter, 317 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 1034 SdHoareTripleChecker+Invalid, 320 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 317 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:53,001 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [57 Valid, 1034 Invalid, 320 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 317 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2021-12-21 18:09:53,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 422 states. [2021-12-21 18:09:53,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 422 to 381. [2021-12-21 18:09:53,009 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 381 states, 233 states have (on average 1.742489270386266) internal successors, (406), 351 states have internal predecessors, (406), 19 states have call successors, (19), 10 states have call predecessors, (19), 13 states have return successors, (30), 21 states have call predecessors, (30), 19 states have call successors, (30) [2021-12-21 18:09:53,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 381 states to 381 states and 455 transitions. [2021-12-21 18:09:53,010 INFO L78 Accepts]: Start accepts. Automaton has 381 states and 455 transitions. Word has length 23 [2021-12-21 18:09:53,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:53,010 INFO L470 AbstractCegarLoop]: Abstraction has 381 states and 455 transitions. [2021-12-21 18:09:53,010 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:53,010 INFO L276 IsEmpty]: Start isEmpty. Operand 381 states and 455 transitions. [2021-12-21 18:09:53,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2021-12-21 18:09:53,011 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:53,011 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:53,035 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (20)] Ended with exit code 0 [2021-12-21 18:09:53,220 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:53,220 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr92REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:53,221 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:53,221 INFO L85 PathProgramCache]: Analyzing trace with hash -1415040466, now seen corresponding path program 1 times [2021-12-21 18:09:53,221 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:53,221 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [27339665] [2021-12-21 18:09:53,221 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:53,221 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:53,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:53,223 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:53,282 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (21)] Waiting until timeout for monitored process [2021-12-21 18:09:53,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:53,346 INFO L263 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-21 18:09:53,347 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:53,576 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:09:53,582 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:09:53,623 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-21 18:09:53,623 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:53,623 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:53,624 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [27339665] [2021-12-21 18:09:53,624 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [27339665] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:53,624 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:53,624 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 18:09:53,624 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1644712692] [2021-12-21 18:09:53,624 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:53,624 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:53,625 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:53,625 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:53,625 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:53,625 INFO L87 Difference]: Start difference. First operand 381 states and 455 transitions. Second operand has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:54,639 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:54,639 INFO L93 Difference]: Finished difference Result 403 states and 477 transitions. [2021-12-21 18:09:54,640 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-21 18:09:54,641 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 23 [2021-12-21 18:09:54,641 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:54,642 INFO L225 Difference]: With dead ends: 403 [2021-12-21 18:09:54,642 INFO L226 Difference]: Without dead ends: 403 [2021-12-21 18:09:54,643 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-12-21 18:09:54,644 INFO L933 BasicCegarLoop]: 327 mSDtfsCounter, 39 mSDsluCounter, 758 mSDsCounter, 0 mSdLazyCounter, 267 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 1085 SdHoareTripleChecker+Invalid, 269 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 267 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:54,644 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 1085 Invalid, 269 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 267 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2021-12-21 18:09:54,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 403 states. [2021-12-21 18:09:54,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 403 to 381. [2021-12-21 18:09:54,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 381 states, 233 states have (on average 1.738197424892704) internal successors, (405), 351 states have internal predecessors, (405), 19 states have call successors, (19), 10 states have call predecessors, (19), 13 states have return successors, (30), 21 states have call predecessors, (30), 19 states have call successors, (30) [2021-12-21 18:09:54,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 381 states to 381 states and 454 transitions. [2021-12-21 18:09:54,653 INFO L78 Accepts]: Start accepts. Automaton has 381 states and 454 transitions. Word has length 23 [2021-12-21 18:09:54,653 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:54,653 INFO L470 AbstractCegarLoop]: Abstraction has 381 states and 454 transitions. [2021-12-21 18:09:54,653 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:09:54,653 INFO L276 IsEmpty]: Start isEmpty. Operand 381 states and 454 transitions. [2021-12-21 18:09:54,654 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-21 18:09:54,654 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:54,654 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:54,675 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (21)] Ended with exit code 0 [2021-12-21 18:09:54,863 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:54,864 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr83ASSERT_VIOLATIONMEMORY_FREE === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:54,864 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:54,865 INFO L85 PathProgramCache]: Analyzing trace with hash -412937067, now seen corresponding path program 1 times [2021-12-21 18:09:54,865 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:54,865 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1848261355] [2021-12-21 18:09:54,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:54,865 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:54,866 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:54,867 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:54,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (22)] Waiting until timeout for monitored process [2021-12-21 18:09:54,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:54,949 INFO L263 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-21 18:09:54,951 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:55,005 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-21 18:09:55,006 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:55,056 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-21 18:09:55,057 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:55,057 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1848261355] [2021-12-21 18:09:55,057 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1848261355] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 18:09:55,057 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:55,057 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2021-12-21 18:09:55,057 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1761579714] [2021-12-21 18:09:55,057 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:55,057 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:55,058 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:55,058 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:55,058 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:55,058 INFO L87 Difference]: Start difference. First operand 381 states and 454 transitions. Second operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-21 18:09:55,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:55,092 INFO L93 Difference]: Finished difference Result 380 states and 453 transitions. [2021-12-21 18:09:55,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:09:55,095 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 25 [2021-12-21 18:09:55,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:55,096 INFO L225 Difference]: With dead ends: 380 [2021-12-21 18:09:55,096 INFO L226 Difference]: Without dead ends: 380 [2021-12-21 18:09:55,096 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:55,097 INFO L933 BasicCegarLoop]: 332 mSDtfsCounter, 248 mSDsluCounter, 731 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 260 SdHoareTripleChecker+Valid, 1063 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:55,097 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [260 Valid, 1063 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 18:09:55,098 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 380 states. [2021-12-21 18:09:55,103 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 380 to 380. [2021-12-21 18:09:55,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 380 states, 233 states have (on average 1.7339055793991416) internal successors, (404), 350 states have internal predecessors, (404), 19 states have call successors, (19), 10 states have call predecessors, (19), 13 states have return successors, (30), 21 states have call predecessors, (30), 19 states have call successors, (30) [2021-12-21 18:09:55,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 380 states to 380 states and 453 transitions. [2021-12-21 18:09:55,105 INFO L78 Accepts]: Start accepts. Automaton has 380 states and 453 transitions. Word has length 25 [2021-12-21 18:09:55,105 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:55,105 INFO L470 AbstractCegarLoop]: Abstraction has 380 states and 453 transitions. [2021-12-21 18:09:55,105 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-21 18:09:55,105 INFO L276 IsEmpty]: Start isEmpty. Operand 380 states and 453 transitions. [2021-12-21 18:09:55,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-21 18:09:55,105 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:55,105 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:55,125 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (22)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:55,314 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:55,314 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:55,315 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:55,315 INFO L85 PathProgramCache]: Analyzing trace with hash -412937301, now seen corresponding path program 1 times [2021-12-21 18:09:55,315 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:55,315 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1610018300] [2021-12-21 18:09:55,315 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:55,316 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:55,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:55,317 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:55,322 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (23)] Waiting until timeout for monitored process [2021-12-21 18:09:55,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:55,395 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 18:09:55,396 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:55,471 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-21 18:09:55,472 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:09:55,472 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:55,472 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1610018300] [2021-12-21 18:09:55,472 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1610018300] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:09:55,473 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:09:55,473 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 18:09:55,473 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [900751940] [2021-12-21 18:09:55,473 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:09:55,473 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:09:55,473 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:55,473 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:09:55,474 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:55,474 INFO L87 Difference]: Start difference. First operand 380 states and 453 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-21 18:09:55,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:55,507 INFO L93 Difference]: Finished difference Result 415 states and 481 transitions. [2021-12-21 18:09:55,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:09:55,508 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 25 [2021-12-21 18:09:55,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:55,509 INFO L225 Difference]: With dead ends: 415 [2021-12-21 18:09:55,509 INFO L226 Difference]: Without dead ends: 415 [2021-12-21 18:09:55,509 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:09:55,510 INFO L933 BasicCegarLoop]: 373 mSDtfsCounter, 44 mSDsluCounter, 1072 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 1445 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:55,510 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [45 Valid, 1445 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 18:09:55,511 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 415 states. [2021-12-21 18:09:55,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 415 to 371. [2021-12-21 18:09:55,516 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 371 states, 226 states have (on average 1.7345132743362832) internal successors, (392), 343 states have internal predecessors, (392), 17 states have call successors, (17), 10 states have call predecessors, (17), 13 states have return successors, (26), 19 states have call predecessors, (26), 17 states have call successors, (26) [2021-12-21 18:09:55,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 371 states to 371 states and 435 transitions. [2021-12-21 18:09:55,517 INFO L78 Accepts]: Start accepts. Automaton has 371 states and 435 transitions. Word has length 25 [2021-12-21 18:09:55,517 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:55,517 INFO L470 AbstractCegarLoop]: Abstraction has 371 states and 435 transitions. [2021-12-21 18:09:55,517 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 1 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-21 18:09:55,518 INFO L276 IsEmpty]: Start isEmpty. Operand 371 states and 435 transitions. [2021-12-21 18:09:55,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-21 18:09:55,518 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:55,518 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:55,539 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (23)] Ended with exit code 0 [2021-12-21 18:09:55,726 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:55,727 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:55,727 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:55,727 INFO L85 PathProgramCache]: Analyzing trace with hash -441566452, now seen corresponding path program 1 times [2021-12-21 18:09:55,727 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:55,727 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [155395507] [2021-12-21 18:09:55,728 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:55,728 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:55,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:55,729 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:55,729 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (24)] Waiting until timeout for monitored process [2021-12-21 18:09:55,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:55,818 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-21 18:09:55,819 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:55,840 INFO L387 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-21 18:09:55,925 INFO L353 Elim1Store]: treesize reduction 12, result has 40.0 percent of original size [2021-12-21 18:09:55,925 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 17 [2021-12-21 18:09:55,942 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:55,942 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:09:56,137 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:09:56,138 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:09:56,138 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [155395507] [2021-12-21 18:09:56,138 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [155395507] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 18:09:56,138 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:09:56,138 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 7 [2021-12-21 18:09:56,138 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1845747786] [2021-12-21 18:09:56,138 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:09:56,138 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-21 18:09:56,139 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:09:56,139 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-21 18:09:56,139 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2021-12-21 18:09:56,139 INFO L87 Difference]: Start difference. First operand 371 states and 435 transitions. Second operand has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 18:09:57,465 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:09:57,465 INFO L93 Difference]: Finished difference Result 515 states and 605 transitions. [2021-12-21 18:09:57,466 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-21 18:09:57,466 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 25 [2021-12-21 18:09:57,466 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:09:57,468 INFO L225 Difference]: With dead ends: 515 [2021-12-21 18:09:57,468 INFO L226 Difference]: Without dead ends: 515 [2021-12-21 18:09:57,468 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 39 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2021-12-21 18:09:57,478 INFO L933 BasicCegarLoop]: 268 mSDtfsCounter, 182 mSDsluCounter, 1036 mSDsCounter, 0 mSdLazyCounter, 733 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 187 SdHoareTripleChecker+Valid, 1304 SdHoareTripleChecker+Invalid, 990 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 733 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 223 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2021-12-21 18:09:57,479 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [187 Valid, 1304 Invalid, 990 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 733 Invalid, 0 Unknown, 223 Unchecked, 1.3s Time] [2021-12-21 18:09:57,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 515 states. [2021-12-21 18:09:57,504 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 515 to 373. [2021-12-21 18:09:57,505 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 373 states, 229 states have (on average 1.724890829694323) internal successors, (395), 345 states have internal predecessors, (395), 17 states have call successors, (17), 10 states have call predecessors, (17), 13 states have return successors, (26), 19 states have call predecessors, (26), 17 states have call successors, (26) [2021-12-21 18:09:57,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 373 states to 373 states and 438 transitions. [2021-12-21 18:09:57,506 INFO L78 Accepts]: Start accepts. Automaton has 373 states and 438 transitions. Word has length 25 [2021-12-21 18:09:57,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:09:57,506 INFO L470 AbstractCegarLoop]: Abstraction has 373 states and 438 transitions. [2021-12-21 18:09:57,506 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 18:09:57,506 INFO L276 IsEmpty]: Start isEmpty. Operand 373 states and 438 transitions. [2021-12-21 18:09:57,507 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-21 18:09:57,507 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:09:57,507 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:09:57,525 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (24)] Forceful destruction successful, exit code 0 [2021-12-21 18:09:57,725 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 24 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:09:57,725 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:09:57,726 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:09:57,726 INFO L85 PathProgramCache]: Analyzing trace with hash -441566451, now seen corresponding path program 1 times [2021-12-21 18:09:57,726 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:09:57,726 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1015620514] [2021-12-21 18:09:57,726 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:09:57,726 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:09:57,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:09:57,728 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:09:57,729 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (25)] Waiting until timeout for monitored process [2021-12-21 18:09:57,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:09:57,816 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-21 18:09:57,817 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:09:57,853 INFO L387 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-21 18:10:02,060 INFO L353 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-21 18:10:02,060 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 14 [2021-12-21 18:10:02,097 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 9 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-21 18:10:02,098 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:10:02,417 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:10:02,417 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1015620514] [2021-12-21 18:10:02,417 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1015620514] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:10:02,417 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1317087428] [2021-12-21 18:10:02,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:10:02,417 INFO L168 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2021-12-21 18:10:02,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2021-12-21 18:10:02,418 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2021-12-21 18:10:02,419 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (26)] Waiting until timeout for monitored process [2021-12-21 18:10:02,569 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:10:02,572 INFO L263 TraceCheckSpWp]: Trace formula consists of 93 conjuncts, 18 conjunts are in the unsatisfiable core [2021-12-21 18:10:02,573 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:10:02,602 INFO L387 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-21 18:10:02,611 INFO L387 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-21 18:10:08,936 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-21 18:10:08,937 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 14 [2021-12-21 18:10:08,947 INFO L353 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-21 18:10:08,948 INFO L387 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-21 18:10:08,965 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-21 18:10:08,965 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:10:09,282 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1317087428] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 18:10:09,283 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:10:09,283 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2021-12-21 18:10:09,283 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [551840719] [2021-12-21 18:10:09,283 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:10:09,284 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-21 18:10:09,284 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:10:09,284 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-21 18:10:09,284 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=225, Unknown=4, NotChecked=0, Total=272 [2021-12-21 18:10:09,285 INFO L87 Difference]: Start difference. First operand 373 states and 438 transitions. Second operand has 14 states, 13 states have (on average 2.076923076923077) internal successors, (27), 11 states have internal predecessors, (27), 3 states have call successors, (4), 3 states have call predecessors, (4), 5 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-21 18:10:14,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:10:14,947 INFO L93 Difference]: Finished difference Result 645 states and 746 transitions. [2021-12-21 18:10:14,948 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-21 18:10:14,948 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.076923076923077) internal successors, (27), 11 states have internal predecessors, (27), 3 states have call successors, (4), 3 states have call predecessors, (4), 5 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) Word has length 25 [2021-12-21 18:10:14,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:10:14,950 INFO L225 Difference]: With dead ends: 645 [2021-12-21 18:10:14,950 INFO L226 Difference]: Without dead ends: 645 [2021-12-21 18:10:14,950 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 41 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 12.9s TimeCoverageRelationStatistics Valid=56, Invalid=281, Unknown=5, NotChecked=0, Total=342 [2021-12-21 18:10:14,951 INFO L933 BasicCegarLoop]: 345 mSDtfsCounter, 507 mSDsluCounter, 1937 mSDsCounter, 0 mSdLazyCounter, 1691 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 515 SdHoareTripleChecker+Valid, 2282 SdHoareTripleChecker+Invalid, 2306 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 1691 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 547 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2021-12-21 18:10:14,951 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [515 Valid, 2282 Invalid, 2306 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 1691 Invalid, 0 Unknown, 547 Unchecked, 3.5s Time] [2021-12-21 18:10:14,952 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 645 states. [2021-12-21 18:10:14,957 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 645 to 372. [2021-12-21 18:10:14,957 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 372 states, 229 states have (on average 1.720524017467249) internal successors, (394), 344 states have internal predecessors, (394), 17 states have call successors, (17), 10 states have call predecessors, (17), 13 states have return successors, (26), 19 states have call predecessors, (26), 17 states have call successors, (26) [2021-12-21 18:10:14,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 372 states to 372 states and 437 transitions. [2021-12-21 18:10:14,958 INFO L78 Accepts]: Start accepts. Automaton has 372 states and 437 transitions. Word has length 25 [2021-12-21 18:10:14,959 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:10:14,959 INFO L470 AbstractCegarLoop]: Abstraction has 372 states and 437 transitions. [2021-12-21 18:10:14,959 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.076923076923077) internal successors, (27), 11 states have internal predecessors, (27), 3 states have call successors, (4), 3 states have call predecessors, (4), 5 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2021-12-21 18:10:14,959 INFO L276 IsEmpty]: Start isEmpty. Operand 372 states and 437 transitions. [2021-12-21 18:10:14,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2021-12-21 18:10:14,960 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:10:14,960 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:10:14,974 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (25)] Forceful destruction successful, exit code 0 [2021-12-21 18:10:15,172 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (26)] Ended with exit code 0 [2021-12-21 18:10:15,369 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 25 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3,26 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2021-12-21 18:10:15,370 INFO L402 AbstractCegarLoop]: === Iteration 22 === Targeting ULTIMATE.startErr84ASSERT_VIOLATIONMEMORY_FREE === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:10:15,370 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:10:15,370 INFO L85 PathProgramCache]: Analyzing trace with hash 83853234, now seen corresponding path program 1 times [2021-12-21 18:10:15,370 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:10:15,370 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1167353042] [2021-12-21 18:10:15,370 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:10:15,371 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:10:15,371 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:10:15,372 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:10:15,373 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (27)] Waiting until timeout for monitored process [2021-12-21 18:10:15,443 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:10:15,445 INFO L263 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 18:10:15,446 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:10:15,696 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-21 18:10:15,697 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 18:10:15,795 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-21 18:10:15,795 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:10:15,796 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1167353042] [2021-12-21 18:10:15,796 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1167353042] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 18:10:15,796 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 18:10:15,796 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 9 [2021-12-21 18:10:15,796 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1513082355] [2021-12-21 18:10:15,796 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 18:10:15,796 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-21 18:10:15,796 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:10:15,796 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-21 18:10:15,797 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2021-12-21 18:10:15,797 INFO L87 Difference]: Start difference. First operand 372 states and 437 transitions. Second operand has 10 states, 9 states have (on average 3.888888888888889) internal successors, (35), 8 states have internal predecessors, (35), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-21 18:10:15,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:10:15,963 INFO L93 Difference]: Finished difference Result 606 states and 700 transitions. [2021-12-21 18:10:15,964 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-21 18:10:15,964 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 3.888888888888889) internal successors, (35), 8 states have internal predecessors, (35), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 26 [2021-12-21 18:10:15,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:10:15,966 INFO L225 Difference]: With dead ends: 606 [2021-12-21 18:10:15,966 INFO L226 Difference]: Without dead ends: 606 [2021-12-21 18:10:15,967 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 42 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2021-12-21 18:10:15,967 INFO L933 BasicCegarLoop]: 346 mSDtfsCounter, 324 mSDsluCounter, 1954 mSDsCounter, 0 mSdLazyCounter, 139 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 325 SdHoareTripleChecker+Valid, 2300 SdHoareTripleChecker+Invalid, 359 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 139 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 207 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-21 18:10:15,967 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [325 Valid, 2300 Invalid, 359 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 139 Invalid, 0 Unknown, 207 Unchecked, 0.2s Time] [2021-12-21 18:10:15,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 606 states. [2021-12-21 18:10:15,974 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 606 to 473. [2021-12-21 18:10:15,974 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 473 states, 316 states have (on average 1.7563291139240507) internal successors, (555), 431 states have internal predecessors, (555), 27 states have call successors, (27), 16 states have call predecessors, (27), 20 states have return successors, (41), 29 states have call predecessors, (41), 27 states have call successors, (41) [2021-12-21 18:10:15,976 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 473 states to 473 states and 623 transitions. [2021-12-21 18:10:15,976 INFO L78 Accepts]: Start accepts. Automaton has 473 states and 623 transitions. Word has length 26 [2021-12-21 18:10:15,976 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:10:15,976 INFO L470 AbstractCegarLoop]: Abstraction has 473 states and 623 transitions. [2021-12-21 18:10:15,976 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 3.888888888888889) internal successors, (35), 8 states have internal predecessors, (35), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-21 18:10:15,976 INFO L276 IsEmpty]: Start isEmpty. Operand 473 states and 623 transitions. [2021-12-21 18:10:15,977 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2021-12-21 18:10:15,977 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:10:15,977 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 18:10:15,999 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (27)] Ended with exit code 0 [2021-12-21 18:10:16,185 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 27 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:10:16,185 INFO L402 AbstractCegarLoop]: === Iteration 23 === Targeting ULTIMATE.startErr93REQUIRES_VIOLATION === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:10:16,185 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:10:16,185 INFO L85 PathProgramCache]: Analyzing trace with hash -366162574, now seen corresponding path program 1 times [2021-12-21 18:10:16,186 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:10:16,186 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1353657450] [2021-12-21 18:10:16,186 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:10:16,186 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:10:16,186 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:10:16,187 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:10:16,189 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (28)] Waiting until timeout for monitored process [2021-12-21 18:10:16,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:10:16,270 INFO L263 TraceCheckSpWp]: Trace formula consists of 85 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-21 18:10:16,271 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:10:16,500 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:10:16,504 INFO L387 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2021-12-21 18:10:16,565 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-21 18:10:16,565 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 18:10:16,565 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-21 18:10:16,565 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1353657450] [2021-12-21 18:10:16,566 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1353657450] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 18:10:16,567 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 18:10:16,567 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-21 18:10:16,567 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2135104012] [2021-12-21 18:10:16,567 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 18:10:16,567 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 18:10:16,567 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-21 18:10:16,567 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 18:10:16,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 18:10:16,568 INFO L87 Difference]: Start difference. First operand 473 states and 623 transitions. Second operand has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:10:16,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 18:10:16,921 INFO L93 Difference]: Finished difference Result 455 states and 584 transitions. [2021-12-21 18:10:16,921 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 18:10:16,922 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 26 [2021-12-21 18:10:16,922 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 18:10:16,924 INFO L225 Difference]: With dead ends: 455 [2021-12-21 18:10:16,924 INFO L226 Difference]: Without dead ends: 455 [2021-12-21 18:10:16,924 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-12-21 18:10:16,925 INFO L933 BasicCegarLoop]: 332 mSDtfsCounter, 12 mSDsluCounter, 918 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 1250 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-21 18:10:16,925 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 1250 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-21 18:10:16,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 455 states. [2021-12-21 18:10:16,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 455 to 451. [2021-12-21 18:10:16,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 451 states, 296 states have (on average 1.739864864864865) internal successors, (515), 411 states have internal predecessors, (515), 26 states have call successors, (26), 15 states have call predecessors, (26), 19 states have return successors, (40), 28 states have call predecessors, (40), 26 states have call successors, (40) [2021-12-21 18:10:16,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 451 states to 451 states and 581 transitions. [2021-12-21 18:10:16,940 INFO L78 Accepts]: Start accepts. Automaton has 451 states and 581 transitions. Word has length 26 [2021-12-21 18:10:16,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 18:10:16,941 INFO L470 AbstractCegarLoop]: Abstraction has 451 states and 581 transitions. [2021-12-21 18:10:16,941 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 1 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-21 18:10:16,941 INFO L276 IsEmpty]: Start isEmpty. Operand 451 states and 581 transitions. [2021-12-21 18:10:16,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2021-12-21 18:10:16,941 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 18:10:16,941 INFO L514 BasicCegarLoop]: trace histogram [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] [2021-12-21 18:10:16,967 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (28)] Forceful destruction successful, exit code 0 [2021-12-21 18:10:17,150 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 28 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-21 18:10:17,150 INFO L402 AbstractCegarLoop]: === Iteration 24 === Targeting ULTIMATE.startErr103ASSERT_VIOLATIONMEMORY_LEAK === [ldv_msg_freeErr0REQUIRES_VIOLATION, ldv_msg_freeErr1REQUIRES_VIOLATION, ldv_msg_freeErr2ASSERT_VIOLATIONMEMORY_FREE, ldv_msg_freeErr3ASSERT_VIOLATIONMEMORY_FREE (and 120 more)] === [2021-12-21 18:10:17,150 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 18:10:17,151 INFO L85 PathProgramCache]: Analyzing trace with hash 305064464, now seen corresponding path program 1 times [2021-12-21 18:10:17,151 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-21 18:10:17,151 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1191718948] [2021-12-21 18:10:17,151 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 18:10:17,152 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-21 18:10:17,152 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-21 18:10:17,153 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-21 18:10:17,155 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (29)] Waiting until timeout for monitored process [2021-12-21 18:10:17,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 18:10:17,238 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-21 18:10:17,245 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 18:10:17,415 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-21 18:10:17,415 INFO L328 TraceCheckSpWp]: Computing backward predicates...