java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf -i ../../../trunk/examples/svcomp/array-examples/standard_strcpy_false-valid-deref_ground.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-1cf7e2d-m [2018-03-29 22:58:18,584 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-03-29 22:58:18,585 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-03-29 22:58:18,600 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-03-29 22:58:18,600 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-03-29 22:58:18,601 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-03-29 22:58:18,602 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-03-29 22:58:18,603 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-03-29 22:58:18,605 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-03-29 22:58:18,606 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-03-29 22:58:18,607 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-03-29 22:58:18,607 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-03-29 22:58:18,608 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-03-29 22:58:18,610 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-03-29 22:58:18,611 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-03-29 22:58:18,613 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-03-29 22:58:18,615 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-03-29 22:58:18,617 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-03-29 22:58:18,618 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-03-29 22:58:18,619 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-03-29 22:58:18,621 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-03-29 22:58:18,622 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-03-29 22:58:18,622 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-03-29 22:58:18,623 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-03-29 22:58:18,624 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-03-29 22:58:18,625 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-03-29 22:58:18,626 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-03-29 22:58:18,626 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-03-29 22:58:18,627 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-03-29 22:58:18,627 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-03-29 22:58:18,628 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-03-29 22:58:18,628 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf [2018-03-29 22:58:18,655 INFO L110 SettingsManager]: Loading preferences was successful [2018-03-29 22:58:18,656 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-03-29 22:58:18,656 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-03-29 22:58:18,656 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-03-29 22:58:18,657 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-03-29 22:58:18,657 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-03-29 22:58:18,657 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-03-29 22:58:18,657 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-03-29 22:58:18,658 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-03-29 22:58:18,658 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-03-29 22:58:18,658 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-03-29 22:58:18,658 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-03-29 22:58:18,659 INFO L133 SettingsManager]: * sizeof long=4 [2018-03-29 22:58:18,659 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-03-29 22:58:18,659 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-03-29 22:58:18,659 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-03-29 22:58:18,659 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-03-29 22:58:18,660 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-03-29 22:58:18,660 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-03-29 22:58:18,660 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-03-29 22:58:18,660 INFO L133 SettingsManager]: * sizeof long double=12 [2018-03-29 22:58:18,660 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-03-29 22:58:18,660 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-03-29 22:58:18,661 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-03-29 22:58:18,661 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-03-29 22:58:18,661 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-03-29 22:58:18,661 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-03-29 22:58:18,661 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-03-29 22:58:18,662 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-03-29 22:58:18,662 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-03-29 22:58:18,662 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-03-29 22:58:18,662 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:18,662 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-03-29 22:58:18,663 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-03-29 22:58:18,663 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-03-29 22:58:18,664 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-03-29 22:58:18,664 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-03-29 22:58:18,700 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-03-29 22:58:18,713 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-03-29 22:58:18,717 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-03-29 22:58:18,719 INFO L271 PluginConnector]: Initializing CDTParser... [2018-03-29 22:58:18,719 INFO L276 PluginConnector]: CDTParser initialized [2018-03-29 22:58:18,720 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-examples/standard_strcpy_false-valid-deref_ground.i [2018-03-29 22:58:19,061 INFO L225 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG0a54e0d1e [2018-03-29 22:58:19,180 INFO L287 CDTParser]: IsIndexed: true [2018-03-29 22:58:19,180 INFO L288 CDTParser]: Found 1 translation units. [2018-03-29 22:58:19,180 INFO L168 CDTParser]: Scanning standard_strcpy_false-valid-deref_ground.i [2018-03-29 22:58:19,181 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-03-29 22:58:19,181 INFO L215 ultiparseSymbolTable]: [2018-03-29 22:58:19,181 INFO L218 ultiparseSymbolTable]: Function table: [2018-03-29 22:58:19,181 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert ('__VERIFIER_assert') in standard_strcpy_false-valid-deref_ground.i [2018-03-29 22:58:19,182 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in standard_strcpy_false-valid-deref_ground.i [2018-03-29 22:58:19,182 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-03-29 22:58:19,182 INFO L233 ultiparseSymbolTable]: [2018-03-29 22:58:19,198 INFO L330 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG0a54e0d1e [2018-03-29 22:58:19,202 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-03-29 22:58:19,206 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-03-29 22:58:19,207 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-03-29 22:58:19,207 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-03-29 22:58:19,212 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-03-29 22:58:19,213 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,215 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3344d245 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19, skipping insertion in model container [2018-03-29 22:58:19,215 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,229 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-29 22:58:19,242 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-29 22:58:19,365 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-29 22:58:19,380 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-29 22:58:19,384 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 5 non ball SCCs. Number of states in SCCs 5. [2018-03-29 22:58:19,390 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19 WrapperNode [2018-03-29 22:58:19,390 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-03-29 22:58:19,390 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-03-29 22:58:19,390 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-03-29 22:58:19,391 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-03-29 22:58:19,400 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,400 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,405 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,405 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,406 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,411 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,411 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,413 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-03-29 22:58:19,413 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-03-29 22:58:19,413 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-03-29 22:58:19,414 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-03-29 22:58:19,415 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-03-29 22:58:19,471 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-03-29 22:58:19,471 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-03-29 22:58:19,471 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-03-29 22:58:19,471 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-03-29 22:58:19,471 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-03-29 22:58:19,472 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-03-29 22:58:19,472 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-03-29 22:58:19,472 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-03-29 22:58:19,472 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-03-29 22:58:19,680 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-03-29 22:58:19,680 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.03 10:58:19 BoogieIcfgContainer [2018-03-29 22:58:19,681 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-03-29 22:58:19,681 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-03-29 22:58:19,681 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-03-29 22:58:19,682 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-03-29 22:58:19,686 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.03 10:58:19" (1/1) ... [2018-03-29 22:58:19,691 WARN L218 ansformationObserver]: HeapSeparator: input icfg has no '#valid' array -- returning unchanged Icfg! [2018-03-29 22:58:19,700 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,701 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,701 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,701 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,702 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_~src~0=v_main_~src~0_1} AuxVars[] AssignedVars[main_~src~0] [2018-03-29 22:58:19,702 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_~dst~0=v_main_~dst~0_1} AuxVars[] AssignedVars[main_~dst~0] [2018-03-29 22:58:19,703 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~i~0_1 0) InVars {} OutVars{main_~i~0=v_main_~i~0_1} AuxVars[] AssignedVars[main_~i~0] [2018-03-29 22:58:19,703 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,703 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: false InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,704 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (or (not (< v_main_~i~0_2 100000)) (not (<= 0 v_main_~i~0_2))) InVars {main_~i~0=v_main_~i~0_2} OutVars{main_~i~0=v_main_~i~0_2} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,704 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,704 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_~x~0=v_main_~x~0_1} AuxVars[] AssignedVars[main_~x~0] [2018-03-29 22:58:19,704 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= (select v_main_~src~0_2 v_main_~i~0_3) 0) InVars {main_~src~0=v_main_~src~0_2, main_~i~0=v_main_~i~0_3} OutVars{main_~src~0=v_main_~src~0_2, main_~i~0=v_main_~i~0_3} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,705 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (not (= (select v_main_~src~0_3 v_main_~i~0_4) 0)) InVars {main_~src~0=v_main_~src~0_3, main_~i~0=v_main_~i~0_4} OutVars{main_~src~0=v_main_~src~0_3, main_~i~0=v_main_~i~0_4} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,705 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~x~0_2 0) InVars {} OutVars{main_~x~0=v_main_~x~0_2} AuxVars[] AssignedVars[main_~x~0] [2018-03-29 22:58:19,706 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (or (not (< v_main_~i~0_5 100000)) (not (<= 0 v_main_~i~0_5))) InVars {main_~i~0=v_main_~i~0_5} OutVars{main_~i~0=v_main_~i~0_5} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,706 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,706 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,706 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: false InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,707 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (or (not (< v_main_~i~0_6 100000)) (not (<= 0 v_main_~i~0_6))) InVars {main_~i~0=v_main_~i~0_6} OutVars{main_~i~0=v_main_~i~0_6} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,707 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,707 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (not (< v_main_~x~0_3 v_main_~i~0_10)) InVars {main_~x~0=v_main_~x~0_3, main_~i~0=v_main_~i~0_10} OutVars{main_~x~0=v_main_~x~0_3, main_~i~0=v_main_~i~0_10} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,708 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (< v_main_~x~0_4 v_main_~i~0_11) InVars {main_~x~0=v_main_~x~0_4, main_~i~0=v_main_~i~0_11} OutVars{main_~x~0=v_main_~x~0_4, main_~i~0=v_main_~i~0_11} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,708 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= |v_main_#res_1| 0) InVars {} OutVars{main_#res=|v_main_#res_1|} AuxVars[] AssignedVars[main_#res] [2018-03-29 22:58:19,708 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~dst~0_2 (store v_main_~dst~0_3 v_main_~i~0_7 (select v_main_~src~0_4 v_main_~i~0_7))) InVars {main_~src~0=v_main_~src~0_4, main_~i~0=v_main_~i~0_7, main_~dst~0=v_main_~dst~0_3} OutVars{main_~src~0=v_main_~src~0_4, main_~i~0=v_main_~i~0_7, main_~dst~0=v_main_~dst~0_2} AuxVars[] AssignedVars[main_~dst~0] [2018-03-29 22:58:19,708 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (or (not (<= 0 v_main_~x~0_5)) (not (< v_main_~x~0_5 100000))) InVars {main_~x~0=v_main_~x~0_5} OutVars{main_~x~0=v_main_~x~0_5} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,709 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,709 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,709 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~i~0_8 (+ v_main_~i~0_9 1)) InVars {main_~i~0=v_main_~i~0_9} OutVars{main_~i~0=v_main_~i~0_8} AuxVars[] AssignedVars[main_~i~0] [2018-03-29 22:58:19,709 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (or (not (<= 0 v_main_~x~0_6)) (not (< v_main_~x~0_6 100000))) InVars {main_~x~0=v_main_~x~0_6} OutVars{main_~x~0=v_main_~x~0_6} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,709 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,710 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= |v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~condInParam_1| (ite (= (select v_main_~src~0_6 v_main_~x~0_10) (select v_main_~dst~0_5 v_main_~x~0_10)) 1 0)) InVars {main_~src~0=v_main_~src~0_6, main_~x~0=v_main_~x~0_10, main_~dst~0=v_main_~dst~0_5} OutVars{__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~cond=|v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~condInParam_1|} AuxVars[] AssignedVars[__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~cond] [2018-03-29 22:58:19,710 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= |v_main_#t~post0_1| v_main_~x~0_8) InVars {main_~x~0=v_main_~x~0_8} OutVars{main_#t~post0=|v_main_#t~post0_1|, main_~x~0=v_main_~x~0_8} AuxVars[] AssignedVars[main_#t~post0] [2018-03-29 22:58:19,711 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_1 |v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~cond_1|) InVars {__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~cond=|v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~cond_1|} OutVars{__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~cond=|v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_#in~cond_1|, __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond=v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_1} AuxVars[] AssignedVars[__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond] [2018-03-29 22:58:19,711 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~x~0_9 (+ |v_main_#t~post0_2| 1)) InVars {main_#t~post0=|v_main_#t~post0_2|} OutVars{main_~x~0=v_main_~x~0_9, main_#t~post0=|v_main_#t~post0_2|} AuxVars[] AssignedVars[main_~x~0] [2018-03-29 22:58:19,711 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= 0 v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_2) InVars {__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond=v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_2} OutVars{__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond=v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_2} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,712 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (not (= 0 v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_3)) InVars {__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond=v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_3} OutVars{__U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond=v___U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert_~cond_3} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,712 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_#t~post0=|v_main_#t~post0_3|} AuxVars[] AssignedVars[main_#t~post0] [2018-03-29 22:58:19,712 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: false InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,712 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,714 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,714 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: (= |v_ULTIMATE.start_#t~ret1_2| |v_main_#resOutParam_1|) InVars {main_#res=|v_main_#resOutParam_1|} OutVars{ULTIMATE.start_#t~ret1=|v_ULTIMATE.start_#t~ret1_2|} AuxVars[] AssignedVars[ULTIMATE.start_#t~ret1] [2018-03-29 22:58:19,714 DEBUG L90 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-29 22:58:19,715 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 29.03 10:58:19 BasicIcfg [2018-03-29 22:58:19,715 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-03-29 22:58:19,716 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-03-29 22:58:19,716 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-03-29 22:58:19,720 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-03-29 22:58:19,720 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 29.03 10:58:19" (1/4) ... [2018-03-29 22:58:19,721 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7fffebe7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.03 10:58:19, skipping insertion in model container [2018-03-29 22:58:19,721 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.03 10:58:19" (2/4) ... [2018-03-29 22:58:19,721 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7fffebe7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.03 10:58:19, skipping insertion in model container [2018-03-29 22:58:19,721 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.03 10:58:19" (3/4) ... [2018-03-29 22:58:19,722 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7fffebe7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 29.03 10:58:19, skipping insertion in model container [2018-03-29 22:58:19,722 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 29.03 10:58:19" (4/4) ... [2018-03-29 22:58:19,723 INFO L107 eAbstractionObserver]: Analyzing ICFG standard_strcpy_false-valid-deref_ground.ileft_unchanged_by_heapseparator [2018-03-29 22:58:19,734 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-03-29 22:58:19,742 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-03-29 22:58:19,786 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-03-29 22:58:19,787 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-03-29 22:58:19,787 INFO L370 AbstractCegarLoop]: Hoare is true [2018-03-29 22:58:19,787 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-03-29 22:58:19,787 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-03-29 22:58:19,787 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-03-29 22:58:19,787 INFO L374 AbstractCegarLoop]: Difference is false [2018-03-29 22:58:19,787 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-03-29 22:58:19,788 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-03-29 22:58:19,788 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-03-29 22:58:19,808 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states. [2018-03-29 22:58:19,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-03-29 22:58:19,814 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:19,814 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:19,815 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:19,820 INFO L82 PathProgramCache]: Analyzing trace with hash 167026923, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:19,832 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:19,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:19,853 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:19,883 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:19,883 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:19,919 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:19,941 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-29 22:58:19,941 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-03-29 22:58:19,943 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-03-29 22:58:19,953 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-03-29 22:58:19,953 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-29 22:58:19,955 INFO L87 Difference]: Start difference. First operand 39 states. Second operand 4 states. [2018-03-29 22:58:20,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:20,042 INFO L93 Difference]: Finished difference Result 108 states and 130 transitions. [2018-03-29 22:58:20,043 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-03-29 22:58:20,044 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 9 [2018-03-29 22:58:20,044 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:20,051 INFO L225 Difference]: With dead ends: 108 [2018-03-29 22:58:20,051 INFO L226 Difference]: Without dead ends: 71 [2018-03-29 22:58:20,054 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-29 22:58:20,070 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-03-29 22:58:20,094 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 45. [2018-03-29 22:58:20,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-03-29 22:58:20,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2018-03-29 22:58:20,098 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 9 [2018-03-29 22:58:20,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:20,098 INFO L459 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2018-03-29 22:58:20,099 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-03-29 22:58:20,099 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2018-03-29 22:58:20,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-03-29 22:58:20,099 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:20,099 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:20,099 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:20,100 INFO L82 PathProgramCache]: Analyzing trace with hash -2125002319, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:20,106 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:20,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:20,114 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:20,127 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:20,128 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:20,180 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:20,206 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-29 22:58:20,207 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-03-29 22:58:20,208 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-03-29 22:58:20,208 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-03-29 22:58:20,208 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-29 22:58:20,209 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand 4 states. [2018-03-29 22:58:20,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:20,226 INFO L93 Difference]: Finished difference Result 54 states and 58 transitions. [2018-03-29 22:58:20,226 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-03-29 22:58:20,226 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-03-29 22:58:20,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:20,227 INFO L225 Difference]: With dead ends: 54 [2018-03-29 22:58:20,227 INFO L226 Difference]: Without dead ends: 52 [2018-03-29 22:58:20,228 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-29 22:58:20,228 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-03-29 22:58:20,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 49. [2018-03-29 22:58:20,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-03-29 22:58:20,233 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 52 transitions. [2018-03-29 22:58:20,233 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 52 transitions. Word has length 15 [2018-03-29 22:58:20,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:20,233 INFO L459 AbstractCegarLoop]: Abstraction has 49 states and 52 transitions. [2018-03-29 22:58:20,234 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-03-29 22:58:20,234 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 52 transitions. [2018-03-29 22:58:20,234 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-03-29 22:58:20,234 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:20,234 INFO L355 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:20,235 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:20,235 INFO L82 PathProgramCache]: Analyzing trace with hash 406766827, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:20,240 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:20,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:20,250 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:20,292 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:20,293 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:20,386 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:20,408 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:20,408 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-29 22:58:20,408 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-29 22:58:20,409 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-29 22:58:20,409 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-03-29 22:58:20,409 INFO L87 Difference]: Start difference. First operand 49 states and 52 transitions. Second operand 8 states. [2018-03-29 22:58:20,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:20,635 INFO L93 Difference]: Finished difference Result 178 states and 200 transitions. [2018-03-29 22:58:20,635 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-03-29 22:58:20,635 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 23 [2018-03-29 22:58:20,636 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:20,640 INFO L225 Difference]: With dead ends: 178 [2018-03-29 22:58:20,641 INFO L226 Difference]: Without dead ends: 175 [2018-03-29 22:58:20,641 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=52, Unknown=0, NotChecked=0, Total=90 [2018-03-29 22:58:20,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2018-03-29 22:58:20,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 77. [2018-03-29 22:58:20,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-03-29 22:58:20,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 84 transitions. [2018-03-29 22:58:20,656 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 84 transitions. Word has length 23 [2018-03-29 22:58:20,656 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:20,656 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 84 transitions. [2018-03-29 22:58:20,657 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-29 22:58:20,657 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 84 transitions. [2018-03-29 22:58:20,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-03-29 22:58:20,657 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:20,658 INFO L355 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:20,658 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:20,658 INFO L82 PathProgramCache]: Analyzing trace with hash -1469768630, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:20,666 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:20,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:20,677 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:20,705 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-29 22:58:20,705 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:20,747 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-03-29 22:58:20,781 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-29 22:58:20,781 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4, 4] imperfect sequences [] total 5 [2018-03-29 22:58:20,782 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-03-29 22:58:20,782 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-03-29 22:58:20,782 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-03-29 22:58:20,783 INFO L87 Difference]: Start difference. First operand 77 states and 84 transitions. Second operand 5 states. [2018-03-29 22:58:20,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:20,846 INFO L93 Difference]: Finished difference Result 97 states and 104 transitions. [2018-03-29 22:58:20,846 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-03-29 22:58:20,846 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 27 [2018-03-29 22:58:20,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:20,848 INFO L225 Difference]: With dead ends: 97 [2018-03-29 22:58:20,848 INFO L226 Difference]: Without dead ends: 77 [2018-03-29 22:58:20,849 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 49 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-03-29 22:58:20,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-03-29 22:58:20,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-03-29 22:58:20,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-03-29 22:58:20,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 83 transitions. [2018-03-29 22:58:20,858 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 83 transitions. Word has length 27 [2018-03-29 22:58:20,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:20,859 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 83 transitions. [2018-03-29 22:58:20,859 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-03-29 22:58:20,859 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 83 transitions. [2018-03-29 22:58:20,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-03-29 22:58:20,860 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:20,860 INFO L355 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:20,861 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:20,861 INFO L82 PathProgramCache]: Analyzing trace with hash 333723178, now seen corresponding path program 1 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:20,874 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:20,884 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:20,887 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:20,939 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:20,939 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:21,016 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:21,038 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:21,038 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2018-03-29 22:58:21,038 INFO L442 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-03-29 22:58:21,039 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-03-29 22:58:21,039 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2018-03-29 22:58:21,039 INFO L87 Difference]: Start difference. First operand 77 states and 83 transitions. Second operand 10 states. [2018-03-29 22:58:21,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:21,145 INFO L93 Difference]: Finished difference Result 103 states and 110 transitions. [2018-03-29 22:58:21,145 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-03-29 22:58:21,145 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 34 [2018-03-29 22:58:21,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:21,146 INFO L225 Difference]: With dead ends: 103 [2018-03-29 22:58:21,146 INFO L226 Difference]: Without dead ends: 77 [2018-03-29 22:58:21,146 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 57 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=88, Unknown=0, NotChecked=0, Total=132 [2018-03-29 22:58:21,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-03-29 22:58:21,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-03-29 22:58:21,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-03-29 22:58:21,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 82 transitions. [2018-03-29 22:58:21,153 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 82 transitions. Word has length 34 [2018-03-29 22:58:21,154 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:21,154 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 82 transitions. [2018-03-29 22:58:21,154 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-03-29 22:58:21,154 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 82 transitions. [2018-03-29 22:58:21,155 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-03-29 22:58:21,155 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:21,155 INFO L355 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:21,155 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:21,155 INFO L82 PathProgramCache]: Analyzing trace with hash 1844330570, now seen corresponding path program 2 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:21,163 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:21,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:21,175 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:21,195 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-03-29 22:58:21,195 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:21,231 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-03-29 22:58:21,252 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:21,253 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-29 22:58:21,253 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-29 22:58:21,253 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-29 22:58:21,253 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-03-29 22:58:21,254 INFO L87 Difference]: Start difference. First operand 77 states and 82 transitions. Second operand 8 states. [2018-03-29 22:58:21,346 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:21,346 INFO L93 Difference]: Finished difference Result 98 states and 108 transitions. [2018-03-29 22:58:21,346 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-03-29 22:58:21,346 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 41 [2018-03-29 22:58:21,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:21,347 INFO L225 Difference]: With dead ends: 98 [2018-03-29 22:58:21,347 INFO L226 Difference]: Without dead ends: 96 [2018-03-29 22:58:21,348 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-03-29 22:58:21,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-03-29 22:58:21,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 93. [2018-03-29 22:58:21,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-03-29 22:58:21,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 100 transitions. [2018-03-29 22:58:21,354 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 100 transitions. Word has length 41 [2018-03-29 22:58:21,355 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:21,355 INFO L459 AbstractCegarLoop]: Abstraction has 93 states and 100 transitions. [2018-03-29 22:58:21,355 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-29 22:58:21,355 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 100 transitions. [2018-03-29 22:58:21,357 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-03-29 22:58:21,357 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:21,357 INFO L355 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:21,357 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:21,357 INFO L82 PathProgramCache]: Analyzing trace with hash -1889137429, now seen corresponding path program 2 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:21,368 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:21,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:21,383 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:21,444 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:21,444 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:21,522 INFO L134 CoverageAnalysis]: Checked inductivity of 117 backedges. 0 proven. 117 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:21,543 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:21,543 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-29 22:58:21,543 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-29 22:58:21,544 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-29 22:58:21,544 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-03-29 22:58:21,544 INFO L87 Difference]: Start difference. First operand 93 states and 100 transitions. Second operand 16 states. [2018-03-29 22:58:21,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:21,975 INFO L93 Difference]: Finished difference Result 538 states and 610 transitions. [2018-03-29 22:58:21,975 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-03-29 22:58:21,975 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 51 [2018-03-29 22:58:21,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:21,979 INFO L225 Difference]: With dead ends: 538 [2018-03-29 22:58:21,980 INFO L226 Difference]: Without dead ends: 535 [2018-03-29 22:58:21,981 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 87 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=174, Invalid=288, Unknown=0, NotChecked=0, Total=462 [2018-03-29 22:58:21,981 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 535 states. [2018-03-29 22:58:22,002 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 535 to 149. [2018-03-29 22:58:22,003 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-03-29 22:58:22,005 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 164 transitions. [2018-03-29 22:58:22,005 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 164 transitions. Word has length 51 [2018-03-29 22:58:22,005 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:22,006 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 164 transitions. [2018-03-29 22:58:22,006 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-29 22:58:22,006 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 164 transitions. [2018-03-29 22:58:22,008 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-03-29 22:58:22,008 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:22,008 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:22,008 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:22,008 INFO L82 PathProgramCache]: Analyzing trace with hash -169194244, now seen corresponding path program 3 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:22,016 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:22,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:22,031 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:22,078 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 40 proven. 13 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-03-29 22:58:22,078 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:22,138 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 32 proven. 13 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-03-29 22:58:22,162 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:22,162 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-03-29 22:58:22,163 INFO L442 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-03-29 22:58:22,163 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-03-29 22:58:22,163 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2018-03-29 22:58:22,163 INFO L87 Difference]: Start difference. First operand 149 states and 164 transitions. Second operand 15 states. [2018-03-29 22:58:22,283 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:22,283 INFO L93 Difference]: Finished difference Result 185 states and 202 transitions. [2018-03-29 22:58:22,284 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-03-29 22:58:22,284 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 65 [2018-03-29 22:58:22,284 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:22,285 INFO L225 Difference]: With dead ends: 185 [2018-03-29 22:58:22,285 INFO L226 Difference]: Without dead ends: 149 [2018-03-29 22:58:22,286 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 113 SyntacticMatches, 3 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=98, Invalid=244, Unknown=0, NotChecked=0, Total=342 [2018-03-29 22:58:22,286 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-03-29 22:58:22,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-03-29 22:58:22,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-03-29 22:58:22,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 163 transitions. [2018-03-29 22:58:22,297 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 163 transitions. Word has length 65 [2018-03-29 22:58:22,297 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:22,297 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 163 transitions. [2018-03-29 22:58:22,298 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-03-29 22:58:22,298 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 163 transitions. [2018-03-29 22:58:22,299 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-03-29 22:58:22,299 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:22,299 INFO L355 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:22,299 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:22,300 INFO L82 PathProgramCache]: Analyzing trace with hash -1020854564, now seen corresponding path program 4 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:22,307 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:22,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:22,321 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:22,395 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 33 proven. 30 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-03-29 22:58:22,395 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:22,479 INFO L134 CoverageAnalysis]: Checked inductivity of 75 backedges. 33 proven. 30 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-03-29 22:58:22,502 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:22,502 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 20 [2018-03-29 22:58:22,502 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-03-29 22:58:22,503 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-03-29 22:58:22,503 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-03-29 22:58:22,503 INFO L87 Difference]: Start difference. First operand 149 states and 163 transitions. Second operand 20 states. [2018-03-29 22:58:22,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:22,676 INFO L93 Difference]: Finished difference Result 191 states and 208 transitions. [2018-03-29 22:58:22,676 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-03-29 22:58:22,676 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 72 [2018-03-29 22:58:22,677 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:22,678 INFO L225 Difference]: With dead ends: 191 [2018-03-29 22:58:22,678 INFO L226 Difference]: Without dead ends: 149 [2018-03-29 22:58:22,679 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 121 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=171, Invalid=479, Unknown=0, NotChecked=0, Total=650 [2018-03-29 22:58:22,679 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-03-29 22:58:22,690 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-03-29 22:58:22,690 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-03-29 22:58:22,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 162 transitions. [2018-03-29 22:58:22,692 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 162 transitions. Word has length 72 [2018-03-29 22:58:22,692 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:22,692 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 162 transitions. [2018-03-29 22:58:22,693 INFO L460 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-03-29 22:58:22,693 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 162 transitions. [2018-03-29 22:58:22,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2018-03-29 22:58:22,695 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:22,695 INFO L355 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:22,695 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:22,695 INFO L82 PathProgramCache]: Analyzing trace with hash 1870164220, now seen corresponding path program 5 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:22,706 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:22,723 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:22,727 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:22,775 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-03-29 22:58:22,775 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:22,857 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-03-29 22:58:22,878 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:22,878 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-29 22:58:22,878 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-29 22:58:22,879 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-29 22:58:22,879 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-03-29 22:58:22,879 INFO L87 Difference]: Start difference. First operand 149 states and 162 transitions. Second operand 16 states. [2018-03-29 22:58:23,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:23,118 INFO L93 Difference]: Finished difference Result 186 states and 210 transitions. [2018-03-29 22:58:23,118 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-03-29 22:58:23,118 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 79 [2018-03-29 22:58:23,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:23,119 INFO L225 Difference]: With dead ends: 186 [2018-03-29 22:58:23,119 INFO L226 Difference]: Without dead ends: 184 [2018-03-29 22:58:23,120 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 143 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=244, Invalid=626, Unknown=0, NotChecked=0, Total=870 [2018-03-29 22:58:23,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-03-29 22:58:23,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 181. [2018-03-29 22:58:23,127 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 181 states. [2018-03-29 22:58:23,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 198 transitions. [2018-03-29 22:58:23,128 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 198 transitions. Word has length 79 [2018-03-29 22:58:23,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:23,129 INFO L459 AbstractCegarLoop]: Abstraction has 181 states and 198 transitions. [2018-03-29 22:58:23,129 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-29 22:58:23,129 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 198 transitions. [2018-03-29 22:58:23,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-03-29 22:58:23,130 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:23,130 INFO L355 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:23,131 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:23,131 INFO L82 PathProgramCache]: Analyzing trace with hash 1191222507, now seen corresponding path program 3 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:23,140 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:23,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:23,159 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:23,266 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 0 proven. 665 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:23,266 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:23,643 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 0 proven. 665 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:23,664 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:23,665 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-29 22:58:23,665 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-29 22:58:23,665 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-29 22:58:23,666 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=286, Invalid=706, Unknown=0, NotChecked=0, Total=992 [2018-03-29 22:58:23,666 INFO L87 Difference]: Start difference. First operand 181 states and 198 transitions. Second operand 32 states. [2018-03-29 22:58:25,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:25,032 INFO L93 Difference]: Finished difference Result 1962 states and 2222 transitions. [2018-03-29 22:58:25,032 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-03-29 22:58:25,032 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 107 [2018-03-29 22:58:25,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:25,044 INFO L225 Difference]: With dead ends: 1962 [2018-03-29 22:58:25,044 INFO L226 Difference]: Without dead ends: 1959 [2018-03-29 22:58:25,046 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 183 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=734, Invalid=1336, Unknown=0, NotChecked=0, Total=2070 [2018-03-29 22:58:25,047 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1959 states. [2018-03-29 22:58:25,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1959 to 293. [2018-03-29 22:58:25,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-29 22:58:25,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 326 transitions. [2018-03-29 22:58:25,101 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 326 transitions. Word has length 107 [2018-03-29 22:58:25,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:25,101 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 326 transitions. [2018-03-29 22:58:25,101 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-29 22:58:25,102 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 326 transitions. [2018-03-29 22:58:25,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2018-03-29 22:58:25,103 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:25,104 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:25,104 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:25,104 INFO L82 PathProgramCache]: Analyzing trace with hash -147904416, now seen corresponding path program 6 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:25,113 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:25,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:25,135 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:25,326 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 210 proven. 54 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2018-03-29 22:58:25,326 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:25,481 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 162 proven. 54 refuted. 0 times theorem prover too weak. 111 trivial. 0 not checked. [2018-03-29 22:58:25,503 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:25,503 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-03-29 22:58:25,504 INFO L442 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-03-29 22:58:25,504 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-03-29 22:58:25,504 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=477, Unknown=0, NotChecked=0, Total=600 [2018-03-29 22:58:25,505 INFO L87 Difference]: Start difference. First operand 293 states and 326 transitions. Second operand 25 states. [2018-03-29 22:58:25,779 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:25,779 INFO L93 Difference]: Finished difference Result 361 states and 400 transitions. [2018-03-29 22:58:25,779 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-03-29 22:58:25,779 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 127 [2018-03-29 22:58:25,780 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:25,781 INFO L225 Difference]: With dead ends: 361 [2018-03-29 22:58:25,781 INFO L226 Difference]: Without dead ends: 293 [2018-03-29 22:58:25,782 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 261 GetRequests, 225 SyntacticMatches, 5 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 235 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=263, Invalid=793, Unknown=0, NotChecked=0, Total=1056 [2018-03-29 22:58:25,783 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-29 22:58:25,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-29 22:58:25,805 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-29 22:58:25,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 325 transitions. [2018-03-29 22:58:25,808 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 325 transitions. Word has length 127 [2018-03-29 22:58:25,808 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:25,808 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 325 transitions. [2018-03-29 22:58:25,808 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-03-29 22:58:25,808 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 325 transitions. [2018-03-29 22:58:25,810 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2018-03-29 22:58:25,810 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:25,811 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:25,811 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:25,811 INFO L82 PathProgramCache]: Analyzing trace with hash 1534054976, now seen corresponding path program 7 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:25,820 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:25,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:25,846 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:26,015 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 219 proven. 85 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2018-03-29 22:58:26,015 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:26,148 INFO L134 CoverageAnalysis]: Checked inductivity of 358 backedges. 179 proven. 85 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2018-03-29 22:58:26,169 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:26,169 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 30 [2018-03-29 22:58:26,169 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-03-29 22:58:26,170 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-03-29 22:58:26,170 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=701, Unknown=0, NotChecked=0, Total=870 [2018-03-29 22:58:26,170 INFO L87 Difference]: Start difference. First operand 293 states and 325 transitions. Second operand 30 states. [2018-03-29 22:58:26,463 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:26,463 INFO L93 Difference]: Finished difference Result 361 states and 399 transitions. [2018-03-29 22:58:26,463 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-03-29 22:58:26,463 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 134 [2018-03-29 22:58:26,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:26,465 INFO L225 Difference]: With dead ends: 361 [2018-03-29 22:58:26,465 INFO L226 Difference]: Without dead ends: 293 [2018-03-29 22:58:26,466 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 277 GetRequests, 233 SyntacticMatches, 6 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 360 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=374, Invalid=1186, Unknown=0, NotChecked=0, Total=1560 [2018-03-29 22:58:26,466 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-29 22:58:26,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-29 22:58:26,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-29 22:58:26,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 324 transitions. [2018-03-29 22:58:26,479 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 324 transitions. Word has length 134 [2018-03-29 22:58:26,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:26,480 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 324 transitions. [2018-03-29 22:58:26,480 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-03-29 22:58:26,480 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 324 transitions. [2018-03-29 22:58:26,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 142 [2018-03-29 22:58:26,481 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:26,482 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:26,482 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:26,482 INFO L82 PathProgramCache]: Analyzing trace with hash 987122784, now seen corresponding path program 8 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:26,493 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:26,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:26,517 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:26,786 INFO L134 CoverageAnalysis]: Checked inductivity of 396 backedges. 212 proven. 123 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2018-03-29 22:58:26,787 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:27,039 INFO L134 CoverageAnalysis]: Checked inductivity of 396 backedges. 188 proven. 123 refuted. 0 times theorem prover too weak. 85 trivial. 0 not checked. [2018-03-29 22:58:27,060 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:27,073 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 35 [2018-03-29 22:58:27,074 INFO L442 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-03-29 22:58:27,074 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-03-29 22:58:27,074 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=222, Invalid=968, Unknown=0, NotChecked=0, Total=1190 [2018-03-29 22:58:27,074 INFO L87 Difference]: Start difference. First operand 293 states and 324 transitions. Second operand 35 states. [2018-03-29 22:58:27,537 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:27,537 INFO L93 Difference]: Finished difference Result 361 states and 398 transitions. [2018-03-29 22:58:27,537 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-03-29 22:58:27,537 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 141 [2018-03-29 22:58:27,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:27,538 INFO L225 Difference]: With dead ends: 361 [2018-03-29 22:58:27,538 INFO L226 Difference]: Without dead ends: 293 [2018-03-29 22:58:27,540 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 293 GetRequests, 241 SyntacticMatches, 7 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 512 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=504, Invalid=1658, Unknown=0, NotChecked=0, Total=2162 [2018-03-29 22:58:27,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-29 22:58:27,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-29 22:58:27,552 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-29 22:58:27,553 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 323 transitions. [2018-03-29 22:58:27,553 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 323 transitions. Word has length 141 [2018-03-29 22:58:27,554 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:27,554 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 323 transitions. [2018-03-29 22:58:27,554 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-03-29 22:58:27,554 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 323 transitions. [2018-03-29 22:58:27,555 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2018-03-29 22:58:27,555 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:27,555 INFO L355 BasicCegarLoop]: trace histogram [8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:27,555 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:27,555 INFO L82 PathProgramCache]: Analyzing trace with hash -1472713152, now seen corresponding path program 9 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:27,583 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:27,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:27,609 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:27,852 INFO L134 CoverageAnalysis]: Checked inductivity of 441 backedges. 189 proven. 168 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-03-29 22:58:27,852 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:28,126 INFO L134 CoverageAnalysis]: Checked inductivity of 441 backedges. 189 proven. 168 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-03-29 22:58:28,147 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:28,147 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 40 [2018-03-29 22:58:28,148 INFO L442 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-03-29 22:58:28,148 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-03-29 22:58:28,148 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=282, Invalid=1278, Unknown=0, NotChecked=0, Total=1560 [2018-03-29 22:58:28,148 INFO L87 Difference]: Start difference. First operand 293 states and 323 transitions. Second operand 40 states. [2018-03-29 22:58:28,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:28,446 INFO L93 Difference]: Finished difference Result 367 states and 404 transitions. [2018-03-29 22:58:28,446 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-03-29 22:58:28,446 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 148 [2018-03-29 22:58:28,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:28,448 INFO L225 Difference]: With dead ends: 367 [2018-03-29 22:58:28,448 INFO L226 Difference]: Without dead ends: 293 [2018-03-29 22:58:28,450 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 309 GetRequests, 249 SyntacticMatches, 8 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 691 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=653, Invalid=2209, Unknown=0, NotChecked=0, Total=2862 [2018-03-29 22:58:28,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-29 22:58:28,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-29 22:58:28,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-29 22:58:28,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 322 transitions. [2018-03-29 22:58:28,464 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 322 transitions. Word has length 148 [2018-03-29 22:58:28,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:28,464 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 322 transitions. [2018-03-29 22:58:28,464 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-03-29 22:58:28,464 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 322 transitions. [2018-03-29 22:58:28,466 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2018-03-29 22:58:28,466 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:28,466 INFO L355 BasicCegarLoop]: trace histogram [9, 9, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:28,466 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:28,466 INFO L82 PathProgramCache]: Analyzing trace with hash 1764651104, now seen corresponding path program 10 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:28,475 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:28,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:28,497 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:28,584 INFO L134 CoverageAnalysis]: Checked inductivity of 493 backedges. 0 proven. 189 refuted. 0 times theorem prover too weak. 304 trivial. 0 not checked. [2018-03-29 22:58:28,585 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:28,865 INFO L134 CoverageAnalysis]: Checked inductivity of 493 backedges. 0 proven. 189 refuted. 0 times theorem prover too weak. 304 trivial. 0 not checked. [2018-03-29 22:58:28,885 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:28,885 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-29 22:58:28,885 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-29 22:58:28,886 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-29 22:58:28,886 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-03-29 22:58:28,886 INFO L87 Difference]: Start difference. First operand 293 states and 322 transitions. Second operand 32 states. [2018-03-29 22:58:29,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:29,980 INFO L93 Difference]: Finished difference Result 362 states and 414 transitions. [2018-03-29 22:58:29,980 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-03-29 22:58:29,980 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 155 [2018-03-29 22:58:29,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:29,982 INFO L225 Difference]: With dead ends: 362 [2018-03-29 22:58:29,983 INFO L226 Difference]: Without dead ends: 360 [2018-03-29 22:58:29,984 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 343 GetRequests, 279 SyntacticMatches, 0 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=1096, Invalid=3194, Unknown=0, NotChecked=0, Total=4290 [2018-03-29 22:58:29,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 360 states. [2018-03-29 22:58:29,997 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 360 to 357. [2018-03-29 22:58:29,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 357 states. [2018-03-29 22:58:29,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 357 states to 357 states and 394 transitions. [2018-03-29 22:58:29,998 INFO L78 Accepts]: Start accepts. Automaton has 357 states and 394 transitions. Word has length 155 [2018-03-29 22:58:29,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:29,998 INFO L459 AbstractCegarLoop]: Abstraction has 357 states and 394 transitions. [2018-03-29 22:58:29,998 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-29 22:58:29,998 INFO L276 IsEmpty]: Start isEmpty. Operand 357 states and 394 transitions. [2018-03-29 22:58:30,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-03-29 22:58:30,001 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:30,001 INFO L355 BasicCegarLoop]: trace histogram [31, 30, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:30,001 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:30,001 INFO L82 PathProgramCache]: Analyzing trace with hash 1399176427, now seen corresponding path program 4 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:30,008 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:30,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:30,035 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:30,455 INFO L134 CoverageAnalysis]: Checked inductivity of 3105 backedges. 0 proven. 3105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:30,455 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:31,430 INFO L134 CoverageAnalysis]: Checked inductivity of 3105 backedges. 0 proven. 3105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:58:31,452 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:31,452 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-29 22:58:31,453 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-29 22:58:31,453 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-29 22:58:31,454 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1086, Invalid=2946, Unknown=0, NotChecked=0, Total=4032 [2018-03-29 22:58:31,454 INFO L87 Difference]: Start difference. First operand 357 states and 394 transitions. Second operand 64 states. [2018-03-29 22:58:37,150 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:37,150 INFO L93 Difference]: Finished difference Result 7498 states and 8470 transitions. [2018-03-29 22:58:37,170 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-03-29 22:58:37,170 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 219 [2018-03-29 22:58:37,170 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:37,192 INFO L225 Difference]: With dead ends: 7498 [2018-03-29 22:58:37,192 INFO L226 Difference]: Without dead ends: 7495 [2018-03-29 22:58:37,196 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 467 GetRequests, 375 SyntacticMatches, 0 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 435 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=3006, Invalid=5736, Unknown=0, NotChecked=0, Total=8742 [2018-03-29 22:58:37,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7495 states. [2018-03-29 22:58:37,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7495 to 581. [2018-03-29 22:58:37,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:37,309 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 650 transitions. [2018-03-29 22:58:37,309 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 650 transitions. Word has length 219 [2018-03-29 22:58:37,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:37,309 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 650 transitions. [2018-03-29 22:58:37,309 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-29 22:58:37,310 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 650 transitions. [2018-03-29 22:58:37,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 252 [2018-03-29 22:58:37,311 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:37,311 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:37,311 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:37,311 INFO L82 PathProgramCache]: Analyzing trace with hash 130963240, now seen corresponding path program 11 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:37,318 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:37,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:37,357 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:37,801 INFO L134 CoverageAnalysis]: Checked inductivity of 1525 backedges. 934 proven. 220 refuted. 0 times theorem prover too weak. 371 trivial. 0 not checked. [2018-03-29 22:58:37,801 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:38,136 INFO L134 CoverageAnalysis]: Checked inductivity of 1525 backedges. 710 proven. 220 refuted. 0 times theorem prover too weak. 595 trivial. 0 not checked. [2018-03-29 22:58:38,157 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:38,157 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 45 [2018-03-29 22:58:38,158 INFO L442 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-03-29 22:58:38,158 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-03-29 22:58:38,159 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=349, Invalid=1631, Unknown=0, NotChecked=0, Total=1980 [2018-03-29 22:58:38,159 INFO L87 Difference]: Start difference. First operand 581 states and 650 transitions. Second operand 45 states. [2018-03-29 22:58:38,629 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:38,630 INFO L93 Difference]: Finished difference Result 713 states and 796 transitions. [2018-03-29 22:58:38,630 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-03-29 22:58:38,630 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 251 [2018-03-29 22:58:38,630 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:38,632 INFO L225 Difference]: With dead ends: 713 [2018-03-29 22:58:38,632 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:38,633 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 517 GetRequests, 449 SyntacticMatches, 9 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 897 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=821, Invalid=2839, Unknown=0, NotChecked=0, Total=3660 [2018-03-29 22:58:38,633 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:38,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:38,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:38,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 649 transitions. [2018-03-29 22:58:38,707 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 649 transitions. Word has length 251 [2018-03-29 22:58:38,707 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:38,707 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 649 transitions. [2018-03-29 22:58:38,707 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-03-29 22:58:38,708 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 649 transitions. [2018-03-29 22:58:38,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-03-29 22:58:38,710 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:38,710 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 10, 10, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:38,710 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:38,710 INFO L82 PathProgramCache]: Analyzing trace with hash 1211166984, now seen corresponding path program 12 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:38,719 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:38,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:38,772 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:39,418 INFO L134 CoverageAnalysis]: Checked inductivity of 1584 backedges. 975 proven. 279 refuted. 0 times theorem prover too weak. 330 trivial. 0 not checked. [2018-03-29 22:58:39,419 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:39,799 INFO L134 CoverageAnalysis]: Checked inductivity of 1584 backedges. 759 proven. 279 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2018-03-29 22:58:39,820 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:39,820 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 50 [2018-03-29 22:58:39,820 INFO L442 AbstractCegarLoop]: Interpolant automaton has 50 states [2018-03-29 22:58:39,821 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2018-03-29 22:58:39,821 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=423, Invalid=2027, Unknown=0, NotChecked=0, Total=2450 [2018-03-29 22:58:39,822 INFO L87 Difference]: Start difference. First operand 581 states and 649 transitions. Second operand 50 states. [2018-03-29 22:58:40,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:40,320 INFO L93 Difference]: Finished difference Result 713 states and 795 transitions. [2018-03-29 22:58:40,321 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-03-29 22:58:40,321 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 258 [2018-03-29 22:58:40,321 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:40,323 INFO L225 Difference]: With dead ends: 713 [2018-03-29 22:58:40,323 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:40,324 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 533 GetRequests, 457 SyntacticMatches, 10 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1130 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1008, Invalid=3548, Unknown=0, NotChecked=0, Total=4556 [2018-03-29 22:58:40,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:40,373 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:40,373 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:40,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 648 transitions. [2018-03-29 22:58:40,376 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 648 transitions. Word has length 258 [2018-03-29 22:58:40,376 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:40,377 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 648 transitions. [2018-03-29 22:58:40,377 INFO L460 AbstractCegarLoop]: Interpolant automaton has 50 states. [2018-03-29 22:58:40,377 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 648 transitions. [2018-03-29 22:58:40,379 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 266 [2018-03-29 22:58:40,379 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:40,379 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 11, 11, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:40,379 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:40,380 INFO L82 PathProgramCache]: Analyzing trace with hash -1368949976, now seen corresponding path program 13 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:40,389 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:40,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:40,448 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:40,871 INFO L134 CoverageAnalysis]: Checked inductivity of 1650 backedges. 1000 proven. 345 refuted. 0 times theorem prover too weak. 305 trivial. 0 not checked. [2018-03-29 22:58:40,871 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:41,304 INFO L134 CoverageAnalysis]: Checked inductivity of 1650 backedges. 800 proven. 345 refuted. 0 times theorem prover too weak. 505 trivial. 0 not checked. [2018-03-29 22:58:41,325 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:41,325 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 34] total 55 [2018-03-29 22:58:41,326 INFO L442 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-03-29 22:58:41,326 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-03-29 22:58:41,327 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=504, Invalid=2466, Unknown=0, NotChecked=0, Total=2970 [2018-03-29 22:58:41,327 INFO L87 Difference]: Start difference. First operand 581 states and 648 transitions. Second operand 55 states. [2018-03-29 22:58:41,968 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:41,968 INFO L93 Difference]: Finished difference Result 713 states and 794 transitions. [2018-03-29 22:58:41,969 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-03-29 22:58:41,969 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 265 [2018-03-29 22:58:41,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:41,971 INFO L225 Difference]: With dead ends: 713 [2018-03-29 22:58:41,971 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:41,972 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 549 GetRequests, 465 SyntacticMatches, 11 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1390 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1214, Invalid=4336, Unknown=0, NotChecked=0, Total=5550 [2018-03-29 22:58:41,972 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:42,010 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:42,011 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:42,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 647 transitions. [2018-03-29 22:58:42,012 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 647 transitions. Word has length 265 [2018-03-29 22:58:42,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:42,012 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 647 transitions. [2018-03-29 22:58:42,012 INFO L460 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-03-29 22:58:42,012 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 647 transitions. [2018-03-29 22:58:42,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-03-29 22:58:42,015 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:42,015 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 12, 12, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:42,015 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:42,015 INFO L82 PathProgramCache]: Analyzing trace with hash 1573342472, now seen corresponding path program 14 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:42,021 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:42,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:42,078 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:42,441 INFO L134 CoverageAnalysis]: Checked inductivity of 1723 backedges. 1009 proven. 418 refuted. 0 times theorem prover too weak. 296 trivial. 0 not checked. [2018-03-29 22:58:42,441 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:42,949 INFO L134 CoverageAnalysis]: Checked inductivity of 1723 backedges. 833 proven. 418 refuted. 0 times theorem prover too weak. 472 trivial. 0 not checked. [2018-03-29 22:58:42,970 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:42,971 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 60 [2018-03-29 22:58:42,971 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-03-29 22:58:42,972 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-03-29 22:58:42,972 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=592, Invalid=2948, Unknown=0, NotChecked=0, Total=3540 [2018-03-29 22:58:42,972 INFO L87 Difference]: Start difference. First operand 581 states and 647 transitions. Second operand 60 states. [2018-03-29 22:58:43,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:43,711 INFO L93 Difference]: Finished difference Result 713 states and 793 transitions. [2018-03-29 22:58:43,711 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-03-29 22:58:43,711 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 272 [2018-03-29 22:58:43,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:43,713 INFO L225 Difference]: With dead ends: 713 [2018-03-29 22:58:43,714 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:43,716 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 565 GetRequests, 473 SyntacticMatches, 12 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1677 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=1439, Invalid=5203, Unknown=0, NotChecked=0, Total=6642 [2018-03-29 22:58:43,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:43,770 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:43,771 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:43,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 646 transitions. [2018-03-29 22:58:43,773 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 646 transitions. Word has length 272 [2018-03-29 22:58:43,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:43,774 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 646 transitions. [2018-03-29 22:58:43,774 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-03-29 22:58:43,774 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 646 transitions. [2018-03-29 22:58:43,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 280 [2018-03-29 22:58:43,776 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:43,777 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 13, 13, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:43,777 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:43,777 INFO L82 PathProgramCache]: Analyzing trace with hash 808558376, now seen corresponding path program 15 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:43,790 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:43,835 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:43,842 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:44,421 INFO L134 CoverageAnalysis]: Checked inductivity of 1803 backedges. 1002 proven. 498 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2018-03-29 22:58:44,421 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:45,182 INFO L134 CoverageAnalysis]: Checked inductivity of 1803 backedges. 858 proven. 498 refuted. 0 times theorem prover too weak. 447 trivial. 0 not checked. [2018-03-29 22:58:45,216 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:45,217 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [40, 40] total 65 [2018-03-29 22:58:45,217 INFO L442 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-03-29 22:58:45,218 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-03-29 22:58:45,218 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=687, Invalid=3473, Unknown=0, NotChecked=0, Total=4160 [2018-03-29 22:58:45,218 INFO L87 Difference]: Start difference. First operand 581 states and 646 transitions. Second operand 65 states. [2018-03-29 22:58:46,041 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:46,041 INFO L93 Difference]: Finished difference Result 713 states and 792 transitions. [2018-03-29 22:58:46,042 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-03-29 22:58:46,042 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 279 [2018-03-29 22:58:46,042 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:46,045 INFO L225 Difference]: With dead ends: 713 [2018-03-29 22:58:46,045 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:46,046 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 581 GetRequests, 481 SyntacticMatches, 13 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1991 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1683, Invalid=6149, Unknown=0, NotChecked=0, Total=7832 [2018-03-29 22:58:46,046 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:46,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:46,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:46,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 645 transitions. [2018-03-29 22:58:46,089 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 645 transitions. Word has length 279 [2018-03-29 22:58:46,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:46,090 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 645 transitions. [2018-03-29 22:58:46,090 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-03-29 22:58:46,090 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 645 transitions. [2018-03-29 22:58:46,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 287 [2018-03-29 22:58:46,091 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:46,091 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:46,091 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:46,091 INFO L82 PathProgramCache]: Analyzing trace with hash -821253880, now seen corresponding path program 16 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:46,097 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:46,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:46,132 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:46,637 INFO L134 CoverageAnalysis]: Checked inductivity of 1890 backedges. 979 proven. 585 refuted. 0 times theorem prover too weak. 326 trivial. 0 not checked. [2018-03-29 22:58:46,637 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:47,265 INFO L134 CoverageAnalysis]: Checked inductivity of 1890 backedges. 875 proven. 585 refuted. 0 times theorem prover too weak. 430 trivial. 0 not checked. [2018-03-29 22:58:47,285 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:47,286 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43, 43] total 70 [2018-03-29 22:58:47,286 INFO L442 AbstractCegarLoop]: Interpolant automaton has 70 states [2018-03-29 22:58:47,287 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 70 interpolants. [2018-03-29 22:58:47,287 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=789, Invalid=4041, Unknown=0, NotChecked=0, Total=4830 [2018-03-29 22:58:47,287 INFO L87 Difference]: Start difference. First operand 581 states and 645 transitions. Second operand 70 states. [2018-03-29 22:58:48,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:48,119 INFO L93 Difference]: Finished difference Result 713 states and 791 transitions. [2018-03-29 22:58:48,119 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-03-29 22:58:48,120 INFO L78 Accepts]: Start accepts. Automaton has 70 states. Word has length 286 [2018-03-29 22:58:48,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:48,122 INFO L225 Difference]: With dead ends: 713 [2018-03-29 22:58:48,122 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:48,123 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 597 GetRequests, 489 SyntacticMatches, 14 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2332 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=1946, Invalid=7174, Unknown=0, NotChecked=0, Total=9120 [2018-03-29 22:58:48,123 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:48,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:48,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:48,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 644 transitions. [2018-03-29 22:58:48,161 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 644 transitions. Word has length 286 [2018-03-29 22:58:48,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:48,161 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 644 transitions. [2018-03-29 22:58:48,161 INFO L460 AbstractCegarLoop]: Interpolant automaton has 70 states. [2018-03-29 22:58:48,161 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 644 transitions. [2018-03-29 22:58:48,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 294 [2018-03-29 22:58:48,163 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:48,163 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:48,163 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:48,163 INFO L82 PathProgramCache]: Analyzing trace with hash -1553153240, now seen corresponding path program 17 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:48,169 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:48,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:48,215 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:49,014 INFO L134 CoverageAnalysis]: Checked inductivity of 1984 backedges. 940 proven. 679 refuted. 0 times theorem prover too weak. 365 trivial. 0 not checked. [2018-03-29 22:58:49,014 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:49,747 INFO L134 CoverageAnalysis]: Checked inductivity of 1984 backedges. 884 proven. 679 refuted. 0 times theorem prover too weak. 421 trivial. 0 not checked. [2018-03-29 22:58:49,768 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:49,769 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [46, 46] total 75 [2018-03-29 22:58:49,769 INFO L442 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-03-29 22:58:49,770 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-03-29 22:58:49,770 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=898, Invalid=4652, Unknown=0, NotChecked=0, Total=5550 [2018-03-29 22:58:49,770 INFO L87 Difference]: Start difference. First operand 581 states and 644 transitions. Second operand 75 states. [2018-03-29 22:58:50,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:50,694 INFO L93 Difference]: Finished difference Result 713 states and 790 transitions. [2018-03-29 22:58:50,694 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-03-29 22:58:50,694 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 293 [2018-03-29 22:58:50,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:50,696 INFO L225 Difference]: With dead ends: 713 [2018-03-29 22:58:50,696 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:50,697 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 497 SyntacticMatches, 15 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2700 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=2228, Invalid=8278, Unknown=0, NotChecked=0, Total=10506 [2018-03-29 22:58:50,698 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:50,732 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:50,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:50,733 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 643 transitions. [2018-03-29 22:58:50,733 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 643 transitions. Word has length 293 [2018-03-29 22:58:50,734 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:50,734 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 643 transitions. [2018-03-29 22:58:50,734 INFO L460 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-03-29 22:58:50,734 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 643 transitions. [2018-03-29 22:58:50,735 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 301 [2018-03-29 22:58:50,735 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:50,736 INFO L355 BasicCegarLoop]: trace histogram [16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:50,736 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:50,736 INFO L82 PathProgramCache]: Analyzing trace with hash -37681912, now seen corresponding path program 18 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:50,755 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:50,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:50,789 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:51,432 INFO L134 CoverageAnalysis]: Checked inductivity of 2085 backedges. 885 proven. 780 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2018-03-29 22:58:51,432 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:52,222 INFO L134 CoverageAnalysis]: Checked inductivity of 2085 backedges. 885 proven. 780 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2018-03-29 22:58:52,243 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:52,243 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 80 [2018-03-29 22:58:52,244 INFO L442 AbstractCegarLoop]: Interpolant automaton has 80 states [2018-03-29 22:58:52,244 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 80 interpolants. [2018-03-29 22:58:52,245 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1014, Invalid=5306, Unknown=0, NotChecked=0, Total=6320 [2018-03-29 22:58:52,245 INFO L87 Difference]: Start difference. First operand 581 states and 643 transitions. Second operand 80 states. [2018-03-29 22:58:53,254 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:53,254 INFO L93 Difference]: Finished difference Result 719 states and 796 transitions. [2018-03-29 22:58:53,254 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-03-29 22:58:53,254 INFO L78 Accepts]: Start accepts. Automaton has 80 states. Word has length 300 [2018-03-29 22:58:53,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:53,256 INFO L225 Difference]: With dead ends: 719 [2018-03-29 22:58:53,256 INFO L226 Difference]: Without dead ends: 581 [2018-03-29 22:58:53,257 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 629 GetRequests, 505 SyntacticMatches, 16 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3095 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=2529, Invalid=9461, Unknown=0, NotChecked=0, Total=11990 [2018-03-29 22:58:53,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-29 22:58:53,293 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-29 22:58:53,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-29 22:58:53,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 642 transitions. [2018-03-29 22:58:53,295 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 642 transitions. Word has length 300 [2018-03-29 22:58:53,295 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:53,295 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 642 transitions. [2018-03-29 22:58:53,295 INFO L460 AbstractCegarLoop]: Interpolant automaton has 80 states. [2018-03-29 22:58:53,295 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 642 transitions. [2018-03-29 22:58:53,297 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 308 [2018-03-29 22:58:53,297 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:53,297 INFO L355 BasicCegarLoop]: trace histogram [17, 17, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:53,297 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:53,297 INFO L82 PathProgramCache]: Analyzing trace with hash 777578280, now seen corresponding path program 19 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:53,305 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:53,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:53,347 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:58:53,714 INFO L134 CoverageAnalysis]: Checked inductivity of 2193 backedges. 0 proven. 885 refuted. 0 times theorem prover too weak. 1308 trivial. 0 not checked. [2018-03-29 22:58:53,714 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:58:54,663 INFO L134 CoverageAnalysis]: Checked inductivity of 2193 backedges. 0 proven. 885 refuted. 0 times theorem prover too weak. 1308 trivial. 0 not checked. [2018-03-29 22:58:54,684 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:58:54,684 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-29 22:58:54,685 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-29 22:58:54,685 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-29 22:58:54,685 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-03-29 22:58:54,685 INFO L87 Difference]: Start difference. First operand 581 states and 642 transitions. Second operand 64 states. [2018-03-29 22:58:59,177 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:58:59,177 INFO L93 Difference]: Finished difference Result 714 states and 822 transitions. [2018-03-29 22:58:59,177 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-03-29 22:58:59,177 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 307 [2018-03-29 22:58:59,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:58:59,180 INFO L225 Difference]: With dead ends: 714 [2018-03-29 22:58:59,180 INFO L226 Difference]: Without dead ends: 712 [2018-03-29 22:58:59,181 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 687 GetRequests, 551 SyntacticMatches, 0 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3452 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=4624, Invalid=14282, Unknown=0, NotChecked=0, Total=18906 [2018-03-29 22:58:59,182 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 712 states. [2018-03-29 22:58:59,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 712 to 709. [2018-03-29 22:58:59,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-03-29 22:58:59,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 786 transitions. [2018-03-29 22:58:59,232 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 786 transitions. Word has length 307 [2018-03-29 22:58:59,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:58:59,233 INFO L459 AbstractCegarLoop]: Abstraction has 709 states and 786 transitions. [2018-03-29 22:58:59,233 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-29 22:58:59,233 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 786 transitions. [2018-03-29 22:58:59,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 444 [2018-03-29 22:58:59,236 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:58:59,237 INFO L355 BasicCegarLoop]: trace histogram [63, 62, 62, 62, 62, 62, 62, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:58:59,237 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:58:59,237 INFO L82 PathProgramCache]: Analyzing trace with hash -1594884885, now seen corresponding path program 5 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:58:59,244 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:58:59,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:58:59,294 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:59:00,537 INFO L134 CoverageAnalysis]: Checked inductivity of 13361 backedges. 0 proven. 13361 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:59:00,537 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:59:04,251 INFO L134 CoverageAnalysis]: Checked inductivity of 13361 backedges. 0 proven. 13361 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-29 22:59:04,272 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:59:04,272 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-03-29 22:59:04,273 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-03-29 22:59:04,274 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-03-29 22:59:04,274 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=4222, Invalid=12034, Unknown=0, NotChecked=0, Total=16256 [2018-03-29 22:59:04,274 INFO L87 Difference]: Start difference. First operand 709 states and 786 transitions. Second operand 128 states. [2018-03-29 22:59:09,686 WARN L151 SmtUtils]: Spent 249ms on a formula simplification. DAG size of input: 316 DAG size of output 6 [2018-03-29 22:59:10,166 WARN L151 SmtUtils]: Spent 251ms on a formula simplification. DAG size of input: 311 DAG size of output 6 [2018-03-29 22:59:10,636 WARN L151 SmtUtils]: Spent 234ms on a formula simplification. DAG size of input: 306 DAG size of output 6 [2018-03-29 22:59:11,098 WARN L151 SmtUtils]: Spent 229ms on a formula simplification. DAG size of input: 301 DAG size of output 6 [2018-03-29 22:59:11,564 WARN L151 SmtUtils]: Spent 231ms on a formula simplification. DAG size of input: 296 DAG size of output 6 [2018-03-29 22:59:12,011 WARN L151 SmtUtils]: Spent 212ms on a formula simplification. DAG size of input: 291 DAG size of output 6 [2018-03-29 22:59:12,458 WARN L151 SmtUtils]: Spent 213ms on a formula simplification. DAG size of input: 286 DAG size of output 6 [2018-03-29 22:59:12,908 WARN L151 SmtUtils]: Spent 214ms on a formula simplification. DAG size of input: 281 DAG size of output 6 [2018-03-29 22:59:13,340 WARN L151 SmtUtils]: Spent 192ms on a formula simplification. DAG size of input: 276 DAG size of output 6 [2018-03-29 22:59:13,767 WARN L151 SmtUtils]: Spent 189ms on a formula simplification. DAG size of input: 271 DAG size of output 6 [2018-03-29 22:59:14,197 WARN L151 SmtUtils]: Spent 192ms on a formula simplification. DAG size of input: 266 DAG size of output 6 [2018-03-29 22:59:14,628 WARN L151 SmtUtils]: Spent 176ms on a formula simplification. DAG size of input: 261 DAG size of output 6 [2018-03-29 22:59:15,036 WARN L151 SmtUtils]: Spent 171ms on a formula simplification. DAG size of input: 256 DAG size of output 6 [2018-03-29 22:59:15,445 WARN L151 SmtUtils]: Spent 171ms on a formula simplification. DAG size of input: 251 DAG size of output 6 [2018-03-29 22:59:15,841 WARN L151 SmtUtils]: Spent 159ms on a formula simplification. DAG size of input: 246 DAG size of output 6 [2018-03-29 22:59:16,229 WARN L151 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 241 DAG size of output 6 [2018-03-29 22:59:16,614 WARN L151 SmtUtils]: Spent 145ms on a formula simplification. DAG size of input: 236 DAG size of output 6 [2018-03-29 22:59:17,006 WARN L151 SmtUtils]: Spent 153ms on a formula simplification. DAG size of input: 231 DAG size of output 6 [2018-03-29 22:59:17,384 WARN L151 SmtUtils]: Spent 137ms on a formula simplification. DAG size of input: 226 DAG size of output 6 [2018-03-29 22:59:17,756 WARN L151 SmtUtils]: Spent 136ms on a formula simplification. DAG size of input: 221 DAG size of output 6 [2018-03-29 22:59:18,116 WARN L151 SmtUtils]: Spent 126ms on a formula simplification. DAG size of input: 216 DAG size of output 6 [2018-03-29 22:59:18,482 WARN L151 SmtUtils]: Spent 136ms on a formula simplification. DAG size of input: 211 DAG size of output 6 [2018-03-29 22:59:18,832 WARN L151 SmtUtils]: Spent 118ms on a formula simplification. DAG size of input: 206 DAG size of output 6 [2018-03-29 22:59:19,181 WARN L151 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 201 DAG size of output 6 [2018-03-29 22:59:19,513 WARN L151 SmtUtils]: Spent 106ms on a formula simplification. DAG size of input: 196 DAG size of output 6 [2018-03-29 22:59:19,838 WARN L151 SmtUtils]: Spent 101ms on a formula simplification. DAG size of input: 191 DAG size of output 6 [2018-03-29 22:59:33,379 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:59:33,379 INFO L93 Difference]: Finished difference Result 29322 states and 33062 transitions. [2018-03-29 22:59:33,380 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-03-29 22:59:33,380 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 443 [2018-03-29 22:59:33,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:59:33,470 INFO L225 Difference]: With dead ends: 29322 [2018-03-29 22:59:33,470 INFO L226 Difference]: Without dead ends: 29319 [2018-03-29 22:59:33,481 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 947 GetRequests, 759 SyntacticMatches, 0 SemanticMatches, 188 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1891 ImplicationChecksByTransitivity, 21.6s TimeCoverageRelationStatistics Valid=12158, Invalid=23752, Unknown=0, NotChecked=0, Total=35910 [2018-03-29 22:59:33,499 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29319 states. [2018-03-29 22:59:34,033 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29319 to 1157. [2018-03-29 22:59:34,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 22:59:34,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1298 transitions. [2018-03-29 22:59:34,035 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1298 transitions. Word has length 443 [2018-03-29 22:59:34,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:59:34,036 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1298 transitions. [2018-03-29 22:59:34,036 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-03-29 22:59:34,036 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1298 transitions. [2018-03-29 22:59:34,039 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 500 [2018-03-29 22:59:34,039 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:59:34,040 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 17, 17, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:59:34,040 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:59:34,040 INFO L82 PathProgramCache]: Analyzing trace with hash 2049086648, now seen corresponding path program 20 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:59:34,049 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:59:34,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:59:34,128 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:59:35,063 INFO L134 CoverageAnalysis]: Checked inductivity of 6561 backedges. 3918 proven. 888 refuted. 0 times theorem prover too weak. 1755 trivial. 0 not checked. [2018-03-29 22:59:35,063 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:59:36,048 INFO L134 CoverageAnalysis]: Checked inductivity of 6561 backedges. 2958 proven. 888 refuted. 0 times theorem prover too weak. 2715 trivial. 0 not checked. [2018-03-29 22:59:36,068 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:59:36,069 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [52, 52] total 85 [2018-03-29 22:59:36,069 INFO L442 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-03-29 22:59:36,069 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-03-29 22:59:36,070 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1137, Invalid=6003, Unknown=0, NotChecked=0, Total=7140 [2018-03-29 22:59:36,070 INFO L87 Difference]: Start difference. First operand 1157 states and 1298 transitions. Second operand 85 states. [2018-03-29 22:59:37,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:59:37,330 INFO L93 Difference]: Finished difference Result 1417 states and 1588 transitions. [2018-03-29 22:59:37,330 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-03-29 22:59:37,330 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 499 [2018-03-29 22:59:37,330 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:59:37,332 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 22:59:37,333 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 22:59:37,334 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1029 GetRequests, 897 SyntacticMatches, 17 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3517 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=2849, Invalid=10723, Unknown=0, NotChecked=0, Total=13572 [2018-03-29 22:59:37,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 22:59:37,532 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 22:59:37,532 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 22:59:37,533 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1297 transitions. [2018-03-29 22:59:37,533 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1297 transitions. Word has length 499 [2018-03-29 22:59:37,534 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:59:37,534 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1297 transitions. [2018-03-29 22:59:37,534 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-03-29 22:59:37,534 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1297 transitions. [2018-03-29 22:59:37,536 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 507 [2018-03-29 22:59:37,536 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:59:37,537 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 18, 18, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:59:37,537 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:59:37,537 INFO L82 PathProgramCache]: Analyzing trace with hash -47116648, now seen corresponding path program 21 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:59:37,542 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:59:37,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:59:37,619 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:59:38,627 INFO L134 CoverageAnalysis]: Checked inductivity of 6676 backedges. 4023 proven. 1003 refuted. 0 times theorem prover too weak. 1650 trivial. 0 not checked. [2018-03-29 22:59:38,628 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:59:39,768 INFO L134 CoverageAnalysis]: Checked inductivity of 6676 backedges. 3071 proven. 1003 refuted. 0 times theorem prover too weak. 2602 trivial. 0 not checked. [2018-03-29 22:59:39,814 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:59:39,814 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 55] total 90 [2018-03-29 22:59:39,815 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-03-29 22:59:39,816 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-03-29 22:59:39,816 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1267, Invalid=6743, Unknown=0, NotChecked=0, Total=8010 [2018-03-29 22:59:39,816 INFO L87 Difference]: Start difference. First operand 1157 states and 1297 transitions. Second operand 90 states. [2018-03-29 22:59:41,257 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:59:41,257 INFO L93 Difference]: Finished difference Result 1417 states and 1587 transitions. [2018-03-29 22:59:41,258 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-03-29 22:59:41,258 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 506 [2018-03-29 22:59:41,258 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:59:41,260 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 22:59:41,260 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 22:59:41,263 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1045 GetRequests, 905 SyntacticMatches, 18 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3966 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=3188, Invalid=12064, Unknown=0, NotChecked=0, Total=15252 [2018-03-29 22:59:41,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 22:59:41,471 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 22:59:41,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 22:59:41,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1296 transitions. [2018-03-29 22:59:41,473 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1296 transitions. Word has length 506 [2018-03-29 22:59:41,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:59:41,473 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1296 transitions. [2018-03-29 22:59:41,473 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-03-29 22:59:41,473 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1296 transitions. [2018-03-29 22:59:41,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 514 [2018-03-29 22:59:41,476 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:59:41,476 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 19, 19, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:59:41,476 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:59:41,477 INFO L82 PathProgramCache]: Analyzing trace with hash -509626184, now seen corresponding path program 22 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:59:41,482 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:59:41,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:59:41,557 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:59:42,512 INFO L134 CoverageAnalysis]: Checked inductivity of 6798 backedges. 4112 proven. 1125 refuted. 0 times theorem prover too weak. 1561 trivial. 0 not checked. [2018-03-29 22:59:42,512 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:59:43,784 INFO L134 CoverageAnalysis]: Checked inductivity of 6798 backedges. 3176 proven. 1125 refuted. 0 times theorem prover too weak. 2497 trivial. 0 not checked. [2018-03-29 22:59:43,808 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:59:43,821 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [58, 58] total 95 [2018-03-29 22:59:43,822 INFO L442 AbstractCegarLoop]: Interpolant automaton has 95 states [2018-03-29 22:59:43,822 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 95 interpolants. [2018-03-29 22:59:43,822 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1404, Invalid=7526, Unknown=0, NotChecked=0, Total=8930 [2018-03-29 22:59:43,822 INFO L87 Difference]: Start difference. First operand 1157 states and 1296 transitions. Second operand 95 states. [2018-03-29 22:59:45,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:59:45,311 INFO L93 Difference]: Finished difference Result 1417 states and 1586 transitions. [2018-03-29 22:59:45,311 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2018-03-29 22:59:45,311 INFO L78 Accepts]: Start accepts. Automaton has 95 states. Word has length 513 [2018-03-29 22:59:45,312 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:59:45,314 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 22:59:45,314 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 22:59:45,316 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1061 GetRequests, 913 SyntacticMatches, 19 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4442 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=3546, Invalid=13484, Unknown=0, NotChecked=0, Total=17030 [2018-03-29 22:59:45,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 22:59:45,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 22:59:45,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 22:59:45,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1295 transitions. [2018-03-29 22:59:45,563 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1295 transitions. Word has length 513 [2018-03-29 22:59:45,563 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:59:45,563 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1295 transitions. [2018-03-29 22:59:45,563 INFO L460 AbstractCegarLoop]: Interpolant automaton has 95 states. [2018-03-29 22:59:45,563 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1295 transitions. [2018-03-29 22:59:45,567 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 521 [2018-03-29 22:59:45,567 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:59:45,567 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 20, 20, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:59:45,567 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:59:45,568 INFO L82 PathProgramCache]: Analyzing trace with hash 1231252120, now seen corresponding path program 23 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:59:45,576 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:59:45,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:59:45,665 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:59:47,029 INFO L134 CoverageAnalysis]: Checked inductivity of 6927 backedges. 4185 proven. 1254 refuted. 0 times theorem prover too weak. 1488 trivial. 0 not checked. [2018-03-29 22:59:47,030 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:59:48,313 INFO L134 CoverageAnalysis]: Checked inductivity of 6927 backedges. 3273 proven. 1254 refuted. 0 times theorem prover too weak. 2400 trivial. 0 not checked. [2018-03-29 22:59:48,334 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:59:48,334 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 100 [2018-03-29 22:59:48,335 INFO L442 AbstractCegarLoop]: Interpolant automaton has 100 states [2018-03-29 22:59:48,335 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 100 interpolants. [2018-03-29 22:59:48,336 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1548, Invalid=8352, Unknown=0, NotChecked=0, Total=9900 [2018-03-29 22:59:48,336 INFO L87 Difference]: Start difference. First operand 1157 states and 1295 transitions. Second operand 100 states. [2018-03-29 22:59:50,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:59:50,038 INFO L93 Difference]: Finished difference Result 1417 states and 1585 transitions. [2018-03-29 22:59:50,038 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2018-03-29 22:59:50,038 INFO L78 Accepts]: Start accepts. Automaton has 100 states. Word has length 520 [2018-03-29 22:59:50,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:59:50,040 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 22:59:50,041 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 22:59:50,043 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1077 GetRequests, 921 SyntacticMatches, 20 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4945 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=3923, Invalid=14983, Unknown=0, NotChecked=0, Total=18906 [2018-03-29 22:59:50,044 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 22:59:50,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 22:59:50,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 22:59:50,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1294 transitions. [2018-03-29 22:59:50,209 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1294 transitions. Word has length 520 [2018-03-29 22:59:50,209 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:59:50,209 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1294 transitions. [2018-03-29 22:59:50,209 INFO L460 AbstractCegarLoop]: Interpolant automaton has 100 states. [2018-03-29 22:59:50,209 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1294 transitions. [2018-03-29 22:59:50,213 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 528 [2018-03-29 22:59:50,213 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:59:50,213 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 21, 21, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:59:50,213 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:59:50,214 INFO L82 PathProgramCache]: Analyzing trace with hash -984752968, now seen corresponding path program 24 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:59:50,221 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:59:50,272 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:59:50,278 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:59:51,356 INFO L134 CoverageAnalysis]: Checked inductivity of 7063 backedges. 4242 proven. 1390 refuted. 0 times theorem prover too weak. 1431 trivial. 0 not checked. [2018-03-29 22:59:51,356 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:59:52,787 INFO L134 CoverageAnalysis]: Checked inductivity of 7063 backedges. 3362 proven. 1390 refuted. 0 times theorem prover too weak. 2311 trivial. 0 not checked. [2018-03-29 22:59:52,808 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:59:52,808 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 105 [2018-03-29 22:59:52,808 INFO L442 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-03-29 22:59:52,809 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-03-29 22:59:52,809 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1699, Invalid=9221, Unknown=0, NotChecked=0, Total=10920 [2018-03-29 22:59:52,809 INFO L87 Difference]: Start difference. First operand 1157 states and 1294 transitions. Second operand 105 states. [2018-03-29 22:59:54,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:59:54,449 INFO L93 Difference]: Finished difference Result 1417 states and 1584 transitions. [2018-03-29 22:59:54,449 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-03-29 22:59:54,449 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 527 [2018-03-29 22:59:54,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:59:54,451 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 22:59:54,451 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 22:59:54,453 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1093 GetRequests, 929 SyntacticMatches, 21 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5475 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=4319, Invalid=16561, Unknown=0, NotChecked=0, Total=20880 [2018-03-29 22:59:54,454 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 22:59:54,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 22:59:54,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 22:59:54,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1293 transitions. [2018-03-29 22:59:54,598 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1293 transitions. Word has length 527 [2018-03-29 22:59:54,599 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:59:54,599 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1293 transitions. [2018-03-29 22:59:54,599 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-03-29 22:59:54,599 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1293 transitions. [2018-03-29 22:59:54,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 535 [2018-03-29 22:59:54,601 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:59:54,601 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 22, 22, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:59:54,601 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:59:54,602 INFO L82 PathProgramCache]: Analyzing trace with hash 809813656, now seen corresponding path program 25 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:59:54,607 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:59:54,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:59:54,664 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 22:59:55,805 INFO L134 CoverageAnalysis]: Checked inductivity of 7206 backedges. 4283 proven. 1533 refuted. 0 times theorem prover too weak. 1390 trivial. 0 not checked. [2018-03-29 22:59:55,805 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 22:59:57,384 INFO L134 CoverageAnalysis]: Checked inductivity of 7206 backedges. 3443 proven. 1533 refuted. 0 times theorem prover too weak. 2230 trivial. 0 not checked. [2018-03-29 22:59:57,405 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 22:59:57,405 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67, 67] total 110 [2018-03-29 22:59:57,406 INFO L442 AbstractCegarLoop]: Interpolant automaton has 110 states [2018-03-29 22:59:57,407 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 110 interpolants. [2018-03-29 22:59:57,408 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1857, Invalid=10133, Unknown=0, NotChecked=0, Total=11990 [2018-03-29 22:59:57,408 INFO L87 Difference]: Start difference. First operand 1157 states and 1293 transitions. Second operand 110 states. [2018-03-29 22:59:59,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 22:59:59,311 INFO L93 Difference]: Finished difference Result 1417 states and 1583 transitions. [2018-03-29 22:59:59,311 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 88 states. [2018-03-29 22:59:59,311 INFO L78 Accepts]: Start accepts. Automaton has 110 states. Word has length 534 [2018-03-29 22:59:59,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 22:59:59,312 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 22:59:59,312 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 22:59:59,314 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1109 GetRequests, 937 SyntacticMatches, 22 SemanticMatches, 150 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6032 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=4734, Invalid=18218, Unknown=0, NotChecked=0, Total=22952 [2018-03-29 22:59:59,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 22:59:59,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 22:59:59,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 22:59:59,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1292 transitions. [2018-03-29 22:59:59,451 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1292 transitions. Word has length 534 [2018-03-29 22:59:59,451 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 22:59:59,451 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1292 transitions. [2018-03-29 22:59:59,451 INFO L460 AbstractCegarLoop]: Interpolant automaton has 110 states. [2018-03-29 22:59:59,451 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1292 transitions. [2018-03-29 22:59:59,453 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 542 [2018-03-29 22:59:59,454 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 22:59:59,454 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 23, 23, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 22:59:59,454 INFO L408 AbstractCegarLoop]: === Iteration 34 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 22:59:59,454 INFO L82 PathProgramCache]: Analyzing trace with hash 2070741176, now seen corresponding path program 26 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 35 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 35 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 22:59:59,460 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 22:59:59,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 22:59:59,517 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 23:00:00,747 INFO L134 CoverageAnalysis]: Checked inductivity of 7356 backedges. 4308 proven. 1683 refuted. 0 times theorem prover too weak. 1365 trivial. 0 not checked. [2018-03-29 23:00:00,747 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 23:00:02,492 INFO L134 CoverageAnalysis]: Checked inductivity of 7356 backedges. 3516 proven. 1683 refuted. 0 times theorem prover too weak. 2157 trivial. 0 not checked. [2018-03-29 23:00:02,513 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 23:00:02,513 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [70, 70] total 115 [2018-03-29 23:00:02,514 INFO L442 AbstractCegarLoop]: Interpolant automaton has 115 states [2018-03-29 23:00:02,514 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 115 interpolants. [2018-03-29 23:00:02,515 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2022, Invalid=11088, Unknown=0, NotChecked=0, Total=13110 [2018-03-29 23:00:02,515 INFO L87 Difference]: Start difference. First operand 1157 states and 1292 transitions. Second operand 115 states. [2018-03-29 23:00:04,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 23:00:04,529 INFO L93 Difference]: Finished difference Result 1417 states and 1582 transitions. [2018-03-29 23:00:04,529 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 92 states. [2018-03-29 23:00:04,529 INFO L78 Accepts]: Start accepts. Automaton has 115 states. Word has length 541 [2018-03-29 23:00:04,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 23:00:04,530 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 23:00:04,530 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 23:00:04,532 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1125 GetRequests, 945 SyntacticMatches, 23 SemanticMatches, 157 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6616 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=5168, Invalid=19954, Unknown=0, NotChecked=0, Total=25122 [2018-03-29 23:00:04,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 23:00:04,666 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 23:00:04,667 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 23:00:04,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1291 transitions. [2018-03-29 23:00:04,668 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1291 transitions. Word has length 541 [2018-03-29 23:00:04,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 23:00:04,668 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1291 transitions. [2018-03-29 23:00:04,668 INFO L460 AbstractCegarLoop]: Interpolant automaton has 115 states. [2018-03-29 23:00:04,668 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1291 transitions. [2018-03-29 23:00:04,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 549 [2018-03-29 23:00:04,671 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 23:00:04,671 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 24, 24, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 23:00:04,671 INFO L408 AbstractCegarLoop]: === Iteration 35 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 23:00:04,671 INFO L82 PathProgramCache]: Analyzing trace with hash -745201000, now seen corresponding path program 27 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 36 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 36 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 23:00:04,676 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 23:00:04,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 23:00:04,734 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 23:00:06,103 INFO L134 CoverageAnalysis]: Checked inductivity of 7513 backedges. 4317 proven. 1840 refuted. 0 times theorem prover too weak. 1356 trivial. 0 not checked. [2018-03-29 23:00:06,103 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 23:00:08,246 INFO L134 CoverageAnalysis]: Checked inductivity of 7513 backedges. 3581 proven. 1840 refuted. 0 times theorem prover too weak. 2092 trivial. 0 not checked. [2018-03-29 23:00:08,267 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 23:00:08,268 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 120 [2018-03-29 23:00:08,268 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-03-29 23:00:08,269 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-03-29 23:00:08,270 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2194, Invalid=12086, Unknown=0, NotChecked=0, Total=14280 [2018-03-29 23:00:08,270 INFO L87 Difference]: Start difference. First operand 1157 states and 1291 transitions. Second operand 120 states. [2018-03-29 23:00:10,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 23:00:10,504 INFO L93 Difference]: Finished difference Result 1417 states and 1581 transitions. [2018-03-29 23:00:10,504 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-03-29 23:00:10,504 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 548 [2018-03-29 23:00:10,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 23:00:10,505 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 23:00:10,505 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 23:00:10,507 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1141 GetRequests, 953 SyntacticMatches, 24 SemanticMatches, 164 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7227 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=5621, Invalid=21769, Unknown=0, NotChecked=0, Total=27390 [2018-03-29 23:00:10,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 23:00:10,642 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 23:00:10,642 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 23:00:10,643 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1290 transitions. [2018-03-29 23:00:10,643 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1290 transitions. Word has length 548 [2018-03-29 23:00:10,643 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 23:00:10,643 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1290 transitions. [2018-03-29 23:00:10,643 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-03-29 23:00:10,643 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1290 transitions. [2018-03-29 23:00:10,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 556 [2018-03-29 23:00:10,646 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 23:00:10,646 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 25, 25, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 23:00:10,646 INFO L408 AbstractCegarLoop]: === Iteration 36 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 23:00:10,646 INFO L82 PathProgramCache]: Analyzing trace with hash 1782391992, now seen corresponding path program 28 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 37 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 37 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 23:00:10,652 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 23:00:10,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 23:00:10,710 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 23:00:12,075 INFO L134 CoverageAnalysis]: Checked inductivity of 7677 backedges. 4310 proven. 2004 refuted. 0 times theorem prover too weak. 1363 trivial. 0 not checked. [2018-03-29 23:00:12,075 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 23:00:14,007 INFO L134 CoverageAnalysis]: Checked inductivity of 7677 backedges. 3638 proven. 2004 refuted. 0 times theorem prover too weak. 2035 trivial. 0 not checked. [2018-03-29 23:00:14,032 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 23:00:14,032 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [76, 76] total 125 [2018-03-29 23:00:14,033 INFO L442 AbstractCegarLoop]: Interpolant automaton has 125 states [2018-03-29 23:00:14,033 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 125 interpolants. [2018-03-29 23:00:14,034 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2373, Invalid=13127, Unknown=0, NotChecked=0, Total=15500 [2018-03-29 23:00:14,034 INFO L87 Difference]: Start difference. First operand 1157 states and 1290 transitions. Second operand 125 states. [2018-03-29 23:00:16,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 23:00:16,175 INFO L93 Difference]: Finished difference Result 1417 states and 1580 transitions. [2018-03-29 23:00:16,175 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-03-29 23:00:16,175 INFO L78 Accepts]: Start accepts. Automaton has 125 states. Word has length 555 [2018-03-29 23:00:16,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 23:00:16,176 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 23:00:16,176 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 23:00:16,179 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1157 GetRequests, 961 SyntacticMatches, 25 SemanticMatches, 171 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7865 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=6093, Invalid=23663, Unknown=0, NotChecked=0, Total=29756 [2018-03-29 23:00:16,180 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 23:00:16,336 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 23:00:16,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 23:00:16,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1289 transitions. [2018-03-29 23:00:16,337 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1289 transitions. Word has length 555 [2018-03-29 23:00:16,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 23:00:16,337 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1289 transitions. [2018-03-29 23:00:16,337 INFO L460 AbstractCegarLoop]: Interpolant automaton has 125 states. [2018-03-29 23:00:16,337 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1289 transitions. [2018-03-29 23:00:16,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 563 [2018-03-29 23:00:16,340 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 23:00:16,340 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 26, 26, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 23:00:16,340 INFO L408 AbstractCegarLoop]: === Iteration 37 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 23:00:16,340 INFO L82 PathProgramCache]: Analyzing trace with hash 1158971032, now seen corresponding path program 29 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 38 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 38 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 23:00:16,346 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 23:00:16,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 23:00:16,406 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 23:00:17,868 INFO L134 CoverageAnalysis]: Checked inductivity of 7848 backedges. 4287 proven. 2175 refuted. 0 times theorem prover too weak. 1386 trivial. 0 not checked. [2018-03-29 23:00:17,869 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-29 23:00:19,975 INFO L134 CoverageAnalysis]: Checked inductivity of 7848 backedges. 3687 proven. 2175 refuted. 0 times theorem prover too weak. 1986 trivial. 0 not checked. [2018-03-29 23:00:19,997 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-29 23:00:19,997 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [79, 79] total 130 [2018-03-29 23:00:19,998 INFO L442 AbstractCegarLoop]: Interpolant automaton has 130 states [2018-03-29 23:00:19,998 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 130 interpolants. [2018-03-29 23:00:19,999 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2559, Invalid=14211, Unknown=0, NotChecked=0, Total=16770 [2018-03-29 23:00:19,999 INFO L87 Difference]: Start difference. First operand 1157 states and 1289 transitions. Second operand 130 states. [2018-03-29 23:00:22,474 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-29 23:00:22,474 INFO L93 Difference]: Finished difference Result 1417 states and 1579 transitions. [2018-03-29 23:00:22,474 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 104 states. [2018-03-29 23:00:22,474 INFO L78 Accepts]: Start accepts. Automaton has 130 states. Word has length 562 [2018-03-29 23:00:22,475 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-29 23:00:22,476 INFO L225 Difference]: With dead ends: 1417 [2018-03-29 23:00:22,476 INFO L226 Difference]: Without dead ends: 1157 [2018-03-29 23:00:22,478 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1173 GetRequests, 969 SyntacticMatches, 26 SemanticMatches, 178 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8530 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=6584, Invalid=25636, Unknown=0, NotChecked=0, Total=32220 [2018-03-29 23:00:22,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-29 23:00:22,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-29 23:00:22,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-29 23:00:22,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1288 transitions. [2018-03-29 23:00:22,642 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1288 transitions. Word has length 562 [2018-03-29 23:00:22,642 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-29 23:00:22,643 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1288 transitions. [2018-03-29 23:00:22,643 INFO L460 AbstractCegarLoop]: Interpolant automaton has 130 states. [2018-03-29 23:00:22,643 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1288 transitions. [2018-03-29 23:00:22,645 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 570 [2018-03-29 23:00:22,645 INFO L347 BasicCegarLoop]: Found error trace [2018-03-29 23:00:22,645 INFO L355 BasicCegarLoop]: trace histogram [32, 32, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 27, 27, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-29 23:00:22,646 INFO L408 AbstractCegarLoop]: === Iteration 38 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-29 23:00:22,646 INFO L82 PathProgramCache]: Analyzing trace with hash 134105272, now seen corresponding path program 30 times No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 39 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 39 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-29 23:00:22,653 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-29 23:00:22,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-29 23:00:22,726 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-29 23:00:24,284 INFO L134 CoverageAnalysis]: Checked inductivity of 8026 backedges. 4248 proven. 2353 refuted. 0 times theorem prover too weak. 1425 trivial. 0 not checked. [2018-03-29 23:00:24,284 INFO L314 TraceCheckSpWp]: Computing backward predicates... Received shutdown request... [2018-03-29 23:00:24,406 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-03-29 23:00:24,407 WARN L519 AbstractCegarLoop]: Verification canceled [2018-03-29 23:00:24,410 WARN L197 ceAbstractionStarter]: Timeout [2018-03-29 23:00:24,410 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 29.03 11:00:24 BasicIcfg [2018-03-29 23:00:24,410 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-03-29 23:00:24,411 INFO L168 Benchmark]: Toolchain (without parser) took 125208.34 ms. Allocated memory was 302.0 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 244.2 MB in the beginning and 370.7 MB in the end (delta: -126.5 MB). Peak memory consumption was 940.4 MB. Max. memory is 5.3 GB. [2018-03-29 23:00:24,412 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 302.0 MB. Free memory is still 264.2 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-03-29 23:00:24,412 INFO L168 Benchmark]: CACSL2BoogieTranslator took 183.48 ms. Allocated memory is still 302.0 MB. Free memory was 244.2 MB in the beginning and 235.1 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 5.3 GB. [2018-03-29 23:00:24,413 INFO L168 Benchmark]: Boogie Preprocessor took 22.55 ms. Allocated memory is still 302.0 MB. Free memory was 235.1 MB in the beginning and 233.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-03-29 23:00:24,413 INFO L168 Benchmark]: RCFGBuilder took 267.37 ms. Allocated memory was 302.0 MB in the beginning and 460.8 MB in the end (delta: 158.9 MB). Free memory was 233.1 MB in the beginning and 430.6 MB in the end (delta: -197.5 MB). Peak memory consumption was 22.1 MB. Max. memory is 5.3 GB. [2018-03-29 23:00:24,413 INFO L168 Benchmark]: IcfgTransformer took 34.44 ms. Allocated memory is still 460.8 MB. Free memory was 430.6 MB in the beginning and 426.7 MB in the end (delta: 3.9 MB). Peak memory consumption was 3.9 MB. Max. memory is 5.3 GB. [2018-03-29 23:00:24,414 INFO L168 Benchmark]: TraceAbstraction took 124694.06 ms. Allocated memory was 460.8 MB in the beginning and 1.4 GB in the end (delta: 908.1 MB). Free memory was 426.7 MB in the beginning and 370.7 MB in the end (delta: 56.0 MB). Peak memory consumption was 964.1 MB. Max. memory is 5.3 GB. [2018-03-29 23:00:24,416 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.19 ms. Allocated memory is still 302.0 MB. Free memory is still 264.2 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 183.48 ms. Allocated memory is still 302.0 MB. Free memory was 244.2 MB in the beginning and 235.1 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 22.55 ms. Allocated memory is still 302.0 MB. Free memory was 235.1 MB in the beginning and 233.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 267.37 ms. Allocated memory was 302.0 MB in the beginning and 460.8 MB in the end (delta: 158.9 MB). Free memory was 233.1 MB in the beginning and 430.6 MB in the end (delta: -197.5 MB). Peak memory consumption was 22.1 MB. Max. memory is 5.3 GB. * IcfgTransformer took 34.44 ms. Allocated memory is still 460.8 MB. Free memory was 430.6 MB in the beginning and 426.7 MB in the end (delta: 3.9 MB). Peak memory consumption was 3.9 MB. Max. memory is 5.3 GB. * TraceAbstraction took 124694.06 ms. Allocated memory was 460.8 MB in the beginning and 1.4 GB in the end (delta: 908.1 MB). Free memory was 426.7 MB in the beginning and 370.7 MB in the end (delta: 56.0 MB). Peak memory consumption was 964.1 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 13]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 13). Cancelled while BasicCegarLoop was analyzing trace of length 570 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 86 known predicates. - TimeoutResultAtElement [Line: 13]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 13). Cancelled while BasicCegarLoop was analyzing trace of length 570 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 86 known predicates. - TimeoutResultAtElement [Line: 8]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 8). Cancelled while BasicCegarLoop was analyzing trace of length 570 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 86 known predicates. - TimeoutResultAtElement [Line: 8]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 8). Cancelled while BasicCegarLoop was analyzing trace of length 570 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 86 known predicates. - TimeoutResultAtElement [Line: 7]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 7). Cancelled while BasicCegarLoop was analyzing trace of length 570 with TraceHistMax 32, while TraceCheckSpWp was constructing backward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 86 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 39 locations, 5 error locations. TIMEOUT Result, 124.6s OverallTime, 38 OverallIterations, 63 TraceHistogramMax, 69.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 4663 SDtfs, 41664 SDslu, 98124 SDs, 0 SdLazy, 57643 SolverSat, 6498 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 17.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 20265 GetRequests, 16967 SyntacticMatches, 351 SemanticMatches, 2947 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82577 ImplicationChecksByTransitivity, 78.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=1157occurred in iteration=27, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 3.0s AutomataMinimizationTime, 37 MinimizatonAttempts, 37267 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 47.9s InterpolantComputationTime, 9706 NumberOfCodeBlocks, 9706 NumberOfCodeBlocksAsserted, 37 NumberOfCheckSat, 19338 ConstructedInterpolants, 0 QuantifiedInterpolants, 25960444 SizeOfPredicates, 754 NumberOfNonLiveVariables, 13448 ConjunctsInSsa, 1418 ConjunctsInUnsatCore, 74 InterpolantComputations, 6 PerfectInterpolantSequences, 140098/215186 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/standard_strcpy_false-valid-deref_ground.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerCTransformed.xml/Csv-Benchmark-0-2018-03-29_23-00-24-426.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/standard_strcpy_false-valid-deref_ground.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerCTransformed.xml/Csv-TraceAbstractionBenchmarks-0-2018-03-29_23-00-24-426.csv Completed graceful shutdown