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/AutomizerC.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-4cf2d92 [2018-03-28 12:37:04,547 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-03-28 12:37:04,549 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-03-28 12:37:04,564 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-03-28 12:37:04,565 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-03-28 12:37:04,566 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-03-28 12:37:04,567 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-03-28 12:37:04,569 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-03-28 12:37:04,571 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-03-28 12:37:04,572 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-03-28 12:37:04,572 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-03-28 12:37:04,573 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-03-28 12:37:04,574 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-03-28 12:37:04,575 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-03-28 12:37:04,576 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-03-28 12:37:04,578 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-03-28 12:37:04,580 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-03-28 12:37:04,582 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-03-28 12:37:04,583 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-03-28 12:37:04,584 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-03-28 12:37:04,586 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-03-28 12:37:04,587 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-03-28 12:37:04,587 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-03-28 12:37:04,588 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-03-28 12:37:04,589 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-03-28 12:37:04,590 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-03-28 12:37:04,590 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-03-28 12:37:04,591 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-03-28 12:37:04,592 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-03-28 12:37:04,592 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-03-28 12:37:04,593 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-03-28 12:37:04,593 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 12:37:04,618 INFO L110 SettingsManager]: Loading preferences was successful [2018-03-28 12:37:04,619 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-03-28 12:37:04,619 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-03-28 12:37:04,619 INFO L133 SettingsManager]: * ultimate.logging.details=de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation=DEBUG; [2018-03-28 12:37:04,620 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-03-28 12:37:04,620 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-03-28 12:37:04,620 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-03-28 12:37:04,620 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-03-28 12:37:04,621 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-03-28 12:37:04,621 INFO L131 SettingsManager]: Preferences of LTL2Aut differ from their defaults: [2018-03-28 12:37:04,621 INFO L133 SettingsManager]: * Property to check=[] a a: x > 42 [2018-03-28 12:37:04,622 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-03-28 12:37:04,622 INFO L133 SettingsManager]: * sizeof long=4 [2018-03-28 12:37:04,622 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-03-28 12:37:04,622 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-03-28 12:37:04,622 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-03-28 12:37:04,623 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-03-28 12:37:04,623 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-03-28 12:37:04,623 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-03-28 12:37:04,623 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-03-28 12:37:04,623 INFO L133 SettingsManager]: * sizeof long double=12 [2018-03-28 12:37:04,624 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-03-28 12:37:04,624 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-03-28 12:37:04,624 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-03-28 12:37:04,624 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-03-28 12:37:04,624 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-03-28 12:37:04,625 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-03-28 12:37:04,625 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-03-28 12:37:04,625 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-03-28 12:37:04,625 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-03-28 12:37:04,625 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-03-28 12:37:04,625 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-03-28 12:37:04,626 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-03-28 12:37:04,627 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-03-28 12:37:04,627 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-03-28 12:37:04,627 INFO L131 SettingsManager]: Preferences of Boogie Printer differ from their defaults: [2018-03-28 12:37:04,627 INFO L133 SettingsManager]: * Dump path:=C:\Users\alex\AppData\Local\Temp\ [2018-03-28 12:37:04,663 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-03-28 12:37:04,676 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully (re)initialized [2018-03-28 12:37:04,680 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-03-28 12:37:04,682 INFO L271 PluginConnector]: Initializing CDTParser... [2018-03-28 12:37:04,683 INFO L276 PluginConnector]: CDTParser initialized [2018-03-28 12:37:04,683 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-28 12:37:05,006 INFO L228 CDTParser]: Created temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG54986ab43 [2018-03-28 12:37:05,134 INFO L291 CDTParser]: IsIndexed: true [2018-03-28 12:37:05,134 INFO L292 CDTParser]: Found 1 translation units. [2018-03-28 12:37:05,135 INFO L171 CDTParser]: Scanning standard_strcpy_false-valid-deref_ground.i [2018-03-28 12:37:05,136 INFO L210 ultiparseSymbolTable]: Include resolver: [2018-03-28 12:37:05,136 INFO L215 ultiparseSymbolTable]: [2018-03-28 12:37:05,136 INFO L218 ultiparseSymbolTable]: Function table: [2018-03-28 12:37:05,136 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-28 12:37:05,136 INFO L221 ultiparseSymbolTable]: Function definition of null ('main') in standard_strcpy_false-valid-deref_ground.i [2018-03-28 12:37:05,136 INFO L227 ultiparseSymbolTable]: Global variable table: [2018-03-28 12:37:05,136 INFO L233 ultiparseSymbolTable]: [2018-03-28 12:37:05,152 INFO L334 CDTParser]: Deleted temporary CDT project at /storage/ultimate/releaseScripts/default/UAutomizer-linux/data/FLAG54986ab43 [2018-03-28 12:37:05,157 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-03-28 12:37:05,160 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-03-28 12:37:05,161 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-03-28 12:37:05,161 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-03-28 12:37:05,166 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-03-28 12:37:05,167 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,169 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@64909079 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05, skipping insertion in model container [2018-03-28 12:37:05,169 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,184 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-28 12:37:05,195 INFO L167 Dispatcher]: Using SV-COMP mode [2018-03-28 12:37:05,318 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-28 12:37:05,334 INFO L175 PostProcessor]: Settings: Checked method=main [2018-03-28 12:37:05,337 INFO L100 SccComputation]: Graph consists of 0 InCaSumBalls and 5 non ball SCCs. Number of states in SCCs 5. [2018-03-28 12:37:05,343 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05 WrapperNode [2018-03-28 12:37:05,343 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-03-28 12:37:05,344 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-03-28 12:37:05,344 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-03-28 12:37:05,344 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-03-28 12:37:05,353 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,354 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,359 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,359 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,361 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,365 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,366 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (1/1) ... [2018-03-28 12:37:05,367 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-03-28 12:37:05,368 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-03-28 12:37:05,368 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-03-28 12:37:05,368 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-03-28 12:37:05,369 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (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 12:37:05,424 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-03-28 12:37:05,424 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-03-28 12:37:05,424 INFO L136 BoogieDeclarations]: Found implementation of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-03-28 12:37:05,424 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-03-28 12:37:05,424 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_error [2018-03-28 12:37:05,424 INFO L128 BoogieDeclarations]: Found specification of procedure __U_MULTI_fstandard_strcpy_false_valid_deref_ground_i____VERIFIER_assert [2018-03-28 12:37:05,425 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-03-28 12:37:05,425 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-03-28 12:37:05,425 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-03-28 12:37:05,639 INFO L259 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-03-28 12:37:05,640 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.03 12:37:05 BoogieIcfgContainer [2018-03-28 12:37:05,640 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-03-28 12:37:05,640 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-03-28 12:37:05,640 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-03-28 12:37:05,643 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-03-28 12:37:05,643 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.03 12:37:05" (1/3) ... [2018-03-28 12:37:05,644 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3d5f8d9f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.03 12:37:05, skipping insertion in model container [2018-03-28 12:37:05,644 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.03 12:37:05" (2/3) ... [2018-03-28 12:37:05,644 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3d5f8d9f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.03 12:37:05, skipping insertion in model container [2018-03-28 12:37:05,644 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.03 12:37:05" (3/3) ... [2018-03-28 12:37:05,646 INFO L107 eAbstractionObserver]: Analyzing ICFG standard_strcpy_false-valid-deref_ground.i [2018-03-28 12:37:05,653 INFO L131 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-03-28 12:37:05,659 INFO L143 ceAbstractionStarter]: Appying trace abstraction to program that has 5 error locations. [2018-03-28 12:37:05,694 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-03-28 12:37:05,695 INFO L369 AbstractCegarLoop]: Interprodecural is true [2018-03-28 12:37:05,695 INFO L370 AbstractCegarLoop]: Hoare is true [2018-03-28 12:37:05,695 INFO L371 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-03-28 12:37:05,695 INFO L372 AbstractCegarLoop]: Backedges is TWOTRACK [2018-03-28 12:37:05,696 INFO L373 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-03-28 12:37:05,696 INFO L374 AbstractCegarLoop]: Difference is false [2018-03-28 12:37:05,696 INFO L375 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-03-28 12:37:05,696 INFO L380 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-03-28 12:37:05,697 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-03-28 12:37:05,715 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states. [2018-03-28 12:37:05,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-03-28 12:37:05,721 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:05,722 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:37:05,722 INFO L408 AbstractCegarLoop]: === Iteration 1 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:05,726 INFO L82 PathProgramCache]: Analyzing trace with hash 442952750, 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 12:37:05,740 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:05,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:05,761 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:05,787 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 12:37:05,787 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:05,825 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 12:37:05,849 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-28 12:37:05,849 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-03-28 12:37:05,851 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-03-28 12:37:05,860 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-03-28 12:37:05,861 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-28 12:37:05,863 INFO L87 Difference]: Start difference. First operand 39 states. Second operand 4 states. [2018-03-28 12:37:05,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:05,966 INFO L93 Difference]: Finished difference Result 108 states and 130 transitions. [2018-03-28 12:37:05,966 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-03-28 12:37:05,968 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 9 [2018-03-28 12:37:05,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:05,979 INFO L225 Difference]: With dead ends: 108 [2018-03-28 12:37:05,979 INFO L226 Difference]: Without dead ends: 71 [2018-03-28 12:37:05,983 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-28 12:37:05,996 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-03-28 12:37:06,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 45. [2018-03-28 12:37:06,018 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-03-28 12:37:06,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 48 transitions. [2018-03-28 12:37:06,022 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 48 transitions. Word has length 9 [2018-03-28 12:37:06,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:06,023 INFO L459 AbstractCegarLoop]: Abstraction has 45 states and 48 transitions. [2018-03-28 12:37:06,023 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-03-28 12:37:06,023 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 48 transitions. [2018-03-28 12:37:06,024 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-03-28 12:37:06,024 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:06,024 INFO L355 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:37:06,024 INFO L408 AbstractCegarLoop]: === Iteration 2 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:06,024 INFO L82 PathProgramCache]: Analyzing trace with hash 1498590240, 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 12:37:06,032 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:06,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:06,042 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:06,051 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 12:37:06,051 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:06,080 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 12:37:06,102 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-28 12:37:06,102 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 3 [2018-03-28 12:37:06,103 INFO L442 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-03-28 12:37:06,103 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-03-28 12:37:06,103 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-03-28 12:37:06,104 INFO L87 Difference]: Start difference. First operand 45 states and 48 transitions. Second operand 4 states. [2018-03-28 12:37:06,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:06,129 INFO L93 Difference]: Finished difference Result 54 states and 58 transitions. [2018-03-28 12:37:06,129 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-03-28 12:37:06,130 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 15 [2018-03-28 12:37:06,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:06,131 INFO L225 Difference]: With dead ends: 54 [2018-03-28 12:37:06,131 INFO L226 Difference]: Without dead ends: 52 [2018-03-28 12:37:06,132 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-28 12:37:06,133 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2018-03-28 12:37:06,138 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 49. [2018-03-28 12:37:06,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-03-28 12:37:06,140 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 52 transitions. [2018-03-28 12:37:06,140 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 52 transitions. Word has length 15 [2018-03-28 12:37:06,140 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:06,141 INFO L459 AbstractCegarLoop]: Abstraction has 49 states and 52 transitions. [2018-03-28 12:37:06,141 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-03-28 12:37:06,141 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 52 transitions. [2018-03-28 12:37:06,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-03-28 12:37:06,142 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:06,142 INFO L355 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:37:06,142 INFO L408 AbstractCegarLoop]: === Iteration 3 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:06,143 INFO L82 PathProgramCache]: Analyzing trace with hash -554303570, 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 12:37:06,153 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:06,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:06,163 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:06,220 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-28 12:37:06,220 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:06,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-28 12:37:06,313 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:06,314 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-28 12:37:06,314 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-28 12:37:06,314 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-28 12:37:06,315 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-03-28 12:37:06,315 INFO L87 Difference]: Start difference. First operand 49 states and 52 transitions. Second operand 8 states. [2018-03-28 12:37:06,528 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:06,529 INFO L93 Difference]: Finished difference Result 178 states and 200 transitions. [2018-03-28 12:37:06,529 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-03-28 12:37:06,529 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 23 [2018-03-28 12:37:06,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:06,532 INFO L225 Difference]: With dead ends: 178 [2018-03-28 12:37:06,533 INFO L226 Difference]: Without dead ends: 175 [2018-03-28 12:37:06,533 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-28 12:37:06,534 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2018-03-28 12:37:06,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 77. [2018-03-28 12:37:06,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-03-28 12:37:06,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 84 transitions. [2018-03-28 12:37:06,548 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 84 transitions. Word has length 23 [2018-03-28 12:37:06,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:06,548 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 84 transitions. [2018-03-28 12:37:06,548 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-28 12:37:06,548 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 84 transitions. [2018-03-28 12:37:06,549 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-03-28 12:37:06,549 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:06,549 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-28 12:37:06,549 INFO L408 AbstractCegarLoop]: === Iteration 4 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:06,550 INFO L82 PathProgramCache]: Analyzing trace with hash 1357875333, 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-28 12:37:06,559 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:06,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:06,570 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:06,590 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-28 12:37:06,590 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:06,617 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-28 12:37:06,652 INFO L320 seRefinementStrategy]: Constructing automaton from 2 perfect and 0 imperfect interpolant sequences. [2018-03-28 12:37:06,652 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4, 4] imperfect sequences [] total 5 [2018-03-28 12:37:06,653 INFO L442 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-03-28 12:37:06,653 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-03-28 12:37:06,653 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-03-28 12:37:06,654 INFO L87 Difference]: Start difference. First operand 77 states and 84 transitions. Second operand 5 states. [2018-03-28 12:37:06,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:06,721 INFO L93 Difference]: Finished difference Result 97 states and 104 transitions. [2018-03-28 12:37:06,722 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-03-28 12:37:06,722 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 27 [2018-03-28 12:37:06,722 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:06,724 INFO L225 Difference]: With dead ends: 97 [2018-03-28 12:37:06,724 INFO L226 Difference]: Without dead ends: 77 [2018-03-28 12:37:06,725 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-28 12:37:06,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-03-28 12:37:06,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-03-28 12:37:06,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-03-28 12:37:06,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 83 transitions. [2018-03-28 12:37:06,735 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 83 transitions. Word has length 27 [2018-03-28 12:37:06,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:06,735 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 83 transitions. [2018-03-28 12:37:06,736 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-03-28 12:37:06,736 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 83 transitions. [2018-03-28 12:37:06,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-03-28 12:37:06,737 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:06,737 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-28 12:37:06,738 INFO L408 AbstractCegarLoop]: === Iteration 5 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:06,738 INFO L82 PathProgramCache]: Analyzing trace with hash -1112537975, 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-28 12:37:06,755 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:06,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:06,769 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:06,884 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-28 12:37:06,885 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:06,948 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-28 12:37:06,979 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:06,979 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2018-03-28 12:37:06,979 INFO L442 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-03-28 12:37:06,980 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-03-28 12:37:06,980 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=63, Unknown=0, NotChecked=0, Total=90 [2018-03-28 12:37:06,980 INFO L87 Difference]: Start difference. First operand 77 states and 83 transitions. Second operand 10 states. [2018-03-28 12:37:07,056 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:07,056 INFO L93 Difference]: Finished difference Result 103 states and 110 transitions. [2018-03-28 12:37:07,057 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-03-28 12:37:07,063 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 34 [2018-03-28 12:37:07,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:07,064 INFO L225 Difference]: With dead ends: 103 [2018-03-28 12:37:07,064 INFO L226 Difference]: Without dead ends: 77 [2018-03-28 12:37:07,064 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-28 12:37:07,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2018-03-28 12:37:07,071 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-03-28 12:37:07,072 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 77 states. [2018-03-28 12:37:07,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 82 transitions. [2018-03-28 12:37:07,073 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 82 transitions. Word has length 34 [2018-03-28 12:37:07,074 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:07,074 INFO L459 AbstractCegarLoop]: Abstraction has 77 states and 82 transitions. [2018-03-28 12:37:07,074 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-03-28 12:37:07,074 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 82 transitions. [2018-03-28 12:37:07,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2018-03-28 12:37:07,075 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:07,075 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-28 12:37:07,076 INFO L408 AbstractCegarLoop]: === Iteration 6 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:07,076 INFO L82 PathProgramCache]: Analyzing trace with hash 707836933, 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-28 12:37:07,081 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:07,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:07,091 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:07,102 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-28 12:37:07,102 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:07,137 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-28 12:37:07,158 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:07,158 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 7 [2018-03-28 12:37:07,159 INFO L442 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-03-28 12:37:07,159 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-03-28 12:37:07,159 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-03-28 12:37:07,160 INFO L87 Difference]: Start difference. First operand 77 states and 82 transitions. Second operand 8 states. [2018-03-28 12:37:07,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:07,278 INFO L93 Difference]: Finished difference Result 98 states and 108 transitions. [2018-03-28 12:37:07,278 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-03-28 12:37:07,278 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 41 [2018-03-28 12:37:07,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:07,279 INFO L225 Difference]: With dead ends: 98 [2018-03-28 12:37:07,279 INFO L226 Difference]: Without dead ends: 96 [2018-03-28 12:37:07,280 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-28 12:37:07,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2018-03-28 12:37:07,285 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 93. [2018-03-28 12:37:07,285 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-03-28 12:37:07,287 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 100 transitions. [2018-03-28 12:37:07,287 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 100 transitions. Word has length 41 [2018-03-28 12:37:07,287 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:07,288 INFO L459 AbstractCegarLoop]: Abstraction has 93 states and 100 transitions. [2018-03-28 12:37:07,288 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-03-28 12:37:07,288 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 100 transitions. [2018-03-28 12:37:07,289 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2018-03-28 12:37:07,290 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:07,290 INFO L355 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:37:07,290 INFO L408 AbstractCegarLoop]: === Iteration 7 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:07,290 INFO L82 PathProgramCache]: Analyzing trace with hash 835962542, 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-28 12:37:07,296 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:07,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:07,308 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:07,384 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-28 12:37:07,384 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:07,467 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-28 12:37:07,488 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:07,489 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-28 12:37:07,489 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-28 12:37:07,489 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-28 12:37:07,489 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-03-28 12:37:07,490 INFO L87 Difference]: Start difference. First operand 93 states and 100 transitions. Second operand 16 states. [2018-03-28 12:37:07,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:07,911 INFO L93 Difference]: Finished difference Result 538 states and 610 transitions. [2018-03-28 12:37:07,911 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-03-28 12:37:07,911 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 51 [2018-03-28 12:37:07,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:07,915 INFO L225 Difference]: With dead ends: 538 [2018-03-28 12:37:07,915 INFO L226 Difference]: Without dead ends: 535 [2018-03-28 12:37:07,916 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-28 12:37:07,917 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 535 states. [2018-03-28 12:37:07,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 535 to 149. [2018-03-28 12:37:07,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-03-28 12:37:07,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 164 transitions. [2018-03-28 12:37:07,941 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 164 transitions. Word has length 51 [2018-03-28 12:37:07,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:07,942 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 164 transitions. [2018-03-28 12:37:07,942 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-28 12:37:07,942 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 164 transitions. [2018-03-28 12:37:07,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-03-28 12:37:07,944 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:07,944 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-28 12:37:07,944 INFO L408 AbstractCegarLoop]: === Iteration 8 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:07,944 INFO L82 PathProgramCache]: Analyzing trace with hash 476702287, 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-28 12:37:07,953 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:07,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:07,969 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:08,019 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-28 12:37:08,019 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:08,068 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-28 12:37:08,090 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:08,090 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-03-28 12:37:08,090 INFO L442 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-03-28 12:37:08,090 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-03-28 12:37:08,091 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2018-03-28 12:37:08,091 INFO L87 Difference]: Start difference. First operand 149 states and 164 transitions. Second operand 15 states. [2018-03-28 12:37:08,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:08,195 INFO L93 Difference]: Finished difference Result 185 states and 202 transitions. [2018-03-28 12:37:08,195 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-03-28 12:37:08,195 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 65 [2018-03-28 12:37:08,196 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:08,197 INFO L225 Difference]: With dead ends: 185 [2018-03-28 12:37:08,197 INFO L226 Difference]: Without dead ends: 149 [2018-03-28 12:37:08,197 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-28 12:37:08,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-03-28 12:37:08,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-03-28 12:37:08,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-03-28 12:37:08,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 163 transitions. [2018-03-28 12:37:08,210 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 163 transitions. Word has length 65 [2018-03-28 12:37:08,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:08,210 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 163 transitions. [2018-03-28 12:37:08,210 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-03-28 12:37:08,211 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 163 transitions. [2018-03-28 12:37:08,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2018-03-28 12:37:08,212 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:08,212 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-28 12:37:08,213 INFO L408 AbstractCegarLoop]: === Iteration 9 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:08,213 INFO L82 PathProgramCache]: Analyzing trace with hash -1796128941, 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-28 12:37:08,224 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:08,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:08,243 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:08,373 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-28 12:37:08,373 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:08,493 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-28 12:37:08,515 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:08,515 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 20 [2018-03-28 12:37:08,515 INFO L442 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-03-28 12:37:08,515 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-03-28 12:37:08,516 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-03-28 12:37:08,516 INFO L87 Difference]: Start difference. First operand 149 states and 163 transitions. Second operand 20 states. [2018-03-28 12:37:08,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:08,693 INFO L93 Difference]: Finished difference Result 191 states and 208 transitions. [2018-03-28 12:37:08,693 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-03-28 12:37:08,694 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 72 [2018-03-28 12:37:08,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:08,695 INFO L225 Difference]: With dead ends: 191 [2018-03-28 12:37:08,695 INFO L226 Difference]: Without dead ends: 149 [2018-03-28 12:37:08,696 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 121 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=171, Invalid=479, Unknown=0, NotChecked=0, Total=650 [2018-03-28 12:37:08,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2018-03-28 12:37:08,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 149. [2018-03-28 12:37:08,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-03-28 12:37:08,705 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 162 transitions. [2018-03-28 12:37:08,705 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 162 transitions. Word has length 72 [2018-03-28 12:37:08,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:08,706 INFO L459 AbstractCegarLoop]: Abstraction has 149 states and 162 transitions. [2018-03-28 12:37:08,706 INFO L460 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-03-28 12:37:08,706 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 162 transitions. [2018-03-28 12:37:08,707 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2018-03-28 12:37:08,707 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:08,708 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-28 12:37:08,708 INFO L408 AbstractCegarLoop]: === Iteration 10 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:08,708 INFO L82 PathProgramCache]: Analyzing trace with hash -1364690481, 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-28 12:37:08,714 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:08,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:08,746 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:08,797 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-28 12:37:08,797 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:08,888 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-28 12:37:08,909 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:08,909 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 15 [2018-03-28 12:37:08,909 INFO L442 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-03-28 12:37:08,909 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-03-28 12:37:08,910 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2018-03-28 12:37:08,910 INFO L87 Difference]: Start difference. First operand 149 states and 162 transitions. Second operand 16 states. [2018-03-28 12:37:09,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:09,148 INFO L93 Difference]: Finished difference Result 186 states and 210 transitions. [2018-03-28 12:37:09,148 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-03-28 12:37:09,148 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 79 [2018-03-28 12:37:09,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:09,149 INFO L225 Difference]: With dead ends: 186 [2018-03-28 12:37:09,149 INFO L226 Difference]: Without dead ends: 184 [2018-03-28 12:37:09,150 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-28 12:37:09,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-03-28 12:37:09,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 181. [2018-03-28 12:37:09,159 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 181 states. [2018-03-28 12:37:09,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 181 states to 181 states and 198 transitions. [2018-03-28 12:37:09,161 INFO L78 Accepts]: Start accepts. Automaton has 181 states and 198 transitions. Word has length 79 [2018-03-28 12:37:09,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:09,162 INFO L459 AbstractCegarLoop]: Abstraction has 181 states and 198 transitions. [2018-03-28 12:37:09,162 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-03-28 12:37:09,162 INFO L276 IsEmpty]: Start isEmpty. Operand 181 states and 198 transitions. [2018-03-28 12:37:09,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2018-03-28 12:37:09,164 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:09,164 INFO L355 BasicCegarLoop]: trace histogram [15, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:37:09,164 INFO L408 AbstractCegarLoop]: === Iteration 11 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:09,164 INFO L82 PathProgramCache]: Analyzing trace with hash 212718766, 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-28 12:37:09,173 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:09,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:09,189 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:09,344 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-28 12:37:09,344 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:09,737 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-28 12:37:09,758 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:09,758 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-28 12:37:09,759 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-28 12:37:09,759 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-28 12:37:09,759 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=286, Invalid=706, Unknown=0, NotChecked=0, Total=992 [2018-03-28 12:37:09,760 INFO L87 Difference]: Start difference. First operand 181 states and 198 transitions. Second operand 32 states. [2018-03-28 12:37:11,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:11,088 INFO L93 Difference]: Finished difference Result 1962 states and 2222 transitions. [2018-03-28 12:37:11,088 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-03-28 12:37:11,088 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 107 [2018-03-28 12:37:11,089 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:11,101 INFO L225 Difference]: With dead ends: 1962 [2018-03-28 12:37:11,101 INFO L226 Difference]: Without dead ends: 1959 [2018-03-28 12:37:11,103 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 227 GetRequests, 183 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=734, Invalid=1336, Unknown=0, NotChecked=0, Total=2070 [2018-03-28 12:37:11,104 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1959 states. [2018-03-28 12:37:11,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1959 to 293. [2018-03-28 12:37:11,157 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-28 12:37:11,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 326 transitions. [2018-03-28 12:37:11,160 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 326 transitions. Word has length 107 [2018-03-28 12:37:11,161 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:11,161 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 326 transitions. [2018-03-28 12:37:11,161 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-28 12:37:11,161 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 326 transitions. [2018-03-28 12:37:11,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2018-03-28 12:37:11,163 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:11,163 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-28 12:37:11,163 INFO L408 AbstractCegarLoop]: === Iteration 12 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:11,164 INFO L82 PathProgramCache]: Analyzing trace with hash -1443326877, 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-28 12:37:11,172 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:11,197 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:11,201 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:11,495 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-28 12:37:11,495 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:11,806 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-28 12:37:11,827 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:11,827 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 25 [2018-03-28 12:37:11,827 INFO L442 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-03-28 12:37:11,827 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-03-28 12:37:11,828 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=477, Unknown=0, NotChecked=0, Total=600 [2018-03-28 12:37:11,828 INFO L87 Difference]: Start difference. First operand 293 states and 326 transitions. Second operand 25 states. [2018-03-28 12:37:12,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:12,093 INFO L93 Difference]: Finished difference Result 361 states and 400 transitions. [2018-03-28 12:37:12,094 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-03-28 12:37:12,094 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 127 [2018-03-28 12:37:12,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:12,096 INFO L225 Difference]: With dead ends: 361 [2018-03-28 12:37:12,096 INFO L226 Difference]: Without dead ends: 293 [2018-03-28 12:37:12,097 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 261 GetRequests, 225 SyntacticMatches, 5 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 235 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=263, Invalid=793, Unknown=0, NotChecked=0, Total=1056 [2018-03-28 12:37:12,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-28 12:37:12,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-28 12:37:12,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-28 12:37:12,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 325 transitions. [2018-03-28 12:37:12,117 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 325 transitions. Word has length 127 [2018-03-28 12:37:12,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:12,118 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 325 transitions. [2018-03-28 12:37:12,118 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-03-28 12:37:12,118 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 325 transitions. [2018-03-28 12:37:12,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 135 [2018-03-28 12:37:12,119 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:12,119 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-28 12:37:12,119 INFO L408 AbstractCegarLoop]: === Iteration 13 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:12,119 INFO L82 PathProgramCache]: Analyzing trace with hash -1820836249, 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-28 12:37:12,126 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:12,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:12,156 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:12,287 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-28 12:37:12,287 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:12,425 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-28 12:37:12,446 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:12,446 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 30 [2018-03-28 12:37:12,447 INFO L442 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-03-28 12:37:12,447 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-03-28 12:37:12,447 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=701, Unknown=0, NotChecked=0, Total=870 [2018-03-28 12:37:12,447 INFO L87 Difference]: Start difference. First operand 293 states and 325 transitions. Second operand 30 states. [2018-03-28 12:37:12,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:12,689 INFO L93 Difference]: Finished difference Result 361 states and 399 transitions. [2018-03-28 12:37:12,690 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-03-28 12:37:12,690 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 134 [2018-03-28 12:37:12,690 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:12,691 INFO L225 Difference]: With dead ends: 361 [2018-03-28 12:37:12,691 INFO L226 Difference]: Without dead ends: 293 [2018-03-28 12:37:12,692 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-28 12:37:12,693 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-28 12:37:12,705 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-28 12:37:12,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-28 12:37:12,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 324 transitions. [2018-03-28 12:37:12,707 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 324 transitions. Word has length 134 [2018-03-28 12:37:12,707 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:12,707 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 324 transitions. [2018-03-28 12:37:12,707 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-03-28 12:37:12,708 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 324 transitions. [2018-03-28 12:37:12,708 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 142 [2018-03-28 12:37:12,709 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:12,709 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-28 12:37:12,709 INFO L408 AbstractCegarLoop]: === Iteration 14 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:12,709 INFO L82 PathProgramCache]: Analyzing trace with hash -194377757, 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-28 12:37:12,715 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:12,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:12,738 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:12,926 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-28 12:37:12,926 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:13,130 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-28 12:37:13,151 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:13,151 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 35 [2018-03-28 12:37:13,151 INFO L442 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-03-28 12:37:13,152 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-03-28 12:37:13,152 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=222, Invalid=968, Unknown=0, NotChecked=0, Total=1190 [2018-03-28 12:37:13,152 INFO L87 Difference]: Start difference. First operand 293 states and 324 transitions. Second operand 35 states. [2018-03-28 12:37:13,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:13,614 INFO L93 Difference]: Finished difference Result 361 states and 398 transitions. [2018-03-28 12:37:13,614 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-03-28 12:37:13,614 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 141 [2018-03-28 12:37:13,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:13,616 INFO L225 Difference]: With dead ends: 361 [2018-03-28 12:37:13,617 INFO L226 Difference]: Without dead ends: 293 [2018-03-28 12:37:13,618 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 293 GetRequests, 241 SyntacticMatches, 7 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 512 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=504, Invalid=1658, Unknown=0, NotChecked=0, Total=2162 [2018-03-28 12:37:13,618 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-28 12:37:13,638 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-28 12:37:13,639 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-28 12:37:13,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 323 transitions. [2018-03-28 12:37:13,640 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 323 transitions. Word has length 141 [2018-03-28 12:37:13,641 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:13,641 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 323 transitions. [2018-03-28 12:37:13,641 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-03-28 12:37:13,641 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 323 transitions. [2018-03-28 12:37:13,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2018-03-28 12:37:13,643 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:13,643 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-28 12:37:13,643 INFO L408 AbstractCegarLoop]: === Iteration 15 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:13,644 INFO L82 PathProgramCache]: Analyzing trace with hash -274343193, 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-28 12:37:13,654 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:13,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:13,684 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:13,935 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-28 12:37:13,935 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:14,207 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-28 12:37:14,228 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:14,228 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 40 [2018-03-28 12:37:14,228 INFO L442 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-03-28 12:37:14,229 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-03-28 12:37:14,229 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=282, Invalid=1278, Unknown=0, NotChecked=0, Total=1560 [2018-03-28 12:37:14,229 INFO L87 Difference]: Start difference. First operand 293 states and 323 transitions. Second operand 40 states. [2018-03-28 12:37:14,533 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:14,533 INFO L93 Difference]: Finished difference Result 367 states and 404 transitions. [2018-03-28 12:37:14,534 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-03-28 12:37:14,534 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 148 [2018-03-28 12:37:14,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:14,535 INFO L225 Difference]: With dead ends: 367 [2018-03-28 12:37:14,535 INFO L226 Difference]: Without dead ends: 293 [2018-03-28 12:37:14,536 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-28 12:37:14,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-03-28 12:37:14,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 293. [2018-03-28 12:37:14,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 293 states. [2018-03-28 12:37:14,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 293 states to 293 states and 322 transitions. [2018-03-28 12:37:14,550 INFO L78 Accepts]: Start accepts. Automaton has 293 states and 322 transitions. Word has length 148 [2018-03-28 12:37:14,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:14,550 INFO L459 AbstractCegarLoop]: Abstraction has 293 states and 322 transitions. [2018-03-28 12:37:14,550 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-03-28 12:37:14,550 INFO L276 IsEmpty]: Start isEmpty. Operand 293 states and 322 transitions. [2018-03-28 12:37:14,552 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2018-03-28 12:37:14,552 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:14,552 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-28 12:37:14,552 INFO L408 AbstractCegarLoop]: === Iteration 16 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:14,552 INFO L82 PathProgramCache]: Analyzing trace with hash 596335459, 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-28 12:37:14,559 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:14,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:14,586 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:14,686 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-28 12:37:14,686 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:15,037 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-28 12:37:15,069 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:15,069 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2018-03-28 12:37:15,070 INFO L442 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-03-28 12:37:15,070 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-03-28 12:37:15,070 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=818, Unknown=0, NotChecked=0, Total=992 [2018-03-28 12:37:15,071 INFO L87 Difference]: Start difference. First operand 293 states and 322 transitions. Second operand 32 states. [2018-03-28 12:37:16,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:16,075 INFO L93 Difference]: Finished difference Result 362 states and 414 transitions. [2018-03-28 12:37:16,075 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-03-28 12:37:16,075 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 155 [2018-03-28 12:37:16,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:16,078 INFO L225 Difference]: With dead ends: 362 [2018-03-28 12:37:16,078 INFO L226 Difference]: Without dead ends: 360 [2018-03-28 12:37:16,079 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-28 12:37:16,080 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 360 states. [2018-03-28 12:37:16,101 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 360 to 357. [2018-03-28 12:37:16,101 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 357 states. [2018-03-28 12:37:16,102 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 357 states to 357 states and 394 transitions. [2018-03-28 12:37:16,103 INFO L78 Accepts]: Start accepts. Automaton has 357 states and 394 transitions. Word has length 155 [2018-03-28 12:37:16,103 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:16,103 INFO L459 AbstractCegarLoop]: Abstraction has 357 states and 394 transitions. [2018-03-28 12:37:16,103 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-03-28 12:37:16,104 INFO L276 IsEmpty]: Start isEmpty. Operand 357 states and 394 transitions. [2018-03-28 12:37:16,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 220 [2018-03-28 12:37:16,106 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:16,107 INFO L355 BasicCegarLoop]: trace histogram [31, 30, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:37:16,107 INFO L408 AbstractCegarLoop]: === Iteration 17 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:16,107 INFO L82 PathProgramCache]: Analyzing trace with hash 2010902702, 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-28 12:37:16,120 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:16,151 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:16,156 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:16,561 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-28 12:37:16,561 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:17,550 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-28 12:37:17,571 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:17,571 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-28 12:37:17,571 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-28 12:37:17,572 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-28 12:37:17,572 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1086, Invalid=2946, Unknown=0, NotChecked=0, Total=4032 [2018-03-28 12:37:17,573 INFO L87 Difference]: Start difference. First operand 357 states and 394 transitions. Second operand 64 states. [2018-03-28 12:37:23,214 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:23,214 INFO L93 Difference]: Finished difference Result 7498 states and 8470 transitions. [2018-03-28 12:37:23,215 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-03-28 12:37:23,215 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 219 [2018-03-28 12:37:23,215 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:23,238 INFO L225 Difference]: With dead ends: 7498 [2018-03-28 12:37:23,238 INFO L226 Difference]: Without dead ends: 7495 [2018-03-28 12:37:23,242 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-28 12:37:23,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7495 states. [2018-03-28 12:37:23,435 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7495 to 581. [2018-03-28 12:37:23,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:23,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 650 transitions. [2018-03-28 12:37:23,438 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 650 transitions. Word has length 219 [2018-03-28 12:37:23,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:23,439 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 650 transitions. [2018-03-28 12:37:23,439 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-28 12:37:23,439 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 650 transitions. [2018-03-28 12:37:23,441 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 252 [2018-03-28 12:37:23,441 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:23,441 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-28 12:37:23,441 INFO L408 AbstractCegarLoop]: === Iteration 18 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:23,442 INFO L82 PathProgramCache]: Analyzing trace with hash 1912252555, 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-28 12:37:23,453 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:23,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:23,505 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:24,020 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-28 12:37:24,021 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:24,318 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-28 12:37:24,339 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:24,339 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 45 [2018-03-28 12:37:24,340 INFO L442 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-03-28 12:37:24,340 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-03-28 12:37:24,340 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=349, Invalid=1631, Unknown=0, NotChecked=0, Total=1980 [2018-03-28 12:37:24,341 INFO L87 Difference]: Start difference. First operand 581 states and 650 transitions. Second operand 45 states. [2018-03-28 12:37:24,756 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:24,756 INFO L93 Difference]: Finished difference Result 713 states and 796 transitions. [2018-03-28 12:37:24,756 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-03-28 12:37:24,756 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 251 [2018-03-28 12:37:24,757 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:24,759 INFO L225 Difference]: With dead ends: 713 [2018-03-28 12:37:24,759 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:24,761 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-28 12:37:24,761 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:24,830 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:24,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:24,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 649 transitions. [2018-03-28 12:37:24,833 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 649 transitions. Word has length 251 [2018-03-28 12:37:24,833 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:24,833 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 649 transitions. [2018-03-28 12:37:24,834 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-03-28 12:37:24,834 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 649 transitions. [2018-03-28 12:37:24,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-03-28 12:37:24,836 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:24,836 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-28 12:37:24,836 INFO L408 AbstractCegarLoop]: === Iteration 19 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:24,836 INFO L82 PathProgramCache]: Analyzing trace with hash -922504049, 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-28 12:37:24,849 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:24,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:24,913 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:25,392 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-28 12:37:25,392 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:25,770 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-28 12:37:25,796 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:25,796 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 50 [2018-03-28 12:37:25,797 INFO L442 AbstractCegarLoop]: Interpolant automaton has 50 states [2018-03-28 12:37:25,797 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2018-03-28 12:37:25,797 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=423, Invalid=2027, Unknown=0, NotChecked=0, Total=2450 [2018-03-28 12:37:25,798 INFO L87 Difference]: Start difference. First operand 581 states and 649 transitions. Second operand 50 states. [2018-03-28 12:37:26,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:26,287 INFO L93 Difference]: Finished difference Result 713 states and 795 transitions. [2018-03-28 12:37:26,287 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-03-28 12:37:26,287 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 258 [2018-03-28 12:37:26,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:26,289 INFO L225 Difference]: With dead ends: 713 [2018-03-28 12:37:26,290 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:26,291 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 533 GetRequests, 457 SyntacticMatches, 10 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1130 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=1008, Invalid=3548, Unknown=0, NotChecked=0, Total=4556 [2018-03-28 12:37:26,291 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:26,330 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:26,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:26,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 648 transitions. [2018-03-28 12:37:26,331 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 648 transitions. Word has length 258 [2018-03-28 12:37:26,331 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:26,331 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 648 transitions. [2018-03-28 12:37:26,332 INFO L460 AbstractCegarLoop]: Interpolant automaton has 50 states. [2018-03-28 12:37:26,332 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 648 transitions. [2018-03-28 12:37:26,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 266 [2018-03-28 12:37:26,333 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:26,333 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-28 12:37:26,333 INFO L408 AbstractCegarLoop]: === Iteration 20 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:26,333 INFO L82 PathProgramCache]: Analyzing trace with hash 1400495115, 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-28 12:37:26,339 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:26,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:26,373 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:26,715 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-28 12:37:26,715 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:27,125 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-28 12:37:27,146 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:27,146 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [34, 34] total 55 [2018-03-28 12:37:27,146 INFO L442 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-03-28 12:37:27,147 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-03-28 12:37:27,147 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=504, Invalid=2466, Unknown=0, NotChecked=0, Total=2970 [2018-03-28 12:37:27,147 INFO L87 Difference]: Start difference. First operand 581 states and 648 transitions. Second operand 55 states. [2018-03-28 12:37:27,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:27,793 INFO L93 Difference]: Finished difference Result 713 states and 794 transitions. [2018-03-28 12:37:27,833 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-03-28 12:37:27,833 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 265 [2018-03-28 12:37:27,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:27,835 INFO L225 Difference]: With dead ends: 713 [2018-03-28 12:37:27,836 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:27,837 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 549 GetRequests, 465 SyntacticMatches, 11 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1390 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=1214, Invalid=4336, Unknown=0, NotChecked=0, Total=5550 [2018-03-28 12:37:27,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:27,875 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:27,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:27,877 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 647 transitions. [2018-03-28 12:37:27,877 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 647 transitions. Word has length 265 [2018-03-28 12:37:27,877 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:27,877 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 647 transitions. [2018-03-28 12:37:27,877 INFO L460 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-03-28 12:37:27,877 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 647 transitions. [2018-03-28 12:37:27,878 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-03-28 12:37:27,879 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:27,879 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-28 12:37:27,879 INFO L408 AbstractCegarLoop]: === Iteration 21 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:27,879 INFO L82 PathProgramCache]: Analyzing trace with hash -685010673, 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-28 12:37:27,887 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:27,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:27,919 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:28,296 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-28 12:37:28,297 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:28,786 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-28 12:37:28,807 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:28,807 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 60 [2018-03-28 12:37:28,808 INFO L442 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-03-28 12:37:28,808 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-03-28 12:37:28,809 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=592, Invalid=2948, Unknown=0, NotChecked=0, Total=3540 [2018-03-28 12:37:28,809 INFO L87 Difference]: Start difference. First operand 581 states and 647 transitions. Second operand 60 states. [2018-03-28 12:37:29,517 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:29,518 INFO L93 Difference]: Finished difference Result 713 states and 793 transitions. [2018-03-28 12:37:29,518 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-03-28 12:37:29,518 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 272 [2018-03-28 12:37:29,519 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:29,520 INFO L225 Difference]: With dead ends: 713 [2018-03-28 12:37:29,521 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:29,522 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-28 12:37:29,523 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:29,589 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:29,589 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:29,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 646 transitions. [2018-03-28 12:37:29,592 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 646 transitions. Word has length 272 [2018-03-28 12:37:29,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:29,592 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 646 transitions. [2018-03-28 12:37:29,592 INFO L460 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-03-28 12:37:29,592 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 646 transitions. [2018-03-28 12:37:29,595 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 280 [2018-03-28 12:37:29,595 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:29,595 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-28 12:37:29,595 INFO L408 AbstractCegarLoop]: === Iteration 22 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:29,595 INFO L82 PathProgramCache]: Analyzing trace with hash -828838005, 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-28 12:37:29,606 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:29,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:29,657 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:30,228 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-28 12:37:30,228 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:30,820 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-28 12:37:30,841 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:30,842 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [40, 40] total 65 [2018-03-28 12:37:30,842 INFO L442 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-03-28 12:37:30,842 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-03-28 12:37:30,843 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=687, Invalid=3473, Unknown=0, NotChecked=0, Total=4160 [2018-03-28 12:37:30,843 INFO L87 Difference]: Start difference. First operand 581 states and 646 transitions. Second operand 65 states. [2018-03-28 12:37:32,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:32,044 INFO L93 Difference]: Finished difference Result 713 states and 792 transitions. [2018-03-28 12:37:32,044 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-03-28 12:37:32,044 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 279 [2018-03-28 12:37:32,045 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:32,048 INFO L225 Difference]: With dead ends: 713 [2018-03-28 12:37:32,048 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:32,050 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-28 12:37:32,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:32,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:32,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:32,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 645 transitions. [2018-03-28 12:37:32,091 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 645 transitions. Word has length 279 [2018-03-28 12:37:32,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:32,091 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 645 transitions. [2018-03-28 12:37:32,091 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-03-28 12:37:32,091 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 645 transitions. [2018-03-28 12:37:32,092 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 287 [2018-03-28 12:37:32,092 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:32,093 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-28 12:37:32,093 INFO L408 AbstractCegarLoop]: === Iteration 23 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:32,093 INFO L82 PathProgramCache]: Analyzing trace with hash 303533455, 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-28 12:37:32,098 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:32,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:32,134 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:32,921 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-28 12:37:32,921 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:33,549 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-28 12:37:33,570 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:33,571 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43, 43] total 70 [2018-03-28 12:37:33,571 INFO L442 AbstractCegarLoop]: Interpolant automaton has 70 states [2018-03-28 12:37:33,571 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 70 interpolants. [2018-03-28 12:37:33,572 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=789, Invalid=4041, Unknown=0, NotChecked=0, Total=4830 [2018-03-28 12:37:33,572 INFO L87 Difference]: Start difference. First operand 581 states and 645 transitions. Second operand 70 states. [2018-03-28 12:37:34,387 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:34,387 INFO L93 Difference]: Finished difference Result 713 states and 791 transitions. [2018-03-28 12:37:34,387 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-03-28 12:37:34,387 INFO L78 Accepts]: Start accepts. Automaton has 70 states. Word has length 286 [2018-03-28 12:37:34,388 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:34,389 INFO L225 Difference]: With dead ends: 713 [2018-03-28 12:37:34,389 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:34,390 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 597 GetRequests, 489 SyntacticMatches, 14 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2332 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1946, Invalid=7174, Unknown=0, NotChecked=0, Total=9120 [2018-03-28 12:37:34,391 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:34,443 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:34,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:34,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 644 transitions. [2018-03-28 12:37:34,446 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 644 transitions. Word has length 286 [2018-03-28 12:37:34,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:34,446 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 644 transitions. [2018-03-28 12:37:34,446 INFO L460 AbstractCegarLoop]: Interpolant automaton has 70 states. [2018-03-28 12:37:34,446 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 644 transitions. [2018-03-28 12:37:34,449 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 294 [2018-03-28 12:37:34,449 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:34,449 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-28 12:37:34,449 INFO L408 AbstractCegarLoop]: === Iteration 24 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:34,450 INFO L82 PathProgramCache]: Analyzing trace with hash 504357643, 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-28 12:37:34,458 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:34,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:34,513 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:35,074 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-28 12:37:35,075 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:35,789 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-28 12:37:35,809 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:35,810 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [46, 46] total 75 [2018-03-28 12:37:35,810 INFO L442 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-03-28 12:37:35,811 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-03-28 12:37:35,811 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=898, Invalid=4652, Unknown=0, NotChecked=0, Total=5550 [2018-03-28 12:37:35,811 INFO L87 Difference]: Start difference. First operand 581 states and 644 transitions. Second operand 75 states. [2018-03-28 12:37:36,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:36,744 INFO L93 Difference]: Finished difference Result 713 states and 790 transitions. [2018-03-28 12:37:36,744 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-03-28 12:37:36,744 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 293 [2018-03-28 12:37:36,745 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:36,747 INFO L225 Difference]: With dead ends: 713 [2018-03-28 12:37:36,747 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:36,748 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 613 GetRequests, 497 SyntacticMatches, 15 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2700 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=2228, Invalid=8278, Unknown=0, NotChecked=0, Total=10506 [2018-03-28 12:37:36,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:36,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:36,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:36,785 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 643 transitions. [2018-03-28 12:37:36,785 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 643 transitions. Word has length 293 [2018-03-28 12:37:36,785 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:36,786 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 643 transitions. [2018-03-28 12:37:36,786 INFO L460 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-03-28 12:37:36,786 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 643 transitions. [2018-03-28 12:37:36,788 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 301 [2018-03-28 12:37:36,788 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:36,788 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-28 12:37:36,788 INFO L408 AbstractCegarLoop]: === Iteration 25 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:36,789 INFO L82 PathProgramCache]: Analyzing trace with hash 1074768399, 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-28 12:37:36,797 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:36,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:36,847 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:37,485 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-28 12:37:37,486 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:38,291 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-28 12:37:38,318 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:38,318 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49, 49] total 80 [2018-03-28 12:37:38,319 INFO L442 AbstractCegarLoop]: Interpolant automaton has 80 states [2018-03-28 12:37:38,319 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 80 interpolants. [2018-03-28 12:37:38,320 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1014, Invalid=5306, Unknown=0, NotChecked=0, Total=6320 [2018-03-28 12:37:38,320 INFO L87 Difference]: Start difference. First operand 581 states and 643 transitions. Second operand 80 states. [2018-03-28 12:37:39,351 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:39,351 INFO L93 Difference]: Finished difference Result 719 states and 796 transitions. [2018-03-28 12:37:39,351 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 64 states. [2018-03-28 12:37:39,351 INFO L78 Accepts]: Start accepts. Automaton has 80 states. Word has length 300 [2018-03-28 12:37:39,352 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:39,354 INFO L225 Difference]: With dead ends: 719 [2018-03-28 12:37:39,354 INFO L226 Difference]: Without dead ends: 581 [2018-03-28 12:37:39,355 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-28 12:37:39,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 581 states. [2018-03-28 12:37:39,405 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 581 to 581. [2018-03-28 12:37:39,405 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 581 states. [2018-03-28 12:37:39,407 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 581 states to 581 states and 642 transitions. [2018-03-28 12:37:39,407 INFO L78 Accepts]: Start accepts. Automaton has 581 states and 642 transitions. Word has length 300 [2018-03-28 12:37:39,408 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:39,408 INFO L459 AbstractCegarLoop]: Abstraction has 581 states and 642 transitions. [2018-03-28 12:37:39,408 INFO L460 AbstractCegarLoop]: Interpolant automaton has 80 states. [2018-03-28 12:37:39,408 INFO L276 IsEmpty]: Start isEmpty. Operand 581 states and 642 transitions. [2018-03-28 12:37:39,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 308 [2018-03-28 12:37:39,409 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:39,410 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-28 12:37:39,410 INFO L408 AbstractCegarLoop]: === Iteration 26 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:39,410 INFO L82 PathProgramCache]: Analyzing trace with hash 1519826571, 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-28 12:37:39,417 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:39,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:39,468 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:39,804 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-28 12:37:39,805 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:40,767 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-28 12:37:40,788 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:40,788 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 63 [2018-03-28 12:37:40,789 INFO L442 AbstractCegarLoop]: Interpolant automaton has 64 states [2018-03-28 12:37:40,789 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 64 interpolants. [2018-03-28 12:37:40,789 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=606, Invalid=3426, Unknown=0, NotChecked=0, Total=4032 [2018-03-28 12:37:40,789 INFO L87 Difference]: Start difference. First operand 581 states and 642 transitions. Second operand 64 states. [2018-03-28 12:37:45,299 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:37:45,299 INFO L93 Difference]: Finished difference Result 714 states and 822 transitions. [2018-03-28 12:37:45,299 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-03-28 12:37:45,299 INFO L78 Accepts]: Start accepts. Automaton has 64 states. Word has length 307 [2018-03-28 12:37:45,300 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:37:45,303 INFO L225 Difference]: With dead ends: 714 [2018-03-28 12:37:45,303 INFO L226 Difference]: Without dead ends: 712 [2018-03-28 12:37:45,304 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-28 12:37:45,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 712 states. [2018-03-28 12:37:45,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 712 to 709. [2018-03-28 12:37:45,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-03-28 12:37:45,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 786 transitions. [2018-03-28 12:37:45,347 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 786 transitions. Word has length 307 [2018-03-28 12:37:45,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:37:45,347 INFO L459 AbstractCegarLoop]: Abstraction has 709 states and 786 transitions. [2018-03-28 12:37:45,347 INFO L460 AbstractCegarLoop]: Interpolant automaton has 64 states. [2018-03-28 12:37:45,347 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 786 transitions. [2018-03-28 12:37:45,351 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 444 [2018-03-28 12:37:45,351 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:37:45,352 INFO L355 BasicCegarLoop]: trace histogram [63, 62, 62, 62, 62, 62, 62, 1, 1, 1, 1, 1, 1, 1, 1] [2018-03-28 12:37:45,352 INFO L408 AbstractCegarLoop]: === Iteration 27 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:37:45,352 INFO L82 PathProgramCache]: Analyzing trace with hash 740305070, 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-28 12:37:45,358 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:37:45,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:37:45,401 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:37:46,684 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-28 12:37:46,685 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:37:50,457 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-28 12:37:50,479 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:37:50,489 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 127 [2018-03-28 12:37:50,490 INFO L442 AbstractCegarLoop]: Interpolant automaton has 128 states [2018-03-28 12:37:50,490 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 128 interpolants. [2018-03-28 12:37:50,491 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=4222, Invalid=12034, Unknown=0, NotChecked=0, Total=16256 [2018-03-28 12:37:50,491 INFO L87 Difference]: Start difference. First operand 709 states and 786 transitions. Second operand 128 states. [2018-03-28 12:37:56,016 WARN L151 SmtUtils]: Spent 249ms on a formula simplification. DAG size of input: 316 DAG size of output 6 [2018-03-28 12:37:56,489 WARN L151 SmtUtils]: Spent 247ms on a formula simplification. DAG size of input: 311 DAG size of output 6 [2018-03-28 12:37:56,968 WARN L151 SmtUtils]: Spent 247ms on a formula simplification. DAG size of input: 306 DAG size of output 6 [2018-03-28 12:37:57,436 WARN L151 SmtUtils]: Spent 234ms on a formula simplification. DAG size of input: 301 DAG size of output 6 [2018-03-28 12:37:57,893 WARN L151 SmtUtils]: Spent 222ms on a formula simplification. DAG size of input: 296 DAG size of output 6 [2018-03-28 12:37:58,342 WARN L151 SmtUtils]: Spent 207ms on a formula simplification. DAG size of input: 291 DAG size of output 6 [2018-03-28 12:37:58,773 WARN L151 SmtUtils]: Spent 199ms on a formula simplification. DAG size of input: 286 DAG size of output 6 [2018-03-28 12:37:59,199 WARN L151 SmtUtils]: Spent 200ms on a formula simplification. DAG size of input: 281 DAG size of output 6 [2018-03-28 12:37:59,651 WARN L151 SmtUtils]: Spent 214ms on a formula simplification. DAG size of input: 276 DAG size of output 6 [2018-03-28 12:38:00,083 WARN L151 SmtUtils]: Spent 190ms on a formula simplification. DAG size of input: 271 DAG size of output 6 [2018-03-28 12:38:00,522 WARN L151 SmtUtils]: Spent 194ms on a formula simplification. DAG size of input: 266 DAG size of output 6 [2018-03-28 12:38:00,961 WARN L151 SmtUtils]: Spent 181ms on a formula simplification. DAG size of input: 261 DAG size of output 6 [2018-03-28 12:38:01,387 WARN L151 SmtUtils]: Spent 172ms on a formula simplification. DAG size of input: 256 DAG size of output 6 [2018-03-28 12:38:01,797 WARN L151 SmtUtils]: Spent 171ms on a formula simplification. DAG size of input: 251 DAG size of output 6 [2018-03-28 12:38:02,211 WARN L151 SmtUtils]: Spent 161ms on a formula simplification. DAG size of input: 246 DAG size of output 6 [2018-03-28 12:38:02,612 WARN L151 SmtUtils]: Spent 161ms on a formula simplification. DAG size of input: 241 DAG size of output 6 [2018-03-28 12:38:03,007 WARN L151 SmtUtils]: Spent 152ms on a formula simplification. DAG size of input: 236 DAG size of output 6 [2018-03-28 12:38:03,398 WARN L151 SmtUtils]: Spent 151ms on a formula simplification. DAG size of input: 231 DAG size of output 6 [2018-03-28 12:38:03,773 WARN L151 SmtUtils]: Spent 136ms on a formula simplification. DAG size of input: 226 DAG size of output 6 [2018-03-28 12:38:04,143 WARN L151 SmtUtils]: Spent 132ms on a formula simplification. DAG size of input: 221 DAG size of output 6 [2018-03-28 12:38:04,504 WARN L151 SmtUtils]: Spent 124ms on a formula simplification. DAG size of input: 216 DAG size of output 6 [2018-03-28 12:38:04,867 WARN L151 SmtUtils]: Spent 129ms on a formula simplification. DAG size of input: 211 DAG size of output 6 [2018-03-28 12:38:05,213 WARN L151 SmtUtils]: Spent 115ms on a formula simplification. DAG size of input: 206 DAG size of output 6 [2018-03-28 12:38:05,568 WARN L151 SmtUtils]: Spent 116ms on a formula simplification. DAG size of input: 201 DAG size of output 6 [2018-03-28 12:38:05,902 WARN L151 SmtUtils]: Spent 108ms on a formula simplification. DAG size of input: 196 DAG size of output 6 [2018-03-28 12:38:06,230 WARN L151 SmtUtils]: Spent 101ms on a formula simplification. DAG size of input: 191 DAG size of output 6 [2018-03-28 12:38:06,566 WARN L151 SmtUtils]: Spent 102ms on a formula simplification. DAG size of input: 186 DAG size of output 6 [2018-03-28 12:38:19,683 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:19,683 INFO L93 Difference]: Finished difference Result 29322 states and 33062 transitions. [2018-03-28 12:38:19,684 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-03-28 12:38:19,684 INFO L78 Accepts]: Start accepts. Automaton has 128 states. Word has length 443 [2018-03-28 12:38:19,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:19,758 INFO L225 Difference]: With dead ends: 29322 [2018-03-28 12:38:19,758 INFO L226 Difference]: Without dead ends: 29319 [2018-03-28 12:38:19,765 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 947 GetRequests, 759 SyntacticMatches, 0 SemanticMatches, 188 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1891 ImplicationChecksByTransitivity, 21.8s TimeCoverageRelationStatistics Valid=12158, Invalid=23752, Unknown=0, NotChecked=0, Total=35910 [2018-03-28 12:38:19,777 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29319 states. [2018-03-28 12:38:20,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29319 to 1157. [2018-03-28 12:38:20,179 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:20,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1298 transitions. [2018-03-28 12:38:20,181 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1298 transitions. Word has length 443 [2018-03-28 12:38:20,181 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:20,181 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1298 transitions. [2018-03-28 12:38:20,181 INFO L460 AbstractCegarLoop]: Interpolant automaton has 128 states. [2018-03-28 12:38:20,181 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1298 transitions. [2018-03-28 12:38:20,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 500 [2018-03-28 12:38:20,184 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:20,185 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-28 12:38:20,185 INFO L408 AbstractCegarLoop]: === Iteration 28 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:20,185 INFO L82 PathProgramCache]: Analyzing trace with hash 1232187611, 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-28 12:38:20,228 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:20,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:20,309 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:21,435 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-28 12:38:21,436 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:22,428 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-28 12:38:22,449 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:22,449 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [52, 52] total 85 [2018-03-28 12:38:22,450 INFO L442 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-03-28 12:38:22,450 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-03-28 12:38:22,450 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1137, Invalid=6003, Unknown=0, NotChecked=0, Total=7140 [2018-03-28 12:38:22,451 INFO L87 Difference]: Start difference. First operand 1157 states and 1298 transitions. Second operand 85 states. [2018-03-28 12:38:23,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:23,721 INFO L93 Difference]: Finished difference Result 1417 states and 1588 transitions. [2018-03-28 12:38:23,721 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 68 states. [2018-03-28 12:38:23,721 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 499 [2018-03-28 12:38:23,721 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:23,724 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:23,724 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:23,726 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1029 GetRequests, 897 SyntacticMatches, 17 SemanticMatches, 115 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3517 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2849, Invalid=10723, Unknown=0, NotChecked=0, Total=13572 [2018-03-28 12:38:23,727 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:23,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:23,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:23,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1297 transitions. [2018-03-28 12:38:23,938 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1297 transitions. Word has length 499 [2018-03-28 12:38:23,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:23,939 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1297 transitions. [2018-03-28 12:38:23,939 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-03-28 12:38:23,939 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1297 transitions. [2018-03-28 12:38:23,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 507 [2018-03-28 12:38:23,941 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:23,941 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-28 12:38:23,942 INFO L408 AbstractCegarLoop]: === Iteration 29 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:23,942 INFO L82 PathProgramCache]: Analyzing trace with hash 1001423071, 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-28 12:38:23,947 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:24,012 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:24,018 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:25,017 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-28 12:38:25,018 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:26,161 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-28 12:38:26,182 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:26,183 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55, 55] total 90 [2018-03-28 12:38:26,183 INFO L442 AbstractCegarLoop]: Interpolant automaton has 90 states [2018-03-28 12:38:26,184 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 90 interpolants. [2018-03-28 12:38:26,184 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1267, Invalid=6743, Unknown=0, NotChecked=0, Total=8010 [2018-03-28 12:38:26,184 INFO L87 Difference]: Start difference. First operand 1157 states and 1297 transitions. Second operand 90 states. [2018-03-28 12:38:27,642 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:27,642 INFO L93 Difference]: Finished difference Result 1417 states and 1587 transitions. [2018-03-28 12:38:27,643 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-03-28 12:38:27,643 INFO L78 Accepts]: Start accepts. Automaton has 90 states. Word has length 506 [2018-03-28 12:38:27,643 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:27,644 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:27,644 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:27,645 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-28 12:38:27,646 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:27,806 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:27,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:27,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1296 transitions. [2018-03-28 12:38:27,808 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1296 transitions. Word has length 506 [2018-03-28 12:38:27,808 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:27,808 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1296 transitions. [2018-03-28 12:38:27,808 INFO L460 AbstractCegarLoop]: Interpolant automaton has 90 states. [2018-03-28 12:38:27,808 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1296 transitions. [2018-03-28 12:38:27,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 514 [2018-03-28 12:38:27,812 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:27,812 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-28 12:38:27,813 INFO L408 AbstractCegarLoop]: === Iteration 30 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:27,813 INFO L82 PathProgramCache]: Analyzing trace with hash 2074895451, 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-28 12:38:27,820 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:27,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:27,895 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:28,803 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-28 12:38:28,803 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:30,048 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-28 12:38:30,070 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:30,070 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [58, 58] total 95 [2018-03-28 12:38:30,071 INFO L442 AbstractCegarLoop]: Interpolant automaton has 95 states [2018-03-28 12:38:30,071 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 95 interpolants. [2018-03-28 12:38:30,072 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1404, Invalid=7526, Unknown=0, NotChecked=0, Total=8930 [2018-03-28 12:38:30,072 INFO L87 Difference]: Start difference. First operand 1157 states and 1296 transitions. Second operand 95 states. [2018-03-28 12:38:31,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:31,541 INFO L93 Difference]: Finished difference Result 1417 states and 1586 transitions. [2018-03-28 12:38:31,542 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2018-03-28 12:38:31,542 INFO L78 Accepts]: Start accepts. Automaton has 95 states. Word has length 513 [2018-03-28 12:38:31,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:31,545 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:31,545 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:31,548 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1061 GetRequests, 913 SyntacticMatches, 19 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4442 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=3546, Invalid=13484, Unknown=0, NotChecked=0, Total=17030 [2018-03-28 12:38:31,549 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:31,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:31,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:31,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1295 transitions. [2018-03-28 12:38:31,799 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1295 transitions. Word has length 513 [2018-03-28 12:38:31,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:31,800 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1295 transitions. [2018-03-28 12:38:31,800 INFO L460 AbstractCegarLoop]: Interpolant automaton has 95 states. [2018-03-28 12:38:31,800 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1295 transitions. [2018-03-28 12:38:31,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 521 [2018-03-28 12:38:31,804 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:31,804 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-28 12:38:31,804 INFO L408 AbstractCegarLoop]: === Iteration 31 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:31,805 INFO L82 PathProgramCache]: Analyzing trace with hash 1462558047, 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-28 12:38:31,813 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:31,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:31,879 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:33,012 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-28 12:38:33,012 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:34,315 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-28 12:38:34,336 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:34,337 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61, 61] total 100 [2018-03-28 12:38:34,337 INFO L442 AbstractCegarLoop]: Interpolant automaton has 100 states [2018-03-28 12:38:34,338 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 100 interpolants. [2018-03-28 12:38:34,338 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1548, Invalid=8352, Unknown=0, NotChecked=0, Total=9900 [2018-03-28 12:38:34,338 INFO L87 Difference]: Start difference. First operand 1157 states and 1295 transitions. Second operand 100 states. [2018-03-28 12:38:35,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:35,990 INFO L93 Difference]: Finished difference Result 1417 states and 1585 transitions. [2018-03-28 12:38:35,990 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 80 states. [2018-03-28 12:38:35,990 INFO L78 Accepts]: Start accepts. Automaton has 100 states. Word has length 520 [2018-03-28 12:38:35,990 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:35,992 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:35,992 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:35,995 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1077 GetRequests, 921 SyntacticMatches, 20 SemanticMatches, 136 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4945 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=3923, Invalid=14983, Unknown=0, NotChecked=0, Total=18906 [2018-03-28 12:38:35,996 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:36,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:36,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:36,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1294 transitions. [2018-03-28 12:38:36,153 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1294 transitions. Word has length 520 [2018-03-28 12:38:36,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:36,153 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1294 transitions. [2018-03-28 12:38:36,153 INFO L460 AbstractCegarLoop]: Interpolant automaton has 100 states. [2018-03-28 12:38:36,153 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1294 transitions. [2018-03-28 12:38:36,156 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 528 [2018-03-28 12:38:36,156 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:36,156 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-28 12:38:36,156 INFO L408 AbstractCegarLoop]: === Iteration 32 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:36,157 INFO L82 PathProgramCache]: Analyzing trace with hash -1721305125, 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-28 12:38:36,162 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:36,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:36,222 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:37,361 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-28 12:38:37,361 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:38,783 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-28 12:38:38,804 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:38,805 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [64, 64] total 105 [2018-03-28 12:38:38,805 INFO L442 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-03-28 12:38:38,806 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-03-28 12:38:38,806 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1699, Invalid=9221, Unknown=0, NotChecked=0, Total=10920 [2018-03-28 12:38:38,806 INFO L87 Difference]: Start difference. First operand 1157 states and 1294 transitions. Second operand 105 states. [2018-03-28 12:38:40,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:40,394 INFO L93 Difference]: Finished difference Result 1417 states and 1584 transitions. [2018-03-28 12:38:40,394 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-03-28 12:38:40,394 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 527 [2018-03-28 12:38:40,395 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:40,396 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:40,396 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:40,398 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1093 GetRequests, 929 SyntacticMatches, 21 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5475 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=4319, Invalid=16561, Unknown=0, NotChecked=0, Total=20880 [2018-03-28 12:38:40,398 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:40,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:40,536 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:40,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1293 transitions. [2018-03-28 12:38:40,537 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1293 transitions. Word has length 527 [2018-03-28 12:38:40,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:40,538 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1293 transitions. [2018-03-28 12:38:40,538 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-03-28 12:38:40,538 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1293 transitions. [2018-03-28 12:38:40,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 535 [2018-03-28 12:38:40,540 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:40,541 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-28 12:38:40,541 INFO L408 AbstractCegarLoop]: === Iteration 33 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:40,541 INFO L82 PathProgramCache]: Analyzing trace with hash 1905088991, 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-28 12:38:40,546 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:40,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:40,603 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:41,750 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-28 12:38:41,750 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:43,399 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-28 12:38:43,420 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:43,421 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67, 67] total 110 [2018-03-28 12:38:43,421 INFO L442 AbstractCegarLoop]: Interpolant automaton has 110 states [2018-03-28 12:38:43,422 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 110 interpolants. [2018-03-28 12:38:43,422 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1857, Invalid=10133, Unknown=0, NotChecked=0, Total=11990 [2018-03-28 12:38:43,422 INFO L87 Difference]: Start difference. First operand 1157 states and 1293 transitions. Second operand 110 states. [2018-03-28 12:38:45,181 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:45,182 INFO L93 Difference]: Finished difference Result 1417 states and 1583 transitions. [2018-03-28 12:38:45,182 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 88 states. [2018-03-28 12:38:45,182 INFO L78 Accepts]: Start accepts. Automaton has 110 states. Word has length 534 [2018-03-28 12:38:45,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:45,183 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:45,183 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:45,185 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1109 GetRequests, 937 SyntacticMatches, 22 SemanticMatches, 150 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6032 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=4734, Invalid=18218, Unknown=0, NotChecked=0, Total=22952 [2018-03-28 12:38:45,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:45,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:45,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:45,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1292 transitions. [2018-03-28 12:38:45,323 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1292 transitions. Word has length 534 [2018-03-28 12:38:45,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:45,323 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1292 transitions. [2018-03-28 12:38:45,324 INFO L460 AbstractCegarLoop]: Interpolant automaton has 110 states. [2018-03-28 12:38:45,324 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1292 transitions. [2018-03-28 12:38:45,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 542 [2018-03-28 12:38:45,326 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:45,326 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-28 12:38:45,326 INFO L408 AbstractCegarLoop]: === Iteration 34 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:45,326 INFO L82 PathProgramCache]: Analyzing trace with hash 358181723, 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-28 12:38:45,332 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:45,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:45,392 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:46,632 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-28 12:38:46,632 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:48,322 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-28 12:38:48,344 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:48,344 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [70, 70] total 115 [2018-03-28 12:38:48,344 INFO L442 AbstractCegarLoop]: Interpolant automaton has 115 states [2018-03-28 12:38:48,345 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 115 interpolants. [2018-03-28 12:38:48,345 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2022, Invalid=11088, Unknown=0, NotChecked=0, Total=13110 [2018-03-28 12:38:48,345 INFO L87 Difference]: Start difference. First operand 1157 states and 1292 transitions. Second operand 115 states. [2018-03-28 12:38:50,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:50,307 INFO L93 Difference]: Finished difference Result 1417 states and 1582 transitions. [2018-03-28 12:38:50,307 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 92 states. [2018-03-28 12:38:50,307 INFO L78 Accepts]: Start accepts. Automaton has 115 states. Word has length 541 [2018-03-28 12:38:50,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:50,309 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:50,309 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:50,311 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1125 GetRequests, 945 SyntacticMatches, 23 SemanticMatches, 157 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6616 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=5168, Invalid=19954, Unknown=0, NotChecked=0, Total=25122 [2018-03-28 12:38:50,311 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:50,450 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:50,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:50,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1291 transitions. [2018-03-28 12:38:50,451 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1291 transitions. Word has length 541 [2018-03-28 12:38:50,451 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:50,452 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1291 transitions. [2018-03-28 12:38:50,452 INFO L460 AbstractCegarLoop]: Interpolant automaton has 115 states. [2018-03-28 12:38:50,452 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1291 transitions. [2018-03-28 12:38:50,454 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 549 [2018-03-28 12:38:50,454 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:50,454 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-28 12:38:50,454 INFO L408 AbstractCegarLoop]: === Iteration 35 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:50,455 INFO L82 PathProgramCache]: Analyzing trace with hash 421131871, 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-28 12:38:50,461 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:50,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:50,520 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:51,845 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-28 12:38:51,845 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:53,684 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-28 12:38:53,706 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:53,724 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73, 73] total 120 [2018-03-28 12:38:53,725 INFO L442 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-03-28 12:38:53,726 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-03-28 12:38:53,726 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2194, Invalid=12086, Unknown=0, NotChecked=0, Total=14280 [2018-03-28 12:38:53,726 INFO L87 Difference]: Start difference. First operand 1157 states and 1291 transitions. Second operand 120 states. [2018-03-28 12:38:56,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:38:56,068 INFO L93 Difference]: Finished difference Result 1417 states and 1581 transitions. [2018-03-28 12:38:56,068 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-03-28 12:38:56,068 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 548 [2018-03-28 12:38:56,068 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:38:56,069 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:38:56,069 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:38:56,071 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1141 GetRequests, 953 SyntacticMatches, 24 SemanticMatches, 164 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7227 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=5621, Invalid=21769, Unknown=0, NotChecked=0, Total=27390 [2018-03-28 12:38:56,071 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:38:56,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:38:56,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:38:56,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1290 transitions. [2018-03-28 12:38:56,210 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1290 transitions. Word has length 548 [2018-03-28 12:38:56,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:38:56,210 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1290 transitions. [2018-03-28 12:38:56,210 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-03-28 12:38:56,210 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1290 transitions. [2018-03-28 12:38:56,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 556 [2018-03-28 12:38:56,213 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:38:56,213 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-28 12:38:56,213 INFO L408 AbstractCegarLoop]: === Iteration 36 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:38:56,213 INFO L82 PathProgramCache]: Analyzing trace with hash 1077657307, 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-28 12:38:56,219 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:38:56,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:38:56,279 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:38:57,695 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-28 12:38:57,695 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:38:59,641 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-28 12:38:59,662 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:38:59,680 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [76, 76] total 125 [2018-03-28 12:38:59,681 INFO L442 AbstractCegarLoop]: Interpolant automaton has 125 states [2018-03-28 12:38:59,681 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 125 interpolants. [2018-03-28 12:38:59,682 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2373, Invalid=13127, Unknown=0, NotChecked=0, Total=15500 [2018-03-28 12:38:59,682 INFO L87 Difference]: Start difference. First operand 1157 states and 1290 transitions. Second operand 125 states. [2018-03-28 12:39:01,868 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:39:01,868 INFO L93 Difference]: Finished difference Result 1417 states and 1580 transitions. [2018-03-28 12:39:01,869 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-03-28 12:39:01,869 INFO L78 Accepts]: Start accepts. Automaton has 125 states. Word has length 555 [2018-03-28 12:39:01,869 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:39:01,870 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:39:01,870 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:39:01,872 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1157 GetRequests, 961 SyntacticMatches, 25 SemanticMatches, 171 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7865 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=6093, Invalid=23663, Unknown=0, NotChecked=0, Total=29756 [2018-03-28 12:39:01,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:39:02,032 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:39:02,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:39:02,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1289 transitions. [2018-03-28 12:39:02,033 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1289 transitions. Word has length 555 [2018-03-28 12:39:02,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:39:02,033 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1289 transitions. [2018-03-28 12:39:02,033 INFO L460 AbstractCegarLoop]: Interpolant automaton has 125 states. [2018-03-28 12:39:02,034 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1289 transitions. [2018-03-28 12:39:02,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 563 [2018-03-28 12:39:02,036 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:39:02,036 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-28 12:39:02,036 INFO L408 AbstractCegarLoop]: === Iteration 37 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:39:02,037 INFO L82 PathProgramCache]: Analyzing trace with hash 1041937119, 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-28 12:39:02,042 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:39:02,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:39:02,101 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-03-28 12:39:03,619 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-28 12:39:03,619 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:39:05,760 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-28 12:39:05,794 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-03-28 12:39:05,794 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [79, 79] total 130 [2018-03-28 12:39:05,795 INFO L442 AbstractCegarLoop]: Interpolant automaton has 130 states [2018-03-28 12:39:05,795 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 130 interpolants. [2018-03-28 12:39:05,796 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=2559, Invalid=14211, Unknown=0, NotChecked=0, Total=16770 [2018-03-28 12:39:05,796 INFO L87 Difference]: Start difference. First operand 1157 states and 1289 transitions. Second operand 130 states. [2018-03-28 12:39:08,364 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-03-28 12:39:08,365 INFO L93 Difference]: Finished difference Result 1417 states and 1579 transitions. [2018-03-28 12:39:08,365 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 104 states. [2018-03-28 12:39:08,365 INFO L78 Accepts]: Start accepts. Automaton has 130 states. Word has length 562 [2018-03-28 12:39:08,365 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-03-28 12:39:08,366 INFO L225 Difference]: With dead ends: 1417 [2018-03-28 12:39:08,366 INFO L226 Difference]: Without dead ends: 1157 [2018-03-28 12:39:08,368 INFO L567 BasicCegarLoop]: 0 DeclaredPredicates, 1173 GetRequests, 969 SyntacticMatches, 26 SemanticMatches, 178 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8530 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=6584, Invalid=25636, Unknown=0, NotChecked=0, Total=32220 [2018-03-28 12:39:08,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1157 states. [2018-03-28 12:39:08,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1157 to 1157. [2018-03-28 12:39:08,544 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1157 states. [2018-03-28 12:39:08,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1157 states to 1157 states and 1288 transitions. [2018-03-28 12:39:08,545 INFO L78 Accepts]: Start accepts. Automaton has 1157 states and 1288 transitions. Word has length 562 [2018-03-28 12:39:08,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-03-28 12:39:08,546 INFO L459 AbstractCegarLoop]: Abstraction has 1157 states and 1288 transitions. [2018-03-28 12:39:08,546 INFO L460 AbstractCegarLoop]: Interpolant automaton has 130 states. [2018-03-28 12:39:08,546 INFO L276 IsEmpty]: Start isEmpty. Operand 1157 states and 1288 transitions. [2018-03-28 12:39:08,549 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 570 [2018-03-28 12:39:08,550 INFO L347 BasicCegarLoop]: Found error trace [2018-03-28 12:39:08,550 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-28 12:39:08,550 INFO L408 AbstractCegarLoop]: === Iteration 38 === [mainErr3AssertViolationARRAY_INDEX, mainErr4AssertViolationARRAY_INDEX, mainErr1AssertViolationARRAY_INDEX, mainErr2AssertViolationARRAY_INDEX, mainErr0AssertViolationARRAY_INDEX]=== [2018-03-28 12:39:08,550 INFO L82 PathProgramCache]: Analyzing trace with hash -926551461, 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-28 12:39:08,556 INFO L68 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-03-28 12:39:08,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-03-28 12:39:08,623 INFO L270 TraceCheckSpWp]: Computing forward predicates... Received shutdown request... [2018-03-28 12:39:10,239 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-28 12:39:10,239 INFO L314 TraceCheckSpWp]: Computing backward predicates... [2018-03-28 12:39:10,241 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-03-28 12:39:10,241 WARN L519 AbstractCegarLoop]: Verification canceled [2018-03-28 12:39:10,244 WARN L197 ceAbstractionStarter]: Timeout [2018-03-28 12:39:10,244 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.03 12:39:10 BoogieIcfgContainer [2018-03-28 12:39:10,245 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-03-28 12:39:10,245 INFO L168 Benchmark]: Toolchain (without parser) took 125088.10 ms. Allocated memory was 306.2 MB in the beginning and 1.3 GB in the end (delta: 953.2 MB). Free memory was 249.5 MB in the beginning and 1.1 GB in the end (delta: -841.1 MB). Peak memory consumption was 112.0 MB. Max. memory is 5.3 GB. [2018-03-28 12:39:10,246 INFO L168 Benchmark]: CDTParser took 0.19 ms. Allocated memory is still 306.2 MB. Free memory is still 268.7 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-03-28 12:39:10,247 INFO L168 Benchmark]: CACSL2BoogieTranslator took 182.88 ms. Allocated memory is still 306.2 MB. Free memory was 249.5 MB in the beginning and 240.4 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 5.3 GB. [2018-03-28 12:39:10,247 INFO L168 Benchmark]: Boogie Preprocessor took 23.26 ms. Allocated memory is still 306.2 MB. Free memory was 240.4 MB in the beginning and 238.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-03-28 12:39:10,247 INFO L168 Benchmark]: RCFGBuilder took 272.17 ms. Allocated memory was 306.2 MB in the beginning and 472.9 MB in the end (delta: 166.7 MB). Free memory was 238.4 MB in the beginning and 443.9 MB in the end (delta: -205.5 MB). Peak memory consumption was 23.3 MB. Max. memory is 5.3 GB. [2018-03-28 12:39:10,248 INFO L168 Benchmark]: TraceAbstraction took 124604.27 ms. Allocated memory was 472.9 MB in the beginning and 1.3 GB in the end (delta: 786.4 MB). Free memory was 442.6 MB in the beginning and 1.1 GB in the end (delta: -648.0 MB). Peak memory consumption was 138.5 MB. Max. memory is 5.3 GB. [2018-03-28 12:39:10,249 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 306.2 MB. Free memory is still 268.7 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 182.88 ms. Allocated memory is still 306.2 MB. Free memory was 249.5 MB in the beginning and 240.4 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 23.26 ms. Allocated memory is still 306.2 MB. Free memory was 240.4 MB in the beginning and 238.4 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 272.17 ms. Allocated memory was 306.2 MB in the beginning and 472.9 MB in the end (delta: 166.7 MB). Free memory was 238.4 MB in the beginning and 443.9 MB in the end (delta: -205.5 MB). Peak memory consumption was 23.3 MB. Max. memory is 5.3 GB. * TraceAbstraction took 124604.27 ms. Allocated memory was 472.9 MB in the beginning and 1.3 GB in the end (delta: 786.4 MB). Free memory was 442.6 MB in the beginning and 1.1 GB in the end (delta: -648.0 MB). Peak memory consumption was 138.5 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 PartialQuantifierElimination was doing sequential composition of 3 TransFormulas, while SimplifyDDAWithTimeout was simplifying term of DAG size 1. - 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 PartialQuantifierElimination was doing sequential composition of 3 TransFormulas, while SimplifyDDAWithTimeout was simplifying term of DAG size 1. - 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 PartialQuantifierElimination was doing sequential composition of 3 TransFormulas, while SimplifyDDAWithTimeout was simplifying term of DAG size 1. - 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 PartialQuantifierElimination was doing sequential composition of 3 TransFormulas, while SimplifyDDAWithTimeout was simplifying term of DAG size 1. - 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 PartialQuantifierElimination was doing sequential composition of 3 TransFormulas, while SimplifyDDAWithTimeout was simplifying term of DAG size 1. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 39 locations, 5 error locations. TIMEOUT Result, 124.5s OverallTime, 38 OverallIterations, 63 TraceHistogramMax, 69.3s 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.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 20265 GetRequests, 16967 SyntacticMatches, 351 SemanticMatches, 2947 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82577 ImplicationChecksByTransitivity, 78.5s 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, 1.0s SatisfiabilityAnalysisTime, 47.7s 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_AutomizerC.xml/Csv-Benchmark-0-2018-03-28_12-39-10-259.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_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-03-28_12-39-10-259.csv Completed graceful shutdown