./Ultimate.py --spec ../sv-benchmarks/c/properties/valid-memsafety.prp --file ../sv-benchmarks/c/memsafety/20020406-1.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version c3fed411 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerMemDerefMemtrack.xml -i ../sv-benchmarks/c/memsafety/20020406-1.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 1ecdf6fdf9ec72145fabb79894bcc278b3e5646bc4893dbabc4bb180fa53c5ae --- Real Ultimate output --- This is Ultimate 0.2.2-tmp.no-commuhash-c3fed41 [2021-12-16 05:49:38,681 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-16 05:49:38,683 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-16 05:49:38,735 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-16 05:49:38,736 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-16 05:49:38,737 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-16 05:49:38,738 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-16 05:49:38,739 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-16 05:49:38,740 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-16 05:49:38,741 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-16 05:49:38,742 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-16 05:49:38,742 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-16 05:49:38,743 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-16 05:49:38,743 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-16 05:49:38,744 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-16 05:49:38,745 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-16 05:49:38,746 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-16 05:49:38,746 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-16 05:49:38,747 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-16 05:49:38,749 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-16 05:49:38,749 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-16 05:49:38,750 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-16 05:49:38,751 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-16 05:49:38,767 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-16 05:49:38,770 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-16 05:49:38,777 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-16 05:49:38,778 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-16 05:49:38,778 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-16 05:49:38,780 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-16 05:49:38,781 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-16 05:49:38,781 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-16 05:49:38,782 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-16 05:49:38,783 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-16 05:49:38,784 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-16 05:49:38,785 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-16 05:49:38,787 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-16 05:49:38,788 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-16 05:49:38,789 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-16 05:49:38,789 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-16 05:49:38,790 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-16 05:49:38,791 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-16 05:49:38,791 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-32bit-Automizer_Default.epf [2021-12-16 05:49:38,818 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-16 05:49:38,818 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-16 05:49:38,818 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-16 05:49:38,818 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-16 05:49:38,819 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-16 05:49:38,819 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-16 05:49:38,819 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * Use SBE=true [2021-12-16 05:49:38,820 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2021-12-16 05:49:38,820 INFO L138 SettingsManager]: * Bitprecise bitfields=true [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-16 05:49:38,821 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-16 05:49:38,821 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-16 05:49:38,822 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-16 05:49:38,822 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-16 05:49:38,822 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-16 05:49:38,822 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-16 05:49:38,822 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-16 05:49:38,822 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 -> 1ecdf6fdf9ec72145fabb79894bcc278b3e5646bc4893dbabc4bb180fa53c5ae [2021-12-16 05:49:38,994 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-16 05:49:39,018 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-16 05:49:39,021 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-16 05:49:39,023 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-16 05:49:39,027 INFO L275 PluginConnector]: CDTParser initialized [2021-12-16 05:49:39,029 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/memsafety/20020406-1.i [2021-12-16 05:49:39,093 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/346bb75ad/55c3d4776a6e4584a0d3e29a3b731b63/FLAG002a585cc [2021-12-16 05:49:39,558 INFO L306 CDTParser]: Found 1 translation units. [2021-12-16 05:49:39,558 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/memsafety/20020406-1.i [2021-12-16 05:49:39,583 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/346bb75ad/55c3d4776a6e4584a0d3e29a3b731b63/FLAG002a585cc [2021-12-16 05:49:39,930 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/346bb75ad/55c3d4776a6e4584a0d3e29a3b731b63 [2021-12-16 05:49:39,932 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-16 05:49:39,934 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-16 05:49:39,936 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-16 05:49:39,936 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-16 05:49:39,938 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-16 05:49:39,939 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 05:49:39" (1/1) ... [2021-12-16 05:49:39,940 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4056775a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:39, skipping insertion in model container [2021-12-16 05:49:39,940 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 05:49:39" (1/1) ... [2021-12-16 05:49:39,944 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-16 05:49:39,985 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-16 05:49:40,401 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 05:49:40,409 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-16 05:49:40,410 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.CACSL2BoogieTranslatorObserver@230c747b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:40, skipping insertion in model container [2021-12-16 05:49:40,410 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-16 05:49:40,411 INFO L184 ToolchainWalker]: Toolchain execution was canceled (user or tool) before executing de.uni_freiburg.informatik.ultimate.boogie.procedureinliner [2021-12-16 05:49:40,413 INFO L158 Benchmark]: Toolchain (without parser) took 477.76ms. Allocated memory was 88.1MB in the beginning and 109.1MB in the end (delta: 21.0MB). Free memory was 56.9MB in the beginning and 80.7MB in the end (delta: -23.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2021-12-16 05:49:40,414 INFO L158 Benchmark]: CDTParser took 0.29ms. Allocated memory is still 88.1MB. Free memory is still 45.2MB. There was no memory consumed. Max. memory is 16.1GB. [2021-12-16 05:49:40,415 INFO L158 Benchmark]: CACSL2BoogieTranslator took 474.84ms. Allocated memory was 88.1MB in the beginning and 109.1MB in the end (delta: 21.0MB). Free memory was 56.6MB in the beginning and 80.7MB in the end (delta: -24.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2021-12-16 05:49:40,416 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.29ms. Allocated memory is still 88.1MB. Free memory is still 45.2MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 474.84ms. Allocated memory was 88.1MB in the beginning and 109.1MB in the end (delta: 21.0MB). Free memory was 56.6MB in the beginning and 80.7MB in the end (delta: -24.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - UnsupportedSyntaxResult [Line: 897]: 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/memsafety/20020406-1.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 1ecdf6fdf9ec72145fabb79894bcc278b3e5646bc4893dbabc4bb180fa53c5ae --- Real Ultimate output --- This is Ultimate 0.2.2-tmp.no-commuhash-c3fed41 [2021-12-16 05:49:41,922 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-16 05:49:41,923 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-16 05:49:41,958 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-16 05:49:41,960 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-16 05:49:41,961 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-16 05:49:41,963 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-16 05:49:41,964 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-16 05:49:41,965 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-16 05:49:41,965 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-16 05:49:41,966 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-16 05:49:41,967 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-16 05:49:41,968 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-16 05:49:41,969 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-16 05:49:41,971 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-16 05:49:41,972 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-16 05:49:41,974 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-16 05:49:41,978 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-16 05:49:41,979 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-16 05:49:41,980 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-16 05:49:41,984 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-16 05:49:41,987 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-16 05:49:41,988 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-16 05:49:41,988 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-16 05:49:41,990 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-16 05:49:41,991 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-16 05:49:41,991 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-16 05:49:41,992 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-16 05:49:41,998 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-16 05:49:41,999 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-16 05:49:41,999 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-16 05:49:42,000 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-16 05:49:42,001 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-16 05:49:42,003 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-16 05:49:42,003 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-16 05:49:42,004 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-16 05:49:42,004 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-16 05:49:42,004 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-16 05:49:42,005 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-16 05:49:42,005 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-16 05:49:42,006 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-16 05:49:42,007 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-32bit-Automizer_Bitvector.epf [2021-12-16 05:49:42,034 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-16 05:49:42,034 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-16 05:49:42,035 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-16 05:49:42,035 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-16 05:49:42,036 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-16 05:49:42,036 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-16 05:49:42,037 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-16 05:49:42,037 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-16 05:49:42,037 INFO L138 SettingsManager]: * Use SBE=true [2021-12-16 05:49:42,037 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-16 05:49:42,038 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-16 05:49:42,038 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-16 05:49:42,038 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-16 05:49:42,039 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-16 05:49:42,039 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-16 05:49:42,039 INFO L138 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2021-12-16 05:49:42,039 INFO L138 SettingsManager]: * Bitprecise bitfields=true [2021-12-16 05:49:42,039 INFO L138 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2021-12-16 05:49:42,039 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-16 05:49:42,039 INFO L138 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2021-12-16 05:49:42,040 INFO L138 SettingsManager]: * Use bitvectors instead of ints=true [2021-12-16 05:49:42,040 INFO L138 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2021-12-16 05:49:42,040 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-16 05:49:42,040 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-16 05:49:42,040 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-16 05:49:42,040 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-16 05:49:42,041 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-16 05:49:42,041 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-16 05:49:42,041 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-16 05:49:42,041 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-16 05:49:42,041 INFO L138 SettingsManager]: * Trace refinement strategy=WOLF [2021-12-16 05:49:42,041 INFO L138 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2021-12-16 05:49:42,042 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-16 05:49:42,042 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-12-16 05:49:42,042 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 -> 1ecdf6fdf9ec72145fabb79894bcc278b3e5646bc4893dbabc4bb180fa53c5ae [2021-12-16 05:49:42,282 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-16 05:49:42,306 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-16 05:49:42,308 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-16 05:49:42,310 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-16 05:49:42,311 INFO L275 PluginConnector]: CDTParser initialized [2021-12-16 05:49:42,312 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/memsafety/20020406-1.i [2021-12-16 05:49:42,364 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8c9c46e2f/0caf2233daed4ef187bc51ebfb7f5aa1/FLAGf88664415 [2021-12-16 05:49:42,865 INFO L306 CDTParser]: Found 1 translation units. [2021-12-16 05:49:42,866 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/memsafety/20020406-1.i [2021-12-16 05:49:42,880 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8c9c46e2f/0caf2233daed4ef187bc51ebfb7f5aa1/FLAGf88664415 [2021-12-16 05:49:43,184 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8c9c46e2f/0caf2233daed4ef187bc51ebfb7f5aa1 [2021-12-16 05:49:43,186 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-16 05:49:43,188 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-16 05:49:43,188 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-16 05:49:43,189 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-16 05:49:43,191 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-16 05:49:43,192 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:43,193 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@50e57941 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43, skipping insertion in model container [2021-12-16 05:49:43,193 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:43,198 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-16 05:49:43,249 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-16 05:49:43,716 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 05:49:43,728 INFO L200 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2021-12-16 05:49:43,733 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-16 05:49:43,784 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 05:49:43,791 INFO L203 MainTranslator]: Completed pre-run [2021-12-16 05:49:43,830 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 05:49:43,901 INFO L208 MainTranslator]: Completed translation [2021-12-16 05:49:43,901 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43 WrapperNode [2021-12-16 05:49:43,901 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-16 05:49:43,903 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-16 05:49:43,903 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-16 05:49:43,903 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-16 05:49:43,909 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:43,938 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:43,966 INFO L137 Inliner]: procedures = 286, calls = 76, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 65 [2021-12-16 05:49:43,967 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-16 05:49:43,968 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-16 05:49:43,968 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-16 05:49:43,968 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-16 05:49:43,973 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:43,974 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:43,987 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:43,988 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:44,005 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:44,015 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:44,017 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:44,024 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-16 05:49:44,028 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-16 05:49:44,028 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-16 05:49:44,028 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-16 05:49:44,029 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (1/1) ... [2021-12-16 05:49:44,034 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-16 05:49:44,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 05:49:44,053 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-16 05:49:44,073 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-16 05:49:44,084 INFO L130 BoogieDeclarations]: Found specification of procedure DUPFFdeg [2021-12-16 05:49:44,084 INFO L138 BoogieDeclarations]: Found implementation of procedure DUPFFdeg [2021-12-16 05:49:44,084 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE4 [2021-12-16 05:49:44,085 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-16 05:49:44,085 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-16 05:49:44,085 INFO L130 BoogieDeclarations]: Found specification of procedure DUPFFnew [2021-12-16 05:49:44,085 INFO L138 BoogieDeclarations]: Found implementation of procedure DUPFFnew [2021-12-16 05:49:44,085 INFO L130 BoogieDeclarations]: Found specification of procedure DUPFFfree [2021-12-16 05:49:44,085 INFO L138 BoogieDeclarations]: Found implementation of procedure DUPFFfree [2021-12-16 05:49:44,085 INFO L130 BoogieDeclarations]: Found specification of procedure DUPFFshift_add [2021-12-16 05:49:44,085 INFO L138 BoogieDeclarations]: Found implementation of procedure DUPFFshift_add [2021-12-16 05:49:44,086 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-16 05:49:44,086 INFO L130 BoogieDeclarations]: Found specification of procedure write~intINTTYPE4 [2021-12-16 05:49:44,086 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1 [2021-12-16 05:49:44,086 INFO L130 BoogieDeclarations]: Found specification of procedure FFmul [2021-12-16 05:49:44,086 INFO L138 BoogieDeclarations]: Found implementation of procedure FFmul [2021-12-16 05:49:44,086 INFO L130 BoogieDeclarations]: Found specification of procedure DUPFFexgcd [2021-12-16 05:49:44,086 INFO L138 BoogieDeclarations]: Found implementation of procedure DUPFFexgcd [2021-12-16 05:49:44,086 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-16 05:49:44,087 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-16 05:49:44,087 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-16 05:49:44,087 INFO L130 BoogieDeclarations]: Found specification of procedure DUPFFswap [2021-12-16 05:49:44,087 INFO L138 BoogieDeclarations]: Found implementation of procedure DUPFFswap [2021-12-16 05:49:44,087 INFO L130 BoogieDeclarations]: Found specification of procedure DUPFFcopy [2021-12-16 05:49:44,088 INFO L138 BoogieDeclarations]: Found implementation of procedure DUPFFcopy [2021-12-16 05:49:44,088 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-16 05:49:44,088 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-16 05:49:44,255 INFO L236 CfgBuilder]: Building ICFG [2021-12-16 05:49:44,256 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-16 05:49:44,825 INFO L277 CfgBuilder]: Performing block encoding [2021-12-16 05:49:44,836 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-16 05:49:44,837 INFO L301 CfgBuilder]: Removed 2 assume(true) statements. [2021-12-16 05:49:44,838 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 05:49:44 BoogieIcfgContainer [2021-12-16 05:49:44,838 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-16 05:49:44,840 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-16 05:49:44,840 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-16 05:49:44,842 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-16 05:49:44,843 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.12 05:49:43" (1/3) ... [2021-12-16 05:49:44,844 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@14439a28 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.12 05:49:44, skipping insertion in model container [2021-12-16 05:49:44,844 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 05:49:43" (2/3) ... [2021-12-16 05:49:44,844 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@14439a28 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.12 05:49:44, skipping insertion in model container [2021-12-16 05:49:44,844 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 05:49:44" (3/3) ... [2021-12-16 05:49:44,847 INFO L111 eAbstractionObserver]: Analyzing ICFG 20020406-1.i [2021-12-16 05:49:44,852 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-16 05:49:44,852 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 55 error locations. [2021-12-16 05:49:44,905 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-16 05:49:44,918 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-16 05:49:44,919 INFO L340 AbstractCegarLoop]: Starting to check reachability of 55 error locations. [2021-12-16 05:49:44,933 INFO L276 IsEmpty]: Start isEmpty. Operand has 187 states, 90 states have (on average 1.7333333333333334) internal successors, (156), 146 states have internal predecessors, (156), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-12-16 05:49:44,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2021-12-16 05:49:44,937 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:44,937 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1] [2021-12-16 05:49:44,938 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting DUPFFnewErr0REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:44,942 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:44,942 INFO L85 PathProgramCache]: Analyzing trace with hash 228226931, now seen corresponding path program 1 times [2021-12-16 05:49:44,950 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:44,951 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1162931486] [2021-12-16 05:49:44,952 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:44,952 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:44,952 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:44,954 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-16 05:49:44,956 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-16 05:49:45,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:45,047 INFO L263 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-16 05:49:45,051 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:45,127 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-16 05:49:45,138 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-16 05:49:45,139 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:45,139 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:45,140 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1162931486] [2021-12-16 05:49:45,140 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1162931486] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:45,140 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:45,141 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-16 05:49:45,142 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1127104471] [2021-12-16 05:49:45,143 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:45,147 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-16 05:49:45,148 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:45,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-16 05:49:45,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-16 05:49:45,185 INFO L87 Difference]: Start difference. First operand has 187 states, 90 states have (on average 1.7333333333333334) internal successors, (156), 146 states have internal predecessors, (156), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) Second operand has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:45,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:45,510 INFO L93 Difference]: Finished difference Result 182 states and 218 transitions. [2021-12-16 05:49:45,512 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-16 05:49:45,512 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 5 [2021-12-16 05:49:45,513 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:45,518 INFO L225 Difference]: With dead ends: 182 [2021-12-16 05:49:45,518 INFO L226 Difference]: Without dead ends: 180 [2021-12-16 05:49:45,519 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-16 05:49:45,522 INFO L933 BasicCegarLoop]: 203 mSDtfsCounter, 22 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 344 SdHoareTripleChecker+Invalid, 73 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:45,522 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 344 Invalid, 73 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-16 05:49:45,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2021-12-16 05:49:45,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 180. [2021-12-16 05:49:45,563 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 180 states, 87 states have (on average 1.6781609195402298) internal successors, (146), 139 states have internal predecessors, (146), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-12-16 05:49:45,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 180 states to 180 states and 216 transitions. [2021-12-16 05:49:45,583 INFO L78 Accepts]: Start accepts. Automaton has 180 states and 216 transitions. Word has length 5 [2021-12-16 05:49:45,591 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:45,591 INFO L470 AbstractCegarLoop]: Abstraction has 180 states and 216 transitions. [2021-12-16 05:49:45,591 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:45,592 INFO L276 IsEmpty]: Start isEmpty. Operand 180 states and 216 transitions. [2021-12-16 05:49:45,592 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2021-12-16 05:49:45,592 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:45,592 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1] [2021-12-16 05:49:45,599 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (2)] Ended with exit code 0 [2021-12-16 05:49:45,792 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-16 05:49:45,793 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting DUPFFnewErr1REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:45,794 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:45,794 INFO L85 PathProgramCache]: Analyzing trace with hash 228226932, now seen corresponding path program 1 times [2021-12-16 05:49:45,795 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:45,795 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [742336577] [2021-12-16 05:49:45,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:45,795 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:45,795 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:45,796 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-16 05:49:45,798 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-16 05:49:45,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:45,865 INFO L263 TraceCheckSpWp]: Trace formula consists of 50 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-16 05:49:45,871 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:45,884 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-16 05:49:45,891 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-16 05:49:45,891 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:45,891 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:45,892 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [742336577] [2021-12-16 05:49:45,892 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [742336577] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:45,892 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:45,892 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-16 05:49:45,892 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1082793451] [2021-12-16 05:49:45,892 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:45,893 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-12-16 05:49:45,893 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:45,894 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-12-16 05:49:45,894 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-16 05:49:45,894 INFO L87 Difference]: Start difference. First operand 180 states and 216 transitions. Second operand has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:46,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:46,124 INFO L93 Difference]: Finished difference Result 184 states and 225 transitions. [2021-12-16 05:49:46,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-16 05:49:46,125 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 5 [2021-12-16 05:49:46,125 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:46,127 INFO L225 Difference]: With dead ends: 184 [2021-12-16 05:49:46,127 INFO L226 Difference]: Without dead ends: 184 [2021-12-16 05:49:46,128 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-12-16 05:49:46,128 INFO L933 BasicCegarLoop]: 210 mSDtfsCounter, 6 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 360 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:46,129 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 360 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-16 05:49:46,129 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2021-12-16 05:49:46,144 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 181. [2021-12-16 05:49:46,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 181 states, 89 states have (on average 1.651685393258427) internal successors, (147), 140 states have internal predecessors, (147), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-12-16 05:49:46,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 217 transitions. [2021-12-16 05:49:46,149 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 217 transitions. Word has length 5 [2021-12-16 05:49:46,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:46,149 INFO L470 AbstractCegarLoop]: Abstraction has 181 states and 217 transitions. [2021-12-16 05:49:46,149 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:46,149 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 217 transitions. [2021-12-16 05:49:46,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2021-12-16 05:49:46,150 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:46,150 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:46,159 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-16 05:49:46,356 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-16 05:49:46,356 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting DUPFFnewErr3REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:46,357 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:46,357 INFO L85 PathProgramCache]: Analyzing trace with hash 282747829, now seen corresponding path program 1 times [2021-12-16 05:49:46,357 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:46,357 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1445341664] [2021-12-16 05:49:46,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:46,358 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:46,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:46,359 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-16 05:49:46,360 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-16 05:49:46,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:46,420 INFO L263 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-16 05:49:46,421 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:46,436 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-16 05:49:46,442 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-16 05:49:46,495 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:49:46,497 INFO L388 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-16 05:49:46,505 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-16 05:49:46,506 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 14 treesize of output 14 [2021-12-16 05:49:46,518 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-16 05:49:46,518 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:46,518 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:46,519 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1445341664] [2021-12-16 05:49:46,519 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1445341664] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:46,519 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:46,519 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-16 05:49:46,520 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1245316049] [2021-12-16 05:49:46,520 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:46,520 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-16 05:49:46,520 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:46,521 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-16 05:49:46,521 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-12-16 05:49:46,521 INFO L87 Difference]: Start difference. First operand 181 states and 217 transitions. Second operand has 4 states, 3 states have (on average 2.0) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:46,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:46,740 INFO L93 Difference]: Finished difference Result 177 states and 213 transitions. [2021-12-16 05:49:46,741 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-12-16 05:49:46,741 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 2.0) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2021-12-16 05:49:46,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:46,742 INFO L225 Difference]: With dead ends: 177 [2021-12-16 05:49:46,742 INFO L226 Difference]: Without dead ends: 177 [2021-12-16 05:49:46,742 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-12-16 05:49:46,743 INFO L933 BasicCegarLoop]: 200 mSDtfsCounter, 33 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 342 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:46,743 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 342 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-16 05:49:46,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2021-12-16 05:49:46,750 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 175. [2021-12-16 05:49:46,750 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 87 states have (on average 1.6206896551724137) internal successors, (141), 134 states have internal predecessors, (141), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-12-16 05:49:46,751 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 211 transitions. [2021-12-16 05:49:46,751 INFO L78 Accepts]: Start accepts. Automaton has 175 states and 211 transitions. Word has length 7 [2021-12-16 05:49:46,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:46,752 INFO L470 AbstractCegarLoop]: Abstraction has 175 states and 211 transitions. [2021-12-16 05:49:46,752 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 2.0) internal successors, (6), 4 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:46,752 INFO L276 IsEmpty]: Start isEmpty. Operand 175 states and 211 transitions. [2021-12-16 05:49:46,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-12-16 05:49:46,752 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:46,753 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:46,782 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (4)] Forceful destruction successful, exit code 0 [2021-12-16 05:49:46,953 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-16 05:49:46,954 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting DUPFFnewErr6ASSERT_VIOLATIONMEMORY_DEREFERENCE === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:46,954 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:46,954 INFO L85 PathProgramCache]: Analyzing trace with hash -1865414411, now seen corresponding path program 1 times [2021-12-16 05:49:46,954 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:46,955 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1597541379] [2021-12-16 05:49:46,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:46,955 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:46,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:46,957 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-16 05:49:46,959 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-16 05:49:47,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:47,034 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-16 05:49:47,035 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:47,060 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-16 05:49:47,085 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:49:47,112 INFO L388 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 24 treesize of output 12 [2021-12-16 05:49:47,126 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-16 05:49:47,127 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:47,127 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:47,127 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1597541379] [2021-12-16 05:49:47,127 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1597541379] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:47,127 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:47,127 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-16 05:49:47,128 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1349965441] [2021-12-16 05:49:47,128 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:47,128 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-16 05:49:47,128 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:47,129 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-16 05:49:47,129 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-16 05:49:47,129 INFO L87 Difference]: Start difference. First operand 175 states and 211 transitions. Second operand has 6 states, 5 states have (on average 2.0) internal successors, (10), 6 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:47,632 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:47,632 INFO L93 Difference]: Finished difference Result 186 states and 233 transitions. [2021-12-16 05:49:47,633 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-12-16 05:49:47,633 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 6 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2021-12-16 05:49:47,633 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:47,634 INFO L225 Difference]: With dead ends: 186 [2021-12-16 05:49:47,634 INFO L226 Difference]: Without dead ends: 186 [2021-12-16 05:49:47,635 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2021-12-16 05:49:47,635 INFO L933 BasicCegarLoop]: 209 mSDtfsCounter, 28 mSDsluCounter, 602 mSDsCounter, 0 mSdLazyCounter, 262 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 811 SdHoareTripleChecker+Invalid, 271 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 262 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:47,635 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [28 Valid, 811 Invalid, 271 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 262 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-16 05:49:47,636 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2021-12-16 05:49:47,642 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 174. [2021-12-16 05:49:47,642 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 87 states have (on average 1.6091954022988506) internal successors, (140), 133 states have internal predecessors, (140), 35 states have call successors, (35), 8 states have call predecessors, (35), 8 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-12-16 05:49:47,643 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 210 transitions. [2021-12-16 05:49:47,643 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 210 transitions. Word has length 11 [2021-12-16 05:49:47,644 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:47,644 INFO L470 AbstractCegarLoop]: Abstraction has 174 states and 210 transitions. [2021-12-16 05:49:47,644 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 6 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:47,644 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 210 transitions. [2021-12-16 05:49:47,644 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2021-12-16 05:49:47,644 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:47,645 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:47,652 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-16 05:49:47,851 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-16 05:49:47,851 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting DUPFFnewErr7ASSERT_VIOLATIONMEMORY_DEREFERENCE === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:47,851 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:47,852 INFO L85 PathProgramCache]: Analyzing trace with hash -1993271845, now seen corresponding path program 1 times [2021-12-16 05:49:47,852 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:47,852 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [586060231] [2021-12-16 05:49:47,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:47,852 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:47,852 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:47,853 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-16 05:49:47,854 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-16 05:49:47,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:47,919 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-16 05:49:47,920 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:47,940 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2021-12-16 05:49:47,962 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:49:47,969 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:49:48,013 INFO L388 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 25 treesize of output 13 [2021-12-16 05:49:48,017 INFO L388 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 19 treesize of output 7 [2021-12-16 05:49:48,065 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-16 05:49:48,065 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:48,065 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:48,065 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [586060231] [2021-12-16 05:49:48,065 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [586060231] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:48,066 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:48,066 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2021-12-16 05:49:48,066 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1509999780] [2021-12-16 05:49:48,066 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:48,066 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-16 05:49:48,066 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:48,067 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-16 05:49:48,067 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2021-12-16 05:49:48,067 INFO L87 Difference]: Start difference. First operand 174 states and 210 transitions. Second operand has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 7 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:48,717 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:48,718 INFO L93 Difference]: Finished difference Result 197 states and 234 transitions. [2021-12-16 05:49:48,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-16 05:49:48,719 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 7 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2021-12-16 05:49:48,719 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:48,720 INFO L225 Difference]: With dead ends: 197 [2021-12-16 05:49:48,720 INFO L226 Difference]: Without dead ends: 197 [2021-12-16 05:49:48,721 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=85, Invalid=187, Unknown=0, NotChecked=0, Total=272 [2021-12-16 05:49:48,721 INFO L933 BasicCegarLoop]: 196 mSDtfsCounter, 50 mSDsluCounter, 857 mSDsCounter, 0 mSdLazyCounter, 216 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 1053 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 216 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:48,721 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [50 Valid, 1053 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 216 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2021-12-16 05:49:48,722 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2021-12-16 05:49:48,727 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 190. [2021-12-16 05:49:48,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 102 states have (on average 1.5294117647058822) internal successors, (156), 148 states have internal predecessors, (156), 35 states have call successors, (35), 9 states have call predecessors, (35), 9 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-12-16 05:49:48,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 226 transitions. [2021-12-16 05:49:48,728 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 226 transitions. Word has length 12 [2021-12-16 05:49:48,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:48,728 INFO L470 AbstractCegarLoop]: Abstraction has 190 states and 226 transitions. [2021-12-16 05:49:48,728 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 7 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-12-16 05:49:48,729 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 226 transitions. [2021-12-16 05:49:48,729 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2021-12-16 05:49:48,729 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:48,729 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:48,757 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-16 05:49:48,943 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-16 05:49:48,944 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:48,944 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:48,944 INFO L85 PathProgramCache]: Analyzing trace with hash 335042805, now seen corresponding path program 1 times [2021-12-16 05:49:48,945 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:48,945 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1819337149] [2021-12-16 05:49:48,945 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:48,945 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:48,945 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:48,946 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-16 05:49:48,947 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-16 05:49:49,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:49,049 INFO L263 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-16 05:49:49,050 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:49,152 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-16 05:49:49,152 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:49,152 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:49,152 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1819337149] [2021-12-16 05:49:49,152 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1819337149] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:49,153 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:49,153 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-12-16 05:49:49,153 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [879050774] [2021-12-16 05:49:49,153 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:49,153 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-16 05:49:49,153 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:49,153 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-16 05:49:49,154 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2021-12-16 05:49:49,154 INFO L87 Difference]: Start difference. First operand 190 states and 226 transitions. Second operand has 6 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 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-16 05:49:49,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:49,333 INFO L93 Difference]: Finished difference Result 209 states and 253 transitions. [2021-12-16 05:49:49,335 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-16 05:49:49,335 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 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 21 [2021-12-16 05:49:49,335 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:49,337 INFO L225 Difference]: With dead ends: 209 [2021-12-16 05:49:49,337 INFO L226 Difference]: Without dead ends: 203 [2021-12-16 05:49:49,337 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2021-12-16 05:49:49,338 INFO L933 BasicCegarLoop]: 196 mSDtfsCounter, 43 mSDsluCounter, 561 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 757 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:49,338 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [43 Valid, 757 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-16 05:49:49,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2021-12-16 05:49:49,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 198. [2021-12-16 05:49:49,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 198 states, 109 states have (on average 1.5045871559633028) internal successors, (164), 156 states have internal predecessors, (164), 35 states have call successors, (35), 9 states have call predecessors, (35), 10 states have return successors, (39), 35 states have call predecessors, (39), 35 states have call successors, (39) [2021-12-16 05:49:49,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 198 states to 198 states and 238 transitions. [2021-12-16 05:49:49,347 INFO L78 Accepts]: Start accepts. Automaton has 198 states and 238 transitions. Word has length 21 [2021-12-16 05:49:49,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:49,347 INFO L470 AbstractCegarLoop]: Abstraction has 198 states and 238 transitions. [2021-12-16 05:49:49,347 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.1666666666666665) internal successors, (19), 6 states have internal predecessors, (19), 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-16 05:49:49,347 INFO L276 IsEmpty]: Start isEmpty. Operand 198 states and 238 transitions. [2021-12-16 05:49:49,348 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2021-12-16 05:49:49,348 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:49,348 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:49,355 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-16 05:49:49,555 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-16 05:49:49,555 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:49,556 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:49,556 INFO L85 PathProgramCache]: Analyzing trace with hash 370721495, now seen corresponding path program 1 times [2021-12-16 05:49:49,556 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:49,556 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1112114007] [2021-12-16 05:49:49,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:49,556 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:49,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:49,557 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-16 05:49:49,559 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-16 05:49:49,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:49,645 INFO L263 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-16 05:49:49,646 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:49,750 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-16 05:49:49,750 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 05:49:49,955 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-16 05:49:49,955 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:49,956 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1112114007] [2021-12-16 05:49:49,956 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1112114007] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 05:49:49,956 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 05:49:49,956 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2021-12-16 05:49:49,956 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [7969184] [2021-12-16 05:49:49,956 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 05:49:49,957 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-12-16 05:49:49,957 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:49,957 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-16 05:49:49,957 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=92, Unknown=0, NotChecked=0, Total=132 [2021-12-16 05:49:49,957 INFO L87 Difference]: Start difference. First operand 198 states and 238 transitions. Second operand has 12 states, 12 states have (on average 3.0) internal successors, (36), 12 states have internal predecessors, (36), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:49:50,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:50,480 INFO L93 Difference]: Finished difference Result 246 states and 304 transitions. [2021-12-16 05:49:50,483 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2021-12-16 05:49:50,483 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 12 states have internal predecessors, (36), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 22 [2021-12-16 05:49:50,484 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:50,485 INFO L225 Difference]: With dead ends: 246 [2021-12-16 05:49:50,485 INFO L226 Difference]: Without dead ends: 234 [2021-12-16 05:49:50,485 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=177, Invalid=329, Unknown=0, NotChecked=0, Total=506 [2021-12-16 05:49:50,485 INFO L933 BasicCegarLoop]: 205 mSDtfsCounter, 153 mSDsluCounter, 1146 mSDsCounter, 0 mSdLazyCounter, 226 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 153 SdHoareTripleChecker+Valid, 1351 SdHoareTripleChecker+Invalid, 254 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 226 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:50,486 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [153 Valid, 1351 Invalid, 254 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 226 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2021-12-16 05:49:50,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 234 states. [2021-12-16 05:49:50,501 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 234 to 216. [2021-12-16 05:49:50,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 127 states have (on average 1.4960629921259843) internal successors, (190), 173 states have internal predecessors, (190), 35 states have call successors, (35), 10 states have call predecessors, (35), 10 states have return successors, (39), 35 states have call predecessors, (39), 35 states have call successors, (39) [2021-12-16 05:49:50,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 264 transitions. [2021-12-16 05:49:50,502 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 264 transitions. Word has length 22 [2021-12-16 05:49:50,503 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:50,503 INFO L470 AbstractCegarLoop]: Abstraction has 216 states and 264 transitions. [2021-12-16 05:49:50,503 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 12 states have internal predecessors, (36), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:49:50,503 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 264 transitions. [2021-12-16 05:49:50,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-16 05:49:50,503 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:50,503 INFO L514 BasicCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:50,511 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (8)] Forceful destruction successful, exit code 0 [2021-12-16 05:49:50,704 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-16 05:49:50,704 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:50,704 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:50,704 INFO L85 PathProgramCache]: Analyzing trace with hash -843792011, now seen corresponding path program 2 times [2021-12-16 05:49:50,705 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:50,705 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [443157593] [2021-12-16 05:49:50,705 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-16 05:49:50,705 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:50,705 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:50,708 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-16 05:49:50,709 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-16 05:49:50,799 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2021-12-16 05:49:50,799 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 05:49:50,804 INFO L263 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-16 05:49:50,805 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:50,859 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2021-12-16 05:49:50,859 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:50,859 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:50,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [443157593] [2021-12-16 05:49:50,859 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [443157593] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:50,859 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:50,859 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-16 05:49:50,859 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2015670247] [2021-12-16 05:49:50,860 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:50,860 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-16 05:49:50,860 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:50,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-16 05:49:50,860 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-16 05:49:50,861 INFO L87 Difference]: Start difference. First operand 216 states and 264 transitions. Second operand has 6 states, 5 states have (on average 4.0) internal successors, (20), 5 states have internal predecessors, (20), 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-16 05:49:51,251 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:51,251 INFO L93 Difference]: Finished difference Result 214 states and 262 transitions. [2021-12-16 05:49:51,252 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-16 05:49:51,252 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 4.0) internal successors, (20), 5 states have internal predecessors, (20), 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 25 [2021-12-16 05:49:51,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:51,253 INFO L225 Difference]: With dead ends: 214 [2021-12-16 05:49:51,253 INFO L226 Difference]: Without dead ends: 214 [2021-12-16 05:49:51,253 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2021-12-16 05:49:51,254 INFO L933 BasicCegarLoop]: 192 mSDtfsCounter, 22 mSDsluCounter, 565 mSDsCounter, 0 mSdLazyCounter, 253 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 757 SdHoareTripleChecker+Invalid, 256 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 253 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:51,254 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 757 Invalid, 256 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 253 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-16 05:49:51,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 214 states. [2021-12-16 05:49:51,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 214 to 214. [2021-12-16 05:49:51,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 214 states, 127 states have (on average 1.4803149606299213) internal successors, (188), 171 states have internal predecessors, (188), 35 states have call successors, (35), 10 states have call predecessors, (35), 10 states have return successors, (39), 35 states have call predecessors, (39), 35 states have call successors, (39) [2021-12-16 05:49:51,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 214 states to 214 states and 262 transitions. [2021-12-16 05:49:51,260 INFO L78 Accepts]: Start accepts. Automaton has 214 states and 262 transitions. Word has length 25 [2021-12-16 05:49:51,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:51,260 INFO L470 AbstractCegarLoop]: Abstraction has 214 states and 262 transitions. [2021-12-16 05:49:51,260 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 4.0) internal successors, (20), 5 states have internal predecessors, (20), 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-16 05:49:51,261 INFO L276 IsEmpty]: Start isEmpty. Operand 214 states and 262 transitions. [2021-12-16 05:49:51,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2021-12-16 05:49:51,261 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:51,261 INFO L514 BasicCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:51,271 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-16 05:49:51,467 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-16 05:49:51,467 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:51,468 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:51,468 INFO L85 PathProgramCache]: Analyzing trace with hash -843792010, now seen corresponding path program 1 times [2021-12-16 05:49:51,468 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:51,468 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [2141866109] [2021-12-16 05:49:51,468 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:51,468 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:51,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:51,469 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-16 05:49:51,470 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-16 05:49:51,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:51,574 INFO L263 TraceCheckSpWp]: Trace formula consists of 200 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-16 05:49:51,575 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:51,766 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-16 05:49:51,766 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 05:49:52,109 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-16 05:49:52,109 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:52,109 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [2141866109] [2021-12-16 05:49:52,109 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [2141866109] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 05:49:52,109 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 05:49:52,109 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2021-12-16 05:49:52,109 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [525596770] [2021-12-16 05:49:52,109 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 05:49:52,110 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2021-12-16 05:49:52,110 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:52,110 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-12-16 05:49:52,110 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=222, Unknown=0, NotChecked=0, Total=306 [2021-12-16 05:49:52,110 INFO L87 Difference]: Start difference. First operand 214 states and 262 transitions. Second operand has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 18 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:49:53,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:53,214 INFO L93 Difference]: Finished difference Result 285 states and 358 transitions. [2021-12-16 05:49:53,214 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2021-12-16 05:49:53,214 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 18 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 25 [2021-12-16 05:49:53,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:53,216 INFO L225 Difference]: With dead ends: 285 [2021-12-16 05:49:53,216 INFO L226 Difference]: Without dead ends: 267 [2021-12-16 05:49:53,216 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 235 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=437, Invalid=1045, Unknown=0, NotChecked=0, Total=1482 [2021-12-16 05:49:53,217 INFO L933 BasicCegarLoop]: 215 mSDtfsCounter, 231 mSDsluCounter, 1602 mSDsCounter, 0 mSdLazyCounter, 490 mSolverCounterSat, 68 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 231 SdHoareTripleChecker+Valid, 1817 SdHoareTripleChecker+Invalid, 558 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 68 IncrementalHoareTripleChecker+Valid, 490 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:53,217 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [231 Valid, 1817 Invalid, 558 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [68 Valid, 490 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2021-12-16 05:49:53,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 267 states. [2021-12-16 05:49:53,222 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 267 to 222. [2021-12-16 05:49:53,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 222 states, 134 states have (on average 1.4402985074626866) internal successors, (193), 179 states have internal predecessors, (193), 35 states have call successors, (35), 10 states have call predecessors, (35), 11 states have return successors, (40), 35 states have call predecessors, (40), 35 states have call successors, (40) [2021-12-16 05:49:53,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 222 states to 222 states and 268 transitions. [2021-12-16 05:49:53,223 INFO L78 Accepts]: Start accepts. Automaton has 222 states and 268 transitions. Word has length 25 [2021-12-16 05:49:53,223 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:53,223 INFO L470 AbstractCegarLoop]: Abstraction has 222 states and 268 transitions. [2021-12-16 05:49:53,223 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 2.3333333333333335) internal successors, (42), 18 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:49:53,224 INFO L276 IsEmpty]: Start isEmpty. Operand 222 states and 268 transitions. [2021-12-16 05:49:53,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2021-12-16 05:49:53,224 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:53,224 INFO L514 BasicCegarLoop]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:53,241 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (10)] Ended with exit code 0 [2021-12-16 05:49:53,424 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-16 05:49:53,424 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:53,425 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:53,425 INFO L85 PathProgramCache]: Analyzing trace with hash 168356342, now seen corresponding path program 2 times [2021-12-16 05:49:53,425 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:53,425 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [657062790] [2021-12-16 05:49:53,425 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-16 05:49:53,425 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:53,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:53,426 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-16 05:49:53,427 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-16 05:49:53,517 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2021-12-16 05:49:53,517 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 05:49:53,521 INFO L263 TraceCheckSpWp]: Trace formula consists of 156 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-16 05:49:53,522 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:53,684 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2021-12-16 05:49:53,684 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:49:53,684 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:49:53,684 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [657062790] [2021-12-16 05:49:53,685 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [657062790] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:49:53,685 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:49:53,685 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-12-16 05:49:53,685 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [481097879] [2021-12-16 05:49:53,685 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:49:53,685 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-16 05:49:53,685 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:49:53,685 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-16 05:49:53,685 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2021-12-16 05:49:53,685 INFO L87 Difference]: Start difference. First operand 222 states and 268 transitions. Second operand has 7 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 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-16 05:49:54,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:49:54,129 INFO L93 Difference]: Finished difference Result 220 states and 266 transitions. [2021-12-16 05:49:54,137 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-16 05:49:54,138 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 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 29 [2021-12-16 05:49:54,138 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:49:54,139 INFO L225 Difference]: With dead ends: 220 [2021-12-16 05:49:54,139 INFO L226 Difference]: Without dead ends: 220 [2021-12-16 05:49:54,139 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2021-12-16 05:49:54,140 INFO L933 BasicCegarLoop]: 192 mSDtfsCounter, 26 mSDsluCounter, 618 mSDsCounter, 0 mSdLazyCounter, 193 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 810 SdHoareTripleChecker+Invalid, 195 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 193 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-16 05:49:54,140 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 810 Invalid, 195 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 193 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-16 05:49:54,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2021-12-16 05:49:54,144 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 220. [2021-12-16 05:49:54,144 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 220 states, 134 states have (on average 1.4253731343283582) internal successors, (191), 177 states have internal predecessors, (191), 35 states have call successors, (35), 10 states have call predecessors, (35), 11 states have return successors, (40), 35 states have call predecessors, (40), 35 states have call successors, (40) [2021-12-16 05:49:54,145 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 220 states to 220 states and 266 transitions. [2021-12-16 05:49:54,145 INFO L78 Accepts]: Start accepts. Automaton has 220 states and 266 transitions. Word has length 29 [2021-12-16 05:49:54,145 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:49:54,145 INFO L470 AbstractCegarLoop]: Abstraction has 220 states and 266 transitions. [2021-12-16 05:49:54,145 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.3333333333333335) internal successors, (20), 6 states have internal predecessors, (20), 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-16 05:49:54,146 INFO L276 IsEmpty]: Start isEmpty. Operand 220 states and 266 transitions. [2021-12-16 05:49:54,146 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2021-12-16 05:49:54,146 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:49:54,146 INFO L514 BasicCegarLoop]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:49:54,158 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-16 05:49:54,357 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-16 05:49:54,357 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:49:54,357 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:49:54,357 INFO L85 PathProgramCache]: Analyzing trace with hash 924079462, now seen corresponding path program 1 times [2021-12-16 05:49:54,358 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:49:54,358 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1620755201] [2021-12-16 05:49:54,358 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:49:54,358 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:49:54,358 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:49:54,359 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2021-12-16 05:49:54,360 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Waiting until timeout for monitored process [2021-12-16 05:49:54,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:49:54,565 INFO L263 TraceCheckSpWp]: Trace formula consists of 250 conjuncts, 30 conjunts are in the unsatisfiable core [2021-12-16 05:49:54,567 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:49:54,577 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-16 05:49:54,613 INFO L354 Elim1Store]: treesize reduction 15, result has 46.4 percent of original size [2021-12-16 05:49:54,614 INFO L388 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 20 treesize of output 27 [2021-12-16 05:49:54,645 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:49:54,763 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,763 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 40 treesize of output 38 [2021-12-16 05:49:54,789 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,789 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 40 treesize of output 38 [2021-12-16 05:49:54,818 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,819 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 40 treesize of output 38 [2021-12-16 05:49:54,849 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,849 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 40 treesize of output 38 [2021-12-16 05:49:54,874 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,874 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 40 treesize of output 38 [2021-12-16 05:49:54,902 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,902 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 40 treesize of output 38 [2021-12-16 05:49:54,931 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,931 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 40 treesize of output 38 [2021-12-16 05:49:54,955 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:49:54,955 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 38 [2021-12-16 05:49:55,056 INFO L354 Elim1Store]: treesize reduction 296, result has 10.6 percent of original size [2021-12-16 05:49:55,057 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 4 case distinctions, treesize of input 51 treesize of output 56 [2021-12-16 05:49:55,147 INFO L354 Elim1Store]: treesize reduction 324, result has 10.2 percent of original size [2021-12-16 05:49:55,148 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 4 case distinctions, treesize of input 53 treesize of output 58 [2021-12-16 05:49:55,243 INFO L388 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 34 treesize of output 16 [2021-12-16 05:49:55,273 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-16 05:49:55,274 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 05:49:57,931 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_552 (Array (_ BitVec 32) (_ BitVec 32)))) (= (_ bv0 1) (bvadd (select |c_#valid| (select (select (store |c_#memory_$Pointer$.base| |c_DUPFFnew_#Ultimate.C_memset_#ptr#1.base| v_ArrVal_552) |c_DUPFFnew_~ans~0#1.base|) (bvadd |c_DUPFFnew_~ans~0#1.offset| (_ bv8 32)))) (_ bv1 1)))) is different from false [2021-12-16 05:49:58,078 WARN L838 $PredicateComparison]: unable to prove that (forall ((v_ArrVal_552 (Array (_ BitVec 32) (_ BitVec 32)))) (= (_ bv0 1) (bvadd (select |c_#valid| (let ((.cse0 (bvadd |c_DUPFFnew_~ans~0#1.offset| (_ bv8 32)))) (select (select (store |c_#memory_$Pointer$.base| (select (select |c_#memory_$Pointer$.base| |c_DUPFFnew_~ans~0#1.base|) .cse0) v_ArrVal_552) |c_DUPFFnew_~ans~0#1.base|) .cse0))) (_ bv1 1)))) is different from false [2021-12-16 05:49:58,090 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-16 05:49:58,090 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 27 [2021-12-16 05:49:58,093 INFO L388 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 44 treesize of output 32 [2021-12-16 05:49:58,096 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 11 [2021-12-16 05:50:02,749 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 8 not checked. [2021-12-16 05:50:02,749 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:50:02,749 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1620755201] [2021-12-16 05:50:02,749 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1620755201] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 05:50:02,749 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 05:50:02,750 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 20 [2021-12-16 05:50:02,750 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [195874596] [2021-12-16 05:50:02,750 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 05:50:02,750 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-16 05:50:02,750 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:50:02,750 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-16 05:50:02,750 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=287, Unknown=4, NotChecked=70, Total=420 [2021-12-16 05:50:02,751 INFO L87 Difference]: Start difference. First operand 220 states and 266 transitions. Second operand has 21 states, 20 states have (on average 2.1) internal successors, (42), 19 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:50:03,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:50:03,768 INFO L93 Difference]: Finished difference Result 219 states and 265 transitions. [2021-12-16 05:50:03,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-16 05:50:03,769 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.1) internal successors, (42), 19 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 30 [2021-12-16 05:50:03,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:50:03,770 INFO L225 Difference]: With dead ends: 219 [2021-12-16 05:50:03,771 INFO L226 Difference]: Without dead ends: 219 [2021-12-16 05:50:03,771 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 38 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 111 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=91, Invalid=419, Unknown=4, NotChecked=86, Total=600 [2021-12-16 05:50:03,771 INFO L933 BasicCegarLoop]: 193 mSDtfsCounter, 34 mSDsluCounter, 1944 mSDsCounter, 0 mSdLazyCounter, 498 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 2137 SdHoareTripleChecker+Invalid, 900 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 498 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 392 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2021-12-16 05:50:03,772 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 2137 Invalid, 900 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 498 Invalid, 0 Unknown, 392 Unchecked, 0.8s Time] [2021-12-16 05:50:03,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2021-12-16 05:50:03,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 219. [2021-12-16 05:50:03,777 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 219 states, 134 states have (on average 1.4179104477611941) internal successors, (190), 176 states have internal predecessors, (190), 35 states have call successors, (35), 10 states have call predecessors, (35), 11 states have return successors, (40), 35 states have call predecessors, (40), 35 states have call successors, (40) [2021-12-16 05:50:03,778 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 219 states to 219 states and 265 transitions. [2021-12-16 05:50:03,778 INFO L78 Accepts]: Start accepts. Automaton has 219 states and 265 transitions. Word has length 30 [2021-12-16 05:50:03,778 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:50:03,779 INFO L470 AbstractCegarLoop]: Abstraction has 219 states and 265 transitions. [2021-12-16 05:50:03,779 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.1) internal successors, (42), 19 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:50:03,779 INFO L276 IsEmpty]: Start isEmpty. Operand 219 states and 265 transitions. [2021-12-16 05:50:03,779 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2021-12-16 05:50:03,780 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:50:03,780 INFO L514 BasicCegarLoop]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:50:03,797 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (12)] Forceful destruction successful, exit code 0 [2021-12-16 05:50:03,991 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 [2021-12-16 05:50:03,991 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:50:03,992 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:50:03,992 INFO L85 PathProgramCache]: Analyzing trace with hash 924079463, now seen corresponding path program 1 times [2021-12-16 05:50:03,992 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:50:03,993 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [553431990] [2021-12-16 05:50:03,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:50:03,993 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:50:03,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:50:03,994 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-16 05:50:03,995 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-16 05:50:04,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:50:04,236 INFO L263 TraceCheckSpWp]: Trace formula consists of 250 conjuncts, 49 conjunts are in the unsatisfiable core [2021-12-16 05:50:04,239 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:50:04,249 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-16 05:50:04,268 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2021-12-16 05:50:04,280 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-16 05:50:04,280 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 14 treesize of output 14 [2021-12-16 05:50:04,302 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:50:04,313 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:50:04,470 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,470 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 39 [2021-12-16 05:50:04,485 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,486 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 16 treesize of output 18 [2021-12-16 05:50:04,508 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,508 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 39 [2021-12-16 05:50:04,522 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,523 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 16 treesize of output 18 [2021-12-16 05:50:04,550 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-16 05:50:04,551 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 16 treesize of output 22 [2021-12-16 05:50:04,560 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 7 treesize of output 3 [2021-12-16 05:50:04,579 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,579 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 39 [2021-12-16 05:50:04,621 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,621 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 39 [2021-12-16 05:50:04,635 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,636 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 16 treesize of output 18 [2021-12-16 05:50:04,659 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,660 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 39 [2021-12-16 05:50:04,677 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,678 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 16 treesize of output 18 [2021-12-16 05:50:04,699 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-16 05:50:04,700 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 16 treesize of output 22 [2021-12-16 05:50:04,705 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 7 treesize of output 3 [2021-12-16 05:50:04,728 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,728 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 39 [2021-12-16 05:50:04,774 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-16 05:50:04,774 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 16 treesize of output 22 [2021-12-16 05:50:04,782 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 7 treesize of output 3 [2021-12-16 05:50:04,802 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,802 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 41 treesize of output 39 [2021-12-16 05:50:04,846 INFO L354 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2021-12-16 05:50:04,846 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 50 treesize of output 49 [2021-12-16 05:50:04,851 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 22 treesize of output 24 [2021-12-16 05:50:04,958 INFO L354 Elim1Store]: treesize reduction 296, result has 10.6 percent of original size [2021-12-16 05:50:04,959 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 4 case distinctions, treesize of input 36 treesize of output 47 [2021-12-16 05:50:04,966 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,967 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,967 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,968 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,969 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,970 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,971 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,971 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,972 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,972 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:04,973 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 10 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 57 [2021-12-16 05:50:05,059 INFO L354 Elim1Store]: treesize reduction 324, result has 10.2 percent of original size [2021-12-16 05:50:05,059 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 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 4 case distinctions, treesize of input 38 treesize of output 49 [2021-12-16 05:50:05,065 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,066 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,066 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,067 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,068 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,069 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,069 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,070 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,071 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,071 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:05,072 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 10 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 59 [2021-12-16 05:50:05,198 INFO L388 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 31 treesize of output 13 [2021-12-16 05:50:05,201 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2021-12-16 05:50:05,228 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-16 05:50:05,228 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 05:50:40,147 WARN L227 SmtUtils]: Spent 34.73s on a formula simplification that was a NOOP. DAG size: 194 (called from [L 234] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.cfg.transitions.TransFormulaUtils.sequentialComposition) [2021-12-16 05:50:47,376 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-16 05:50:47,377 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 45 treesize of output 46 [2021-12-16 05:50:47,388 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-16 05:50:47,388 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 36 [2021-12-16 05:50:47,394 INFO L388 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 62 treesize of output 50 [2021-12-16 05:50:47,397 INFO L388 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 96 treesize of output 78 [2021-12-16 05:50:47,406 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 40 treesize of output 32 [2021-12-16 05:50:47,409 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 66 treesize of output 58 [2021-12-16 05:50:47,523 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-16 05:50:47,523 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 45 treesize of output 36 [2021-12-16 05:50:47,526 INFO L388 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 54 treesize of output 36 [2021-12-16 05:50:47,532 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 19 treesize of output 11 [2021-12-16 05:50:47,815 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-16 05:50:47,819 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-16 05:50:47,819 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:50:47,819 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [553431990] [2021-12-16 05:50:47,819 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [553431990] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 05:50:47,819 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 05:50:47,819 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11] total 20 [2021-12-16 05:50:47,819 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1474524786] [2021-12-16 05:50:47,819 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 05:50:47,820 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-16 05:50:47,820 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:50:47,820 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-16 05:50:47,820 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=359, Unknown=6, NotChecked=0, Total=420 [2021-12-16 05:50:47,821 INFO L87 Difference]: Start difference. First operand 219 states and 265 transitions. Second operand has 21 states, 20 states have (on average 2.1) internal successors, (42), 19 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:50:50,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:50:50,596 INFO L93 Difference]: Finished difference Result 220 states and 267 transitions. [2021-12-16 05:50:50,598 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2021-12-16 05:50:50,598 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.1) internal successors, (42), 19 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 30 [2021-12-16 05:50:50,599 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:50:50,600 INFO L225 Difference]: With dead ends: 220 [2021-12-16 05:50:50,600 INFO L226 Difference]: Without dead ends: 220 [2021-12-16 05:50:50,600 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 36 SyntacticMatches, 5 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 152 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=154, Invalid=831, Unknown=7, NotChecked=0, Total=992 [2021-12-16 05:50:50,601 INFO L933 BasicCegarLoop]: 182 mSDtfsCounter, 45 mSDsluCounter, 1765 mSDsCounter, 0 mSdLazyCounter, 577 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 1947 SdHoareTripleChecker+Invalid, 942 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 577 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 352 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2021-12-16 05:50:50,601 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [45 Valid, 1947 Invalid, 942 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 577 Invalid, 0 Unknown, 352 Unchecked, 1.8s Time] [2021-12-16 05:50:50,602 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2021-12-16 05:50:50,605 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 218. [2021-12-16 05:50:50,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 218 states, 134 states have (on average 1.4104477611940298) internal successors, (189), 175 states have internal predecessors, (189), 35 states have call successors, (35), 10 states have call predecessors, (35), 11 states have return successors, (40), 35 states have call predecessors, (40), 35 states have call successors, (40) [2021-12-16 05:50:50,608 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 264 transitions. [2021-12-16 05:50:50,608 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 264 transitions. Word has length 30 [2021-12-16 05:50:50,609 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:50:50,609 INFO L470 AbstractCegarLoop]: Abstraction has 218 states and 264 transitions. [2021-12-16 05:50:50,609 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.1) internal successors, (42), 19 states have internal predecessors, (42), 1 states have call successors, (1), 1 states have call predecessors, (1), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-16 05:50:50,609 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 264 transitions. [2021-12-16 05:50:50,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2021-12-16 05:50:50,613 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:50:50,613 INFO L514 BasicCegarLoop]: trace histogram [8, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:50:50,623 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-16 05:50:50,822 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-16 05:50:50,823 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting DUPFFnewErr7ASSERT_VIOLATIONMEMORY_DEREFERENCE === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:50:50,823 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:50:50,823 INFO L85 PathProgramCache]: Analyzing trace with hash 2092985884, now seen corresponding path program 1 times [2021-12-16 05:50:50,824 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:50:50,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [758507503] [2021-12-16 05:50:50,824 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:50:50,824 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:50:50,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:50:50,825 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-16 05:50:50,826 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-16 05:50:51,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:50:51,032 INFO L263 TraceCheckSpWp]: Trace formula consists of 362 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-16 05:50:51,034 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:50:51,085 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2021-12-16 05:50:51,102 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:50:51,108 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-12-16 05:50:51,146 INFO L388 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 25 treesize of output 13 [2021-12-16 05:50:51,149 INFO L388 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 19 treesize of output 7 [2021-12-16 05:50:51,193 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2021-12-16 05:50:51,193 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-16 05:50:51,193 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:50:51,193 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [758507503] [2021-12-16 05:50:51,194 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [758507503] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 05:50:51,194 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 05:50:51,194 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2021-12-16 05:50:51,194 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1558667120] [2021-12-16 05:50:51,194 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 05:50:51,194 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-16 05:50:51,194 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:50:51,194 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-16 05:50:51,194 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2021-12-16 05:50:51,195 INFO L87 Difference]: Start difference. First operand 218 states and 264 transitions. Second operand has 8 states, 7 states have (on average 4.571428571428571) internal successors, (32), 7 states have internal predecessors, (32), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-16 05:50:51,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 05:50:51,815 INFO L93 Difference]: Finished difference Result 230 states and 271 transitions. [2021-12-16 05:50:51,816 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-16 05:50:51,816 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 4.571428571428571) internal successors, (32), 7 states have internal predecessors, (32), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 42 [2021-12-16 05:50:51,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-16 05:50:51,817 INFO L225 Difference]: With dead ends: 230 [2021-12-16 05:50:51,817 INFO L226 Difference]: Without dead ends: 218 [2021-12-16 05:50:51,817 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=85, Invalid=187, Unknown=0, NotChecked=0, Total=272 [2021-12-16 05:50:51,818 INFO L933 BasicCegarLoop]: 206 mSDtfsCounter, 51 mSDsluCounter, 696 mSDsCounter, 0 mSdLazyCounter, 173 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 902 SdHoareTripleChecker+Invalid, 190 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 173 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-16 05:50:51,818 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [51 Valid, 902 Invalid, 190 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 173 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-16 05:50:51,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2021-12-16 05:50:51,823 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 213. [2021-12-16 05:50:51,824 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 213 states, 130 states have (on average 1.376923076923077) internal successors, (179), 170 states have internal predecessors, (179), 35 states have call successors, (35), 10 states have call predecessors, (35), 10 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2021-12-16 05:50:51,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 249 transitions. [2021-12-16 05:50:51,825 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 249 transitions. Word has length 42 [2021-12-16 05:50:51,825 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-16 05:50:51,825 INFO L470 AbstractCegarLoop]: Abstraction has 213 states and 249 transitions. [2021-12-16 05:50:51,825 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 4.571428571428571) internal successors, (32), 7 states have internal predecessors, (32), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-16 05:50:51,825 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 249 transitions. [2021-12-16 05:50:51,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2021-12-16 05:50:51,827 INFO L506 BasicCegarLoop]: Found error trace [2021-12-16 05:50:51,828 INFO L514 BasicCegarLoop]: trace histogram [13, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 05:50:51,840 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat -unsat_core_generation=3 (14)] Forceful destruction successful, exit code 0 [2021-12-16 05:50:52,036 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-16 05:50:52,036 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr6REQUIRES_VIOLATION === [DUPFFnewErr0REQUIRES_VIOLATION, DUPFFnewErr1REQUIRES_VIOLATION, DUPFFnewErr2REQUIRES_VIOLATION, DUPFFnewErr3REQUIRES_VIOLATION (and 51 more)] === [2021-12-16 05:50:52,037 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 05:50:52,037 INFO L85 PathProgramCache]: Analyzing trace with hash -562772518, now seen corresponding path program 1 times [2021-12-16 05:50:52,037 INFO L121 FreeRefinementEngine]: Executing refinement strategy WOLF [2021-12-16 05:50:52,037 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1538929581] [2021-12-16 05:50:52,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 05:50:52,037 INFO L168 SolverBuilder]: Constructing external solver with command: mathsat -unsat_core_generation=3 [2021-12-16 05:50:52,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/mathsat [2021-12-16 05:50:52,038 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-16 05:50:52,039 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-16 05:50:52,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 05:50:52,322 INFO L263 TraceCheckSpWp]: Trace formula consists of 476 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-16 05:50:52,323 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 05:50:52,567 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 68 proven. 15 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2021-12-16 05:50:52,567 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 05:50:52,977 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 68 proven. 15 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2021-12-16 05:50:52,977 INFO L139 FreeRefinementEngine]: Strategy WOLF found an infeasible trace [2021-12-16 05:50:52,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1538929581] [2021-12-16 05:50:52,977 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1538929581] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 05:50:52,977 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-16 05:50:52,977 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2021-12-16 05:50:52,977 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1626927027] [2021-12-16 05:50:52,977 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-16 05:50:52,978 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2021-12-16 05:50:52,978 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WOLF [2021-12-16 05:50:52,978 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2021-12-16 05:50:52,978 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=276, Unknown=0, NotChecked=0, Total=380 [2021-12-16 05:50:52,978 INFO L87 Difference]: Start difference. First operand 213 states and 249 transitions. Second operand has 20 states, 20 states have (on average 3.25) internal successors, (65), 20 states have internal predecessors, (65), 1 states have call successors, (2), 1 states have call predecessors, (2), 3 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3)