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/loop-acceleration/array3_false-valid-deref.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-4cf2d92 [2018-03-28 15:52:26,393 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-03-28 15:52:26,395 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-03-28 15:52:26,409 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-03-28 15:52:26,410 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-03-28 15:52:26,411 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-03-28 15:52:26,412 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-03-28 15:52:26,413 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-03-28 15:52:26,415 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-03-28 15:52:26,416 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-03-28 15:52:26,417 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-03-28 15:52:26,417 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-03-28 15:52:26,418 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-03-28 15:52:26,419 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-03-28 15:52:26,420 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-03-28 15:52:26,422 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-03-28 15:52:26,424 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-03-28 15:52:26,425 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-03-28 15:52:26,427 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-03-28 15:52:26,428 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-03-28 15:52:26,430 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-03-28 15:52:26,430 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-03-28 15:52:26,430 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-03-28 15:52:26,431 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-03-28 15:52:26,432 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-03-28 15:52:26,433 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-03-28 15:52:26,434 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-03-28 15:52:26,434 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-03-28 15:52:26,435 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-03-28 15:52:26,435 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-03-28 15:52:26,436 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-03-28 15:52:26,436 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-28 15:52:26,459 INFO L110 SettingsManager]: Loading preferences was successful [2018-03-28 15:52:26,459 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-03-28 15:52:26,459 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-03-28 15:52:26,459 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-03-28 15:52:26,460 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-03-28 15:52:26,460 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-03-28 15:52:26,460 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-03-28 15:52:26,461 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-03-28 15:52:26,461 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-03-28 15:52:26,461 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-03-28 15:52:26,461 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-03-28 15:52:26,462 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-03-28 15:52:26,462 INFO L133 SettingsManager]: * sizeof long=4 [2018-03-28 15:52:26,462 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-03-28 15:52:26,462 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-03-28 15:52:26,462 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-03-28 15:52:26,463 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-03-28 15:52:26,463 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-03-28 15:52:26,463 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-03-28 15:52:26,463 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-03-28 15:52:26,463 INFO L133 SettingsManager]: * sizeof long double=12 [2018-03-28 15:52:26,463 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-03-28 15:52:26,464 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-03-28 15:52:26,464 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-03-28 15:52:26,464 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-03-28 15:52:26,464 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-03-28 15:52:26,464 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-03-28 15:52:26,465 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-03-28 15:52:26,465 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-03-28 15:52:26,465 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-03-28 15:52:26,465 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-03-28 15:52:26,465 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-28 15:52:26,465 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-03-28 15:52:26,466 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-03-28 15:52:26,466 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-03-28 15:52:26,467 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-03-28 15:52:26,467 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-03-28 15:52:26,500 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-03-28 15:52:26,512 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-03-28 15:52:26,517 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-03-28 15:52:26,518 INFO L271 PluginConnector]: Initializing CDTParser... [2018-03-28 15:52:26,519 INFO L276 PluginConnector]: CDTParser initialized [2018-03-28 15:52:26,519 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/loop-acceleration/array3_false-valid-deref.i [2018-03-28 15:52:26,848 INFO L228 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGc00c34410 [2018-03-28 15:52:26,949 INFO L291 CDTParser]: IsIndexed: true [2018-03-28 15:52:26,949 INFO L292 CDTParser]: Found 1 translation units. [2018-03-28 15:52:26,949 INFO L171 CDTParser]: Scanning array3_false-valid-deref.i [2018-03-28 15:52:26,950 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-03-28 15:52:26,951 INFO L215 ultiparseSymbolTable]: [2018-03-28 15:52:26,951 INFO L218 ultiparseSymbolTable]: Function table: [2018-03-28 15:52:26,951 INFO L221 ultiparseSymbolTable]: Function definition of __U_MULTI_farray__false_valid_deref_i____VERIFIER_assert ('__VERIFIER_assert') in array3_false-valid-deref.i [2018-03-28 15:52:26,951 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in array3_false-valid-deref.i [2018-03-28 15:52:26,951 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-03-28 15:52:26,951 INFO L233 ultiparseSymbolTable]: [2018-03-28 15:52:26,966 INFO L334 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAGc00c34410 [2018-03-28 15:52:26,970 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-03-28 15:52:26,973 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-03-28 15:52:26,974 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-03-28 15:52:26,974 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-03-28 15:52:26,981 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-03-28 15:52:26,982 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.03 03:52:26" (1/1) ... [2018-03-28 15:52:26,984 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1f27b4fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:26, skipping insertion in model container [2018-03-28 15:52:26,984 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.03 03:52:26" (1/1) ... [2018-03-28 15:52:26,997 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-28 15:52:27,008 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-28 15:52:27,136 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-28 15:52:27,151 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-28 15:52:27,155 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 6 non ball SCCs. Number of states in SCCs 6. [2018-03-28 15:52:27,161 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27 WrapperNode [2018-03-28 15:52:27,161 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-03-28 15:52:27,162 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-03-28 15:52:27,162 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-03-28 15:52:27,162 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-03-28 15:52:27,172 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,173 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,177 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,177 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,178 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,183 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,183 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,184 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-03-28 15:52:27,185 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-03-28 15:52:27,185 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-03-28 15:52:27,185 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-03-28 15:52:27,185 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (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-28 15:52:27,240 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-03-28 15:52:27,240 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-03-28 15:52:27,240 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_farray__false_valid_deref_i____VERIFIER_assert [2018-03-28 15:52:27,240 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-03-28 15:52:27,240 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-03-28 15:52:27,241 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-03-28 15:52:27,241 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_farray__false_valid_deref_i____VERIFIER_assert [2018-03-28 15:52:27,241 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-03-28 15:52:27,241 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-03-28 15:52:27,241 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-03-28 15:52:27,434 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-03-28 15:52:27,434 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.03 03:52:27 BoogieIcfgContainer [2018-03-28 15:52:27,435 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-03-28 15:52:27,435 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-03-28 15:52:27,435 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-03-28 15:52:27,436 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-03-28 15:52:27,439 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.03 03:52:27" (1/1) ... [2018-03-28 15:52:27,444 WARN L218 ansformationObserver]: HeapSeparator: input icfg has no '#valid' array -- returning unchanged Icfg! [2018-03-28 15:52:27,451 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,452 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,452 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,453 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,453 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_~A~0=v_main_~A~0_1} AuxVars[] AssignedVars[main_~A~0] [2018-03-28 15:52:27,454 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_~i~0=v_main_~i~0_1} AuxVars[] AssignedVars[main_~i~0] [2018-03-28 15:52:27,454 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~i~0_2 0) InVars {} OutVars{main_~i~0=v_main_~i~0_2} AuxVars[] AssignedVars[main_~i~0] [2018-03-28 15:52:27,454 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,454 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: false InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,455 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (not (< v_main_~i~0_3 1024)) InVars {main_~i~0=v_main_~i~0_3} OutVars{main_~i~0=v_main_~i~0_3} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,455 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (< v_main_~i~0_4 1024) InVars {main_~i~0=v_main_~i~0_4} OutVars{main_~i~0=v_main_~i~0_4} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,455 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~i~0_9 0) InVars {} OutVars{main_~i~0=v_main_~i~0_9} AuxVars[] AssignedVars[main_~i~0] [2018-03-28 15:52:27,456 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (or (not (< v_main_~i~0_5 1024)) (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-28 15:52:27,456 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,456 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,456 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: false InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,457 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (and (<= 0 (+ |v_main_#t~nondet1_1| 2147483648)) (<= |v_main_#t~nondet1_1| 2147483647)) InVars {main_#t~nondet1=|v_main_#t~nondet1_1|} OutVars{main_#t~nondet1=|v_main_#t~nondet1_1|} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,457 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (or (not (< v_main_~i~0_10 1024)) (not (<= 0 v_main_~i~0_10))) InVars {main_~i~0=v_main_~i~0_10} OutVars{main_~i~0=v_main_~i~0_10} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,457 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,458 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= |v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~condInParam_1| (ite (<= v_main_~i~0_18 1024) 1 0)) InVars {main_~i~0=v_main_~i~0_18} OutVars{__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond=|v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~condInParam_1|} AuxVars[] AssignedVars[__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond] [2018-03-28 15:52:27,458 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~A~0_2 (store v_main_~A~0_3 v_main_~i~0_6 |v_main_#t~nondet1_2|)) InVars {main_#t~nondet1=|v_main_#t~nondet1_2|, main_~i~0=v_main_~i~0_6, main_~A~0=v_main_~A~0_3} OutVars{main_#t~nondet1=|v_main_#t~nondet1_2|, main_~i~0=v_main_~i~0_6, main_~A~0=v_main_~A~0_2} AuxVars[] AssignedVars[main_~A~0] [2018-03-28 15:52:27,458 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= (select v_main_~A~0_4 v_main_~i~0_11) 0) InVars {main_~i~0=v_main_~i~0_11, main_~A~0=v_main_~A~0_4} OutVars{main_~i~0=v_main_~i~0_11, main_~A~0=v_main_~A~0_4} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,459 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (not (= (select v_main_~A~0_5 v_main_~i~0_12) 0)) InVars {main_~i~0=v_main_~i~0_12, main_~A~0=v_main_~A~0_5} OutVars{main_~i~0=v_main_~i~0_12, main_~A~0=v_main_~A~0_5} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,459 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,459 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_1 |v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond_1|) InVars {__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond=|v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond_1|} OutVars{__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond=|v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond_1|, __U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond=v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_1} AuxVars[] AssignedVars[__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond] [2018-03-28 15:52:27,460 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_#t~nondet1=|v_main_#t~nondet1_3|} AuxVars[] AssignedVars[main_#t~nondet1] [2018-03-28 15:52:27,460 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (<= 1024 v_main_~i~0_13) InVars {main_~i~0=v_main_~i~0_13} OutVars{main_~i~0=v_main_~i~0_13} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,460 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (not (<= 1024 v_main_~i~0_14)) InVars {main_~i~0=v_main_~i~0_14} OutVars{main_~i~0=v_main_~i~0_14} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,460 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_2 0) InVars {__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond=v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_2} OutVars{__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond=v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_2} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,461 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (not (= v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_3 0)) InVars {__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond=v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_3} OutVars{__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond=v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_~cond_3} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,461 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= |v_main_#t~post0_1| v_main_~i~0_7) InVars {main_~i~0=v_main_~i~0_7} OutVars{main_#t~post0=|v_main_#t~post0_1|, main_~i~0=v_main_~i~0_7} AuxVars[] AssignedVars[main_#t~post0] [2018-03-28 15:52:27,461 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= |v_main_#t~post2_1| v_main_~i~0_15) InVars {main_~i~0=v_main_~i~0_15} OutVars{main_~i~0=v_main_~i~0_15, main_#t~post2=|v_main_#t~post2_1|} AuxVars[] AssignedVars[main_#t~post2] [2018-03-28 15:52:27,462 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: false InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,462 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,462 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~i~0_8 (+ |v_main_#t~post0_2| 1)) InVars {main_#t~post0=|v_main_#t~post0_2|} OutVars{main_#t~post0=|v_main_#t~post0_2|, main_~i~0=v_main_~i~0_8} AuxVars[] AssignedVars[main_~i~0] [2018-03-28 15:52:27,463 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= v_main_~i~0_16 (+ |v_main_#t~post2_2| 1)) InVars {main_#t~post2=|v_main_#t~post2_2|} OutVars{main_~i~0=v_main_~i~0_16, main_#t~post2=|v_main_#t~post2_2|} AuxVars[] AssignedVars[main_~i~0] [2018-03-28 15:52:27,463 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_#t~post0=|v_main_#t~post0_3|} AuxVars[] AssignedVars[main_#t~post0] [2018-03-28 15:52:27,463 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{main_#t~post2=|v_main_#t~post2_3|} AuxVars[] AssignedVars[main_#t~post2] [2018-03-28 15:52:27,464 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,464 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,465 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= |v_ULTIMATE.start_#t~ret3_2| |v_main_#resOutParam_1|) InVars {main_#res=|v_main_#resOutParam_1|} OutVars{ULTIMATE.start_#t~ret3=|v_ULTIMATE.start_#t~ret3_2|} AuxVars[] AssignedVars[ULTIMATE.start_#t~ret3] [2018-03-28 15:52:27,465 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,465 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: true InVars {} OutVars{} AuxVars[] AssignedVars[] [2018-03-28 15:52:27,466 DEBUG L87 nsformulaTransformer]: Performing identity transformation for Formula: (= |v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~condInParam_1| (ite (<= v_main_~i~0_18 1024) 1 0)) InVars {main_~i~0=v_main_~i~0_18} OutVars{__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond=|v___U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~condInParam_1|} AuxVars[] AssignedVars[__U_MULTI_farray__false_valid_deref_i____VERIFIER_assert_#in~cond] [2018-03-28 15:52:27,466 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 28.03 03:52:27 BasicIcfg [2018-03-28 15:52:27,467 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-03-28 15:52:27,467 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-03-28 15:52:27,468 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-03-28 15:52:27,471 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-03-28 15:52:27,471 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.03 03:52:26" (1/4) ... [2018-03-28 15:52:27,472 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6596d87d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.03 03:52:27, skipping insertion in model container [2018-03-28 15:52:27,472 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 03:52:27" (2/4) ... [2018-03-28 15:52:27,472 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6596d87d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.03 03:52:27, skipping insertion in model container [2018-03-28 15:52:27,472 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.03 03:52:27" (3/4) ... [2018-03-28 15:52:27,472 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6596d87d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.03 03:52:27, skipping insertion in model container [2018-03-28 15:52:27,473 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 28.03 03:52:27" (4/4) ... [2018-03-28 15:52:27,474 INFO L107 eAbstractionObserver]: Analyzing ICFG array3_false-valid-deref.ileft_unchanged_by_heapseparator [2018-03-28 15:52:27,484 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-03-28 15:52:27,492 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 2 error locations. [2018-03-28 15:52:27,542 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-03-28 15:52:27,543 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-03-28 15:52:27,543 INFO L370 AbstractCegarLoop]: Hoare is true [2018-03-28 15:52:27,543 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-03-28 15:52:27,543 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-03-28 15:52:27,543 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-03-28 15:52:27,543 INFO L374 AbstractCegarLoop]: Difference is false [2018-03-28 15:52:27,543 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-03-28 15:52:27,543 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-03-28 15:52:27,544 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-03-28 15:52:27,557 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states. [2018-03-28 15:52:27,562 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-03-28 15:52:27,562 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:27,562 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:52:27,563 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:27,566 INFO L82 PathProgramCache]: Analyzing trace with hash 1692213986, 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-28 15:52:27,581 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:27,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:27,602 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:27,638 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-28 15:52:27,638 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:27,660 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-28 15:52:27,683 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-28 15:52:27,683 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3, 3] imperfect sequences [] total 3 [2018-03-28 15:52:27,685 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-03-28 15:52:27,694 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-03-28 15:52:27,695 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-28 15:52:27,697 INFO L87 Difference]: Start difference. First operand 36 states. Second operand 4 states. [2018-03-28 15:52:27,786 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:52:27,787 INFO L93 Difference]: Finished difference Result 76 states and 95 transitions. [2018-03-28 15:52:27,787 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-03-28 15:52:27,788 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 10 [2018-03-28 15:52:27,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:52:27,795 INFO L225 Difference]: With dead ends: 76 [2018-03-28 15:52:27,795 INFO L226 Difference]: Without dead ends: 40 [2018-03-28 15:52:27,798 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-28 15:52:27,811 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-03-28 15:52:27,827 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 31. [2018-03-28 15:52:27,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-03-28 15:52:27,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-03-28 15:52:27,831 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 10 [2018-03-28 15:52:27,832 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:52:27,832 INFO L459 AbstractCegarLoop]: Abstraction has 31 states and 32 transitions. [2018-03-28 15:52:27,832 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-03-28 15:52:27,832 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 32 transitions. [2018-03-28 15:52:27,833 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-03-28 15:52:27,833 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:27,833 INFO L355 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:52:27,833 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:27,834 INFO L82 PathProgramCache]: Analyzing trace with hash -480009733, 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-28 15:52:27,841 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:27,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:27,854 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:27,927 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 15:52:27,927 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:27,978 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-03-28 15:52:28,004 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-28 15:52:28,004 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 8 [2018-03-28 15:52:28,005 INFO L442 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-03-28 15:52:28,006 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-03-28 15:52:28,006 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-03-28 15:52:28,006 INFO L87 Difference]: Start difference. First operand 31 states and 32 transitions. Second operand 9 states. [2018-03-28 15:52:28,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:52:28,176 INFO L93 Difference]: Finished difference Result 40 states and 41 transitions. [2018-03-28 15:52:28,176 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-03-28 15:52:28,176 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 19 [2018-03-28 15:52:28,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:52:28,178 INFO L225 Difference]: With dead ends: 40 [2018-03-28 15:52:28,178 INFO L226 Difference]: Without dead ends: 39 [2018-03-28 15:52:28,179 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 29 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2018-03-28 15:52:28,179 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-03-28 15:52:28,183 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 29. [2018-03-28 15:52:28,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-03-28 15:52:28,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-03-28 15:52:28,184 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 19 [2018-03-28 15:52:28,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:52:28,185 INFO L459 AbstractCegarLoop]: Abstraction has 29 states and 30 transitions. [2018-03-28 15:52:28,185 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-03-28 15:52:28,185 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 30 transitions. [2018-03-28 15:52:28,186 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-03-28 15:52:28,186 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:28,186 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, 1] [2018-03-28 15:52:28,186 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:28,186 INFO L82 PathProgramCache]: Analyzing trace with hash -1943421728, 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-28 15:52:28,201 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:28,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:28,214 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:28,243 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:28,243 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:28,291 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:28,313 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 15:52:28,313 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-03-28 15:52:28,314 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-28 15:52:28,314 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-28 15:52:28,314 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-03-28 15:52:28,315 INFO L87 Difference]: Start difference. First operand 29 states and 30 transitions. Second operand 8 states. [2018-03-28 15:52:28,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:52:28,394 INFO L93 Difference]: Finished difference Result 62 states and 65 transitions. [2018-03-28 15:52:28,394 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-03-28 15:52:28,395 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 28 [2018-03-28 15:52:28,395 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:52:28,396 INFO L225 Difference]: With dead ends: 62 [2018-03-28 15:52:28,396 INFO L226 Difference]: Without dead ends: 51 [2018-03-28 15:52:28,397 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2018-03-28 15:52:28,397 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2018-03-28 15:52:28,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 47. [2018-03-28 15:52:28,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-03-28 15:52:28,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 48 transitions. [2018-03-28 15:52:28,404 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 48 transitions. Word has length 28 [2018-03-28 15:52:28,405 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:52:28,405 INFO L459 AbstractCegarLoop]: Abstraction has 47 states and 48 transitions. [2018-03-28 15:52:28,405 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-28 15:52:28,405 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 48 transitions. [2018-03-28 15:52:28,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2018-03-28 15:52:28,407 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:28,407 INFO L355 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:52:28,407 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:28,407 INFO L82 PathProgramCache]: Analyzing trace with hash 639492352, now seen corresponding path program 2 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-28 15:52:28,415 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:28,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:28,431 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:28,512 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:28,512 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:28,602 INFO L134 CoverageAnalysis]: Checked inductivity of 35 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:28,635 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 15:52:28,636 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-03-28 15:52:28,636 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-28 15:52:28,636 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-28 15:52:28,636 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2018-03-28 15:52:28,637 INFO L87 Difference]: Start difference. First operand 47 states and 48 transitions. Second operand 16 states. [2018-03-28 15:52:28,951 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:52:28,952 INFO L93 Difference]: Finished difference Result 98 states and 103 transitions. [2018-03-28 15:52:28,952 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-03-28 15:52:28,952 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 46 [2018-03-28 15:52:28,952 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:52:28,953 INFO L225 Difference]: With dead ends: 98 [2018-03-28 15:52:28,953 INFO L226 Difference]: Without dead ends: 87 [2018-03-28 15:52:28,954 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 113 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=259, Invalid=497, Unknown=0, NotChecked=0, Total=756 [2018-03-28 15:52:28,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2018-03-28 15:52:28,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 83. [2018-03-28 15:52:28,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 83 states. [2018-03-28 15:52:28,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 84 transitions. [2018-03-28 15:52:28,961 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 84 transitions. Word has length 46 [2018-03-28 15:52:28,961 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:52:28,961 INFO L459 AbstractCegarLoop]: Abstraction has 83 states and 84 transitions. [2018-03-28 15:52:28,961 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-28 15:52:28,961 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 84 transitions. [2018-03-28 15:52:28,963 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2018-03-28 15:52:28,963 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:28,963 INFO L355 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 7, 7, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:52:28,964 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:28,965 INFO L82 PathProgramCache]: Analyzing trace with hash 348770624, now seen corresponding path program 3 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-28 15:52:28,974 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:28,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:28,997 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:29,150 INFO L134 CoverageAnalysis]: Checked inductivity of 205 backedges. 0 proven. 203 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:29,150 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:29,345 INFO L134 CoverageAnalysis]: Checked inductivity of 205 backedges. 0 proven. 203 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:29,366 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 15:52:29,367 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 32 [2018-03-28 15:52:29,367 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-28 15:52:29,367 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-28 15:52:29,368 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=272, Invalid=720, Unknown=0, NotChecked=0, Total=992 [2018-03-28 15:52:29,368 INFO L87 Difference]: Start difference. First operand 83 states and 84 transitions. Second operand 32 states. [2018-03-28 15:52:29,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:52:29,906 INFO L93 Difference]: Finished difference Result 170 states and 179 transitions. [2018-03-28 15:52:29,907 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-03-28 15:52:29,907 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 82 [2018-03-28 15:52:29,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:52:29,909 INFO L225 Difference]: With dead ends: 170 [2018-03-28 15:52:29,911 INFO L226 Difference]: Without dead ends: 159 [2018-03-28 15:52:29,913 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 191 GetRequests, 133 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 681 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=1155, Invalid=2385, Unknown=0, NotChecked=0, Total=3540 [2018-03-28 15:52:29,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2018-03-28 15:52:29,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 155. [2018-03-28 15:52:29,924 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 155 states. [2018-03-28 15:52:29,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 156 transitions. [2018-03-28 15:52:29,927 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 156 transitions. Word has length 82 [2018-03-28 15:52:29,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:52:29,928 INFO L459 AbstractCegarLoop]: Abstraction has 155 states and 156 transitions. [2018-03-28 15:52:29,928 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-28 15:52:29,928 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 156 transitions. [2018-03-28 15:52:29,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 155 [2018-03-28 15:52:29,933 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:29,933 INFO L355 BasicCegarLoop]: trace histogram [16, 15, 15, 15, 15, 15, 15, 15, 15, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:52:29,933 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:29,933 INFO L82 PathProgramCache]: Analyzing trace with hash -1318563392, now seen corresponding path program 4 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-28 15:52:29,946 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:29,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:29,993 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:30,295 INFO L134 CoverageAnalysis]: Checked inductivity of 977 backedges. 0 proven. 975 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:30,295 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:30,910 INFO L134 CoverageAnalysis]: Checked inductivity of 977 backedges. 0 proven. 975 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:30,932 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 15:52:30,932 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 64 [2018-03-28 15:52:30,933 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-28 15:52:30,933 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-28 15:52:30,935 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1056, Invalid=2976, Unknown=0, NotChecked=0, Total=4032 [2018-03-28 15:52:30,935 INFO L87 Difference]: Start difference. First operand 155 states and 156 transitions. Second operand 64 states. [2018-03-28 15:52:32,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:52:32,453 INFO L93 Difference]: Finished difference Result 314 states and 331 transitions. [2018-03-28 15:52:32,453 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-03-28 15:52:32,453 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 154 [2018-03-28 15:52:32,454 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:52:32,455 INFO L225 Difference]: With dead ends: 314 [2018-03-28 15:52:32,455 INFO L226 Difference]: Without dead ends: 303 [2018-03-28 15:52:32,458 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 367 GetRequests, 245 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3257 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=4867, Invalid=10385, Unknown=0, NotChecked=0, Total=15252 [2018-03-28 15:52:32,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2018-03-28 15:52:32,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 299. [2018-03-28 15:52:32,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 299 states. [2018-03-28 15:52:32,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 299 states to 299 states and 300 transitions. [2018-03-28 15:52:32,480 INFO L78 Accepts]: Start accepts. Automaton has 299 states and 300 transitions. Word has length 154 [2018-03-28 15:52:32,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:52:32,481 INFO L459 AbstractCegarLoop]: Abstraction has 299 states and 300 transitions. [2018-03-28 15:52:32,481 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-28 15:52:32,481 INFO L276 IsEmpty]: Start isEmpty. Operand 299 states and 300 transitions. [2018-03-28 15:52:32,487 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 299 [2018-03-28 15:52:32,487 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:32,488 INFO L355 BasicCegarLoop]: trace histogram [32, 31, 31, 31, 31, 31, 31, 31, 31, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:52:32,488 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:32,488 INFO L82 PathProgramCache]: Analyzing trace with hash -981478720, now seen corresponding path program 5 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-28 15:52:32,498 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:32,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:32,568 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:33,561 INFO L134 CoverageAnalysis]: Checked inductivity of 4249 backedges. 0 proven. 4247 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:33,562 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:35,826 INFO L134 CoverageAnalysis]: Checked inductivity of 4249 backedges. 0 proven. 4247 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:35,847 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 15:52:35,847 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65, 65] total 128 [2018-03-28 15:52:35,848 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-03-28 15:52:35,848 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-03-28 15:52:35,851 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=4160, Invalid=12096, Unknown=0, NotChecked=0, Total=16256 [2018-03-28 15:52:35,851 INFO L87 Difference]: Start difference. First operand 299 states and 300 transitions. Second operand 128 states. [2018-03-28 15:52:40,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:52:40,309 INFO L93 Difference]: Finished difference Result 602 states and 635 transitions. [2018-03-28 15:52:40,309 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-03-28 15:52:40,309 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 298 [2018-03-28 15:52:40,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:52:40,312 INFO L225 Difference]: With dead ends: 602 [2018-03-28 15:52:40,312 INFO L226 Difference]: Without dead ends: 591 [2018-03-28 15:52:40,318 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 719 GetRequests, 469 SyntacticMatches, 0 SemanticMatches, 250 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14169 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=19971, Invalid=43281, Unknown=0, NotChecked=0, Total=63252 [2018-03-28 15:52:40,319 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 591 states. [2018-03-28 15:52:40,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 591 to 587. [2018-03-28 15:52:40,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 587 states. [2018-03-28 15:52:40,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 587 states to 587 states and 588 transitions. [2018-03-28 15:52:40,343 INFO L78 Accepts]: Start accepts. Automaton has 587 states and 588 transitions. Word has length 298 [2018-03-28 15:52:40,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:52:40,344 INFO L459 AbstractCegarLoop]: Abstraction has 587 states and 588 transitions. [2018-03-28 15:52:40,344 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-03-28 15:52:40,344 INFO L276 IsEmpty]: Start isEmpty. Operand 587 states and 588 transitions. [2018-03-28 15:52:40,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 587 [2018-03-28 15:52:40,361 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:52:40,361 INFO L355 BasicCegarLoop]: trace histogram [64, 63, 63, 63, 63, 63, 63, 63, 63, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:52:40,361 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:52:40,362 INFO L82 PathProgramCache]: Analyzing trace with hash 119067840, now seen corresponding path program 6 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-28 15:52:40,370 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:52:40,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:52:40,497 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:52:43,942 INFO L134 CoverageAnalysis]: Checked inductivity of 17705 backedges. 0 proven. 17703 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:43,943 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:52:52,470 INFO L134 CoverageAnalysis]: Checked inductivity of 17705 backedges. 0 proven. 17703 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:52:52,490 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 15:52:52,491 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [129, 129] total 256 [2018-03-28 15:52:52,492 INFO L442 AbstractCegarLoop]: Interpolant automaton has 256 states [2018-03-28 15:52:52,494 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 256 interpolants. [2018-03-28 15:52:52,496 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=16512, Invalid=48768, Unknown=0, NotChecked=0, Total=65280 [2018-03-28 15:52:52,497 INFO L87 Difference]: Start difference. First operand 587 states and 588 transitions. Second operand 256 states. [2018-03-28 15:53:10,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 15:53:10,419 INFO L93 Difference]: Finished difference Result 1178 states and 1243 transitions. [2018-03-28 15:53:10,419 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 381 states. [2018-03-28 15:53:10,419 INFO L78 Accepts]: Start accepts. Automaton has 256 states. Word has length 586 [2018-03-28 15:53:10,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 15:53:10,423 INFO L225 Difference]: With dead ends: 1178 [2018-03-28 15:53:10,423 INFO L226 Difference]: Without dead ends: 1167 [2018-03-28 15:53:10,429 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1423 GetRequests, 917 SyntacticMatches, 0 SemanticMatches, 506 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 59033 ImplicationChecksByTransitivity, 27.3s TimeCoverageRelationStatistics Valid=80899, Invalid=176657, Unknown=0, NotChecked=0, Total=257556 [2018-03-28 15:53:10,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1167 states. [2018-03-28 15:53:10,449 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1167 to 1163. [2018-03-28 15:53:10,449 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1163 states. [2018-03-28 15:53:10,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1163 states to 1163 states and 1164 transitions. [2018-03-28 15:53:10,453 INFO L78 Accepts]: Start accepts. Automaton has 1163 states and 1164 transitions. Word has length 586 [2018-03-28 15:53:10,454 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 15:53:10,454 INFO L459 AbstractCegarLoop]: Abstraction has 1163 states and 1164 transitions. [2018-03-28 15:53:10,454 INFO L460 AbstractCegarLoop]: Interpolant automaton has 256 states. [2018-03-28 15:53:10,454 INFO L276 IsEmpty]: Start isEmpty. Operand 1163 states and 1164 transitions. [2018-03-28 15:53:10,461 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1163 [2018-03-28 15:53:10,461 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 15:53:10,462 INFO L355 BasicCegarLoop]: trace histogram [128, 127, 127, 127, 127, 127, 127, 127, 127, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 15:53:10,462 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr1AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 15:53:10,462 INFO L82 PathProgramCache]: Analyzing trace with hash 1609750720, now seen corresponding path program 7 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-28 15:53:10,490 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 15:53:10,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 15:53:10,665 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 15:53:25,275 INFO L134 CoverageAnalysis]: Checked inductivity of 72265 backedges. 0 proven. 72263 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:53:25,275 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 15:54:00,294 INFO L134 CoverageAnalysis]: Checked inductivity of 72265 backedges. 0 proven. 72263 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-03-28 15:54:00,329 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 15:54:00,330 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [257, 257] total 512 [2018-03-28 15:54:00,332 INFO L442 AbstractCegarLoop]: Interpolant automaton has 512 states [2018-03-28 15:54:00,341 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 512 interpolants. [2018-03-28 15:54:00,346 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=65792, Invalid=195840, Unknown=0, NotChecked=0, Total=261632 [2018-03-28 15:54:00,347 INFO L87 Difference]: Start difference. First operand 1163 states and 1164 transitions. Second operand 512 states. Received shutdown request... [2018-03-28 15:54:42,113 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 465 states. [2018-03-28 15:54:42,113 WARN L519 AbstractCegarLoop]: Verification canceled [2018-03-28 15:54:42,117 WARN L197 ceAbstractionStarter]: Timeout [2018-03-28 15:54:42,117 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.03 03:54:42 BasicIcfg [2018-03-28 15:54:42,117 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-03-28 15:54:42,118 INFO L168 Benchmark]: Toolchain (without parser) took 135147.40 ms. Allocated memory was 303.6 MB in the beginning and 1.8 GB in the end (delta: 1.5 GB). Free memory was 245.7 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 395.6 MB. Max. memory is 5.3 GB. [2018-03-28 15:54:42,119 INFO L168 Benchmark]: CDTParser took 0.16 ms. Allocated memory is still 303.6 MB. Free memory is still 265.8 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-03-28 15:54:42,120 INFO L168 Benchmark]: CACSL2BoogieTranslator took 187.63 ms. Allocated memory is still 303.6 MB. Free memory was 245.7 MB in the beginning and 236.7 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 5.3 GB. [2018-03-28 15:54:42,120 INFO L168 Benchmark]: Boogie Preprocessor took 22.36 ms. Allocated memory is still 303.6 MB. Free memory was 236.7 MB in the beginning and 234.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-03-28 15:54:42,121 INFO L168 Benchmark]: RCFGBuilder took 250.24 ms. Allocated memory was 303.6 MB in the beginning and 467.1 MB in the end (delta: 163.6 MB). Free memory was 234.7 MB in the beginning and 438.0 MB in the end (delta: -203.3 MB). Peak memory consumption was 23.2 MB. Max. memory is 5.3 GB. [2018-03-28 15:54:42,122 INFO L168 Benchmark]: IcfgTransformer took 31.57 ms. Allocated memory is still 467.1 MB. Free memory was 438.0 MB in the beginning and 432.8 MB in the end (delta: 5.2 MB). Peak memory consumption was 5.2 MB. Max. memory is 5.3 GB. [2018-03-28 15:54:42,122 INFO L168 Benchmark]: TraceAbstraction took 134649.78 ms. Allocated memory was 467.1 MB in the beginning and 1.8 GB in the end (delta: 1.3 GB). Free memory was 432.8 MB in the beginning and 1.3 GB in the end (delta: -900.5 MB). Peak memory consumption was 419.2 MB. Max. memory is 5.3 GB. [2018-03-28 15:54:42,126 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.16 ms. Allocated memory is still 303.6 MB. Free memory is still 265.8 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 187.63 ms. Allocated memory is still 303.6 MB. Free memory was 245.7 MB in the beginning and 236.7 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 22.36 ms. Allocated memory is still 303.6 MB. Free memory was 236.7 MB in the beginning and 234.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 250.24 ms. Allocated memory was 303.6 MB in the beginning and 467.1 MB in the end (delta: 163.6 MB). Free memory was 234.7 MB in the beginning and 438.0 MB in the end (delta: -203.3 MB). Peak memory consumption was 23.2 MB. Max. memory is 5.3 GB. * IcfgTransformer took 31.57 ms. Allocated memory is still 467.1 MB. Free memory was 438.0 MB in the beginning and 432.8 MB in the end (delta: 5.2 MB). Peak memory consumption was 5.2 MB. Max. memory is 5.3 GB. * TraceAbstraction took 134649.78 ms. Allocated memory was 467.1 MB in the beginning and 1.8 GB in the end (delta: 1.3 GB). Free memory was 432.8 MB in the beginning and 1.3 GB in the end (delta: -900.5 MB). Peak memory consumption was 419.2 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 15]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 15). Cancelled while BasicCegarLoop was constructing difference of abstraction (1163states) and interpolant automaton (currently 465 states, 512 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 820 known predicates. - TimeoutResultAtElement [Line: 13]: Timeout (TraceAbstraction) Unable to prove that array index is always in bounds (line 13). Cancelled while BasicCegarLoop was constructing difference of abstraction (1163states) and interpolant automaton (currently 465 states, 512 states before enhancement), while PredicateComparison was comparing new predicate (quantifier-free) to 820 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 36 locations, 2 error locations. TIMEOUT Result, 134.5s OverallTime, 9 OverallIterations, 128 TraceHistogramMax, 66.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 181 SDtfs, 4948 SDslu, 2583 SDs, 0 SdLazy, 2751 SolverSat, 2729 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 5553 GetRequests, 3748 SyntacticMatches, 2 SemanticMatches, 1802 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206761 ImplicationChecksByTransitivity, 113.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=1163occurred in iteration=8, 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: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 43 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 66.6s InterpolantComputationTime, 2385 NumberOfCodeBlocks, 2385 NumberOfCodeBlocksAsserted, 9 NumberOfCheckSat, 4752 ConstructedInterpolants, 0 QuantifiedInterpolants, 10718424 SizeOfPredicates, 503 NumberOfNonLiveVariables, 3213 ConjunctsInSsa, 516 ConjunctsInUnsatCore, 18 InterpolantComputations, 4 PerfectInterpolantSequences, 34/190886 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/array3_false-valid-deref.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerCTransformed.xml/Csv-Benchmark-0-2018-03-28_15-54-42-136.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/array3_false-valid-deref.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Fixed_noBitfields+AI_EQ_SS.epf_AutomizerCTransformed.xml/Csv-TraceAbstractionBenchmarks-0-2018-03-28_15-54-42-136.csv Completed graceful shutdown