java -Xmx8000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerBpl.xml --generate-csv --csv-dir csv -s ../../../trunk/examples/programs/regression/bpl/AutomizerBpl-pdr.epf -i ../../../trunk/examples/programs/20170304-DifficultPathPrograms/s3_srvr_1.cil.c_23.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-56c9370 [2018-07-23 16:14:02,426 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-07-23 16:14:02,428 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-07-23 16:14:02,440 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-07-23 16:14:02,440 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-07-23 16:14:02,441 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-07-23 16:14:02,442 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-07-23 16:14:02,444 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-07-23 16:14:02,446 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-07-23 16:14:02,447 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-07-23 16:14:02,448 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-07-23 16:14:02,448 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-07-23 16:14:02,449 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-07-23 16:14:02,450 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-07-23 16:14:02,451 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-07-23 16:14:02,452 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-07-23 16:14:02,453 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-07-23 16:14:02,455 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-07-23 16:14:02,457 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-07-23 16:14:02,459 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-07-23 16:14:02,460 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-07-23 16:14:02,461 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-07-23 16:14:02,466 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-07-23 16:14:02,466 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-07-23 16:14:02,466 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-07-23 16:14:02,468 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-07-23 16:14:02,471 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-07-23 16:14:02,472 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-07-23 16:14:02,472 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-07-23 16:14:02,475 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-07-23 16:14:02,476 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-07-23 16:14:02,479 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-07-23 16:14:02,479 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-07-23 16:14:02,479 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-07-23 16:14:02,481 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-07-23 16:14:02,482 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-07-23 16:14:02,482 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/regression/bpl/AutomizerBpl-pdr.epf [2018-07-23 16:14:02,490 INFO L110 SettingsManager]: Loading preferences was successful [2018-07-23 16:14:02,490 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-07-23 16:14:02,492 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-07-23 16:14:02,492 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=PDR [2018-07-23 16:14:02,492 INFO L133 SettingsManager]: * Use separate solver for trace checks=false [2018-07-23 16:14:02,492 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-07-23 16:14:02,536 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-07-23 16:14:02,553 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-07-23 16:14:02,560 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-07-23 16:14:02,563 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-07-23 16:14:02,563 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-07-23 16:14:02,564 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/s3_srvr_1.cil.c_23.bpl [2018-07-23 16:14:02,565 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/s3_srvr_1.cil.c_23.bpl' [2018-07-23 16:14:02,644 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-07-23 16:14:02,646 INFO L131 ToolchainWalker]: Walking toolchain with 3 elements. [2018-07-23 16:14:02,647 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-07-23 16:14:02,647 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-07-23 16:14:02,647 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-07-23 16:14:02,674 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... [2018-07-23 16:14:02,675 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... [2018-07-23 16:14:02,689 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... [2018-07-23 16:14:02,689 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... [2018-07-23 16:14:02,699 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... [2018-07-23 16:14:02,704 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... [2018-07-23 16:14:02,710 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... [2018-07-23 16:14:02,721 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-07-23 16:14:02,725 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-07-23 16:14:02,725 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-07-23 16:14:02,725 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-07-23 16:14:02,726 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-07-23 16:14:02,801 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-07-23 16:14:02,801 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-07-23 16:14:03,557 INFO L261 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-07-23 16:14:03,557 INFO L202 PluginConnector]: Adding new model s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.07 04:14:03 BoogieIcfgContainer [2018-07-23 16:14:03,558 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-07-23 16:14:03,559 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-07-23 16:14:03,560 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-07-23 16:14:03,563 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-07-23 16:14:03,563 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 23.07 04:14:02" (1/2) ... [2018-07-23 16:14:03,564 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4400d976 and model type s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.07 04:14:03, skipping insertion in model container [2018-07-23 16:14:03,565 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.07 04:14:03" (2/2) ... [2018-07-23 16:14:03,567 INFO L112 eAbstractionObserver]: Analyzing ICFG s3_srvr_1.cil.c_23.bpl [2018-07-23 16:14:03,576 INFO L132 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:PDR Determinization: PREDICATE_ABSTRACTION [2018-07-23 16:14:03,584 INFO L144 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-07-23 16:14:03,632 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-07-23 16:14:03,633 INFO L373 AbstractCegarLoop]: Interprodecural is true [2018-07-23 16:14:03,634 INFO L374 AbstractCegarLoop]: Hoare is true [2018-07-23 16:14:03,634 INFO L375 AbstractCegarLoop]: Compute interpolants for PDR [2018-07-23 16:14:03,634 INFO L376 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-07-23 16:14:03,634 INFO L377 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-07-23 16:14:03,634 INFO L378 AbstractCegarLoop]: Difference is false [2018-07-23 16:14:03,635 INFO L379 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-07-23 16:14:03,635 INFO L384 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-07-23 16:14:03,654 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states. [2018-07-23 16:14:03,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-07-23 16:14:03,662 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:03,663 INFO L353 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:03,663 INFO L414 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:03,668 INFO L82 PathProgramCache]: Analyzing trace with hash 1511424245, now seen corresponding path program 1 times [2018-07-23 16:14:03,673 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:04,693 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:14:04,693 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-07-23 16:14:04,698 INFO L450 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-07-23 16:14:04,704 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-07-23 16:14:04,705 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-07-23 16:14:04,708 INFO L87 Difference]: Start difference. First operand 20 states. Second operand 4 states. [2018-07-23 16:14:05,126 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:14:05,127 INFO L93 Difference]: Finished difference Result 51 states and 87 transitions. [2018-07-23 16:14:05,127 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-07-23 16:14:05,129 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 16 [2018-07-23 16:14:05,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:14:05,145 INFO L225 Difference]: With dead ends: 51 [2018-07-23 16:14:05,145 INFO L226 Difference]: Without dead ends: 48 [2018-07-23 16:14:05,149 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 1010 GetRequests, 994 SyntacticMatches, 12 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-07-23 16:14:05,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2018-07-23 16:14:05,189 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-07-23 16:14:05,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-07-23 16:14:05,192 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 83 transitions. [2018-07-23 16:14:05,194 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 83 transitions. Word has length 16 [2018-07-23 16:14:05,194 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:14:05,195 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 83 transitions. [2018-07-23 16:14:05,195 INFO L472 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-07-23 16:14:05,195 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 83 transitions. [2018-07-23 16:14:05,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-07-23 16:14:05,197 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:05,197 INFO L353 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:05,198 INFO L414 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:05,198 INFO L82 PathProgramCache]: Analyzing trace with hash -478818365, now seen corresponding path program 1 times [2018-07-23 16:14:05,198 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:06,145 WARN L169 SmtUtils]: Spent 154.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-07-23 16:14:06,416 WARN L169 SmtUtils]: Spent 146.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-07-23 16:14:06,711 WARN L169 SmtUtils]: Spent 195.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 24 [2018-07-23 16:14:06,971 WARN L169 SmtUtils]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2018-07-23 16:14:07,640 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:14:07,641 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-07-23 16:14:07,642 INFO L450 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-07-23 16:14:07,642 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-07-23 16:14:07,643 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-07-23 16:14:07,643 INFO L87 Difference]: Start difference. First operand 48 states and 83 transitions. Second operand 6 states. [2018-07-23 16:14:07,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:14:07,962 INFO L93 Difference]: Finished difference Result 65 states and 112 transitions. [2018-07-23 16:14:07,965 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-07-23 16:14:07,966 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 39 [2018-07-23 16:14:07,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:14:07,968 INFO L225 Difference]: With dead ends: 65 [2018-07-23 16:14:07,968 INFO L226 Difference]: Without dead ends: 63 [2018-07-23 16:14:07,972 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 3516 GetRequests, 3488 SyntacticMatches, 18 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-07-23 16:14:07,974 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2018-07-23 16:14:07,994 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 48. [2018-07-23 16:14:07,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-07-23 16:14:07,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 83 transitions. [2018-07-23 16:14:07,997 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 83 transitions. Word has length 39 [2018-07-23 16:14:07,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:14:07,997 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 83 transitions. [2018-07-23 16:14:07,999 INFO L472 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-07-23 16:14:07,999 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 83 transitions. [2018-07-23 16:14:08,001 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2018-07-23 16:14:08,001 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:08,001 INFO L353 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:08,001 INFO L414 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:08,002 INFO L82 PathProgramCache]: Analyzing trace with hash -380354350, now seen corresponding path program 1 times [2018-07-23 16:14:08,002 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:09,827 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:14:09,827 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-07-23 16:14:09,828 INFO L450 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-07-23 16:14:09,828 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-07-23 16:14:09,829 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-07-23 16:14:09,829 INFO L87 Difference]: Start difference. First operand 48 states and 83 transitions. Second operand 5 states. [2018-07-23 16:14:10,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:14:10,037 INFO L93 Difference]: Finished difference Result 80 states and 139 transitions. [2018-07-23 16:14:10,038 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-07-23 16:14:10,038 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 44 [2018-07-23 16:14:10,038 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:14:10,039 INFO L225 Difference]: With dead ends: 80 [2018-07-23 16:14:10,040 INFO L226 Difference]: Without dead ends: 78 [2018-07-23 16:14:10,040 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 5856 GetRequests, 5823 SyntacticMatches, 23 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-07-23 16:14:10,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2018-07-23 16:14:10,058 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 69. [2018-07-23 16:14:10,058 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 69 states. [2018-07-23 16:14:10,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 121 transitions. [2018-07-23 16:14:10,060 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 121 transitions. Word has length 44 [2018-07-23 16:14:10,060 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:14:10,060 INFO L471 AbstractCegarLoop]: Abstraction has 69 states and 121 transitions. [2018-07-23 16:14:10,060 INFO L472 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-07-23 16:14:10,060 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 121 transitions. [2018-07-23 16:14:10,062 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-07-23 16:14:10,062 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:10,062 INFO L353 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:10,063 INFO L414 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:10,063 INFO L82 PathProgramCache]: Analyzing trace with hash -1286157752, now seen corresponding path program 1 times [2018-07-23 16:14:10,063 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:12,941 WARN L169 SmtUtils]: Spent 109.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:14:15,102 WARN L169 SmtUtils]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:14:15,918 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:14:15,919 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-07-23 16:14:15,919 INFO L450 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-07-23 16:14:15,920 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-07-23 16:14:15,920 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=298, Unknown=0, NotChecked=0, Total=420 [2018-07-23 16:14:15,920 INFO L87 Difference]: Start difference. First operand 69 states and 121 transitions. Second operand 6 states. [2018-07-23 16:14:16,467 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:14:16,467 INFO L93 Difference]: Finished difference Result 101 states and 177 transitions. [2018-07-23 16:14:16,467 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-07-23 16:14:16,468 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 52 [2018-07-23 16:14:16,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:14:16,471 INFO L225 Difference]: With dead ends: 101 [2018-07-23 16:14:16,471 INFO L226 Difference]: Without dead ends: 99 [2018-07-23 16:14:16,472 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 14317 GetRequests, 14262 SyntacticMatches, 36 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 435 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=122, Invalid=298, Unknown=0, NotChecked=0, Total=420 [2018-07-23 16:14:16,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states. [2018-07-23 16:14:16,486 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 61. [2018-07-23 16:14:16,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2018-07-23 16:14:16,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 107 transitions. [2018-07-23 16:14:16,488 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 107 transitions. Word has length 52 [2018-07-23 16:14:16,488 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:14:16,488 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 107 transitions. [2018-07-23 16:14:16,488 INFO L472 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-07-23 16:14:16,488 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 107 transitions. [2018-07-23 16:14:16,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2018-07-23 16:14:16,489 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:16,490 INFO L353 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:16,490 INFO L414 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:16,490 INFO L82 PathProgramCache]: Analyzing trace with hash 1287929422, now seen corresponding path program 1 times [2018-07-23 16:14:16,490 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:17,928 WARN L169 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2018-07-23 16:14:18,360 WARN L169 SmtUtils]: Spent 155.00 ms on a formula simplification that was a NOOP. DAG size: 47 [2018-07-23 16:14:21,711 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:14:21,712 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-07-23 16:14:21,712 INFO L450 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-07-23 16:14:21,713 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-07-23 16:14:21,713 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2018-07-23 16:14:21,713 INFO L87 Difference]: Start difference. First operand 61 states and 107 transitions. Second operand 6 states. [2018-07-23 16:14:22,015 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:14:22,016 INFO L93 Difference]: Finished difference Result 119 states and 210 transitions. [2018-07-23 16:14:22,016 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-07-23 16:14:22,016 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 56 [2018-07-23 16:14:22,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:14:22,019 INFO L225 Difference]: With dead ends: 119 [2018-07-23 16:14:22,019 INFO L226 Difference]: Without dead ends: 117 [2018-07-23 16:14:22,020 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 15982 GetRequests, 15935 SyntacticMatches, 33 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 239 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=72, Invalid=168, Unknown=0, NotChecked=0, Total=240 [2018-07-23 16:14:22,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2018-07-23 16:14:22,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 107. [2018-07-23 16:14:22,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 107 states. [2018-07-23 16:14:22,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 191 transitions. [2018-07-23 16:14:22,052 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 191 transitions. Word has length 56 [2018-07-23 16:14:22,052 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:14:22,052 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 191 transitions. [2018-07-23 16:14:22,053 INFO L472 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-07-23 16:14:22,053 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 191 transitions. [2018-07-23 16:14:22,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-07-23 16:14:22,054 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:22,055 INFO L353 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:22,055 INFO L414 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:22,055 INFO L82 PathProgramCache]: Analyzing trace with hash 849757892, now seen corresponding path program 1 times [2018-07-23 16:14:22,055 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:24,766 WARN L169 SmtUtils]: Spent 109.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:14:26,179 WARN L169 SmtUtils]: Spent 146.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-07-23 16:14:27,677 WARN L169 SmtUtils]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:14:30,319 WARN L169 SmtUtils]: Spent 160.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-07-23 16:14:31,522 WARN L169 SmtUtils]: Spent 201.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-07-23 16:14:38,918 WARN L169 SmtUtils]: Spent 249.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-07-23 16:14:41,668 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:14:41,668 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-07-23 16:14:41,668 INFO L450 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-07-23 16:14:41,669 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-07-23 16:14:41,669 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=246, Invalid=624, Unknown=0, NotChecked=0, Total=870 [2018-07-23 16:14:41,670 INFO L87 Difference]: Start difference. First operand 107 states and 191 transitions. Second operand 7 states. [2018-07-23 16:14:42,198 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:14:42,198 INFO L93 Difference]: Finished difference Result 155 states and 275 transitions. [2018-07-23 16:14:42,199 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-07-23 16:14:42,199 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 64 [2018-07-23 16:14:42,200 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:14:42,201 INFO L225 Difference]: With dead ends: 155 [2018-07-23 16:14:42,201 INFO L226 Difference]: Without dead ends: 153 [2018-07-23 16:14:42,202 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 36468 GetRequests, 36389 SyntacticMatches, 51 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1005 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=246, Invalid=624, Unknown=0, NotChecked=0, Total=870 [2018-07-23 16:14:42,203 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2018-07-23 16:14:42,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 86. [2018-07-23 16:14:42,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 86 states. [2018-07-23 16:14:42,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 153 transitions. [2018-07-23 16:14:42,227 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 153 transitions. Word has length 64 [2018-07-23 16:14:42,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:14:42,228 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 153 transitions. [2018-07-23 16:14:42,228 INFO L472 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-07-23 16:14:42,228 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 153 transitions. [2018-07-23 16:14:42,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2018-07-23 16:14:42,230 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:42,230 INFO L353 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:42,230 INFO L414 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:42,230 INFO L82 PathProgramCache]: Analyzing trace with hash 1495584614, now seen corresponding path program 1 times [2018-07-23 16:14:42,230 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:43,887 WARN L169 SmtUtils]: Spent 109.00 ms on a formula simplification that was a NOOP. DAG size: 47 [2018-07-23 16:14:47,150 WARN L169 SmtUtils]: Spent 135.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:14:52,986 WARN L169 SmtUtils]: Spent 151.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:14:54,578 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:14:54,579 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-07-23 16:14:54,579 INFO L450 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-07-23 16:14:54,579 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-07-23 16:14:54,580 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=268, Unknown=0, NotChecked=0, Total=380 [2018-07-23 16:14:54,580 INFO L87 Difference]: Start difference. First operand 86 states and 153 transitions. Second operand 7 states. [2018-07-23 16:14:54,997 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:14:54,997 INFO L93 Difference]: Finished difference Result 156 states and 278 transitions. [2018-07-23 16:14:54,998 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-07-23 16:14:54,998 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 67 [2018-07-23 16:14:54,999 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:14:55,000 INFO L225 Difference]: With dead ends: 156 [2018-07-23 16:14:55,000 INFO L226 Difference]: Without dead ends: 154 [2018-07-23 16:14:55,001 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 32978 GetRequests, 32918 SyntacticMatches, 42 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 418 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=112, Invalid=268, Unknown=0, NotChecked=0, Total=380 [2018-07-23 16:14:55,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2018-07-23 16:14:55,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 143. [2018-07-23 16:14:55,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 143 states. [2018-07-23 16:14:55,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 143 states to 143 states and 257 transitions. [2018-07-23 16:14:55,049 INFO L78 Accepts]: Start accepts. Automaton has 143 states and 257 transitions. Word has length 67 [2018-07-23 16:14:55,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:14:55,050 INFO L471 AbstractCegarLoop]: Abstraction has 143 states and 257 transitions. [2018-07-23 16:14:55,050 INFO L472 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-07-23 16:14:55,050 INFO L276 IsEmpty]: Start isEmpty. Operand 143 states and 257 transitions. [2018-07-23 16:14:55,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2018-07-23 16:14:55,052 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:14:55,052 INFO L353 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:14:55,052 INFO L414 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:14:55,053 INFO L82 PathProgramCache]: Analyzing trace with hash 1796210992, now seen corresponding path program 1 times [2018-07-23 16:14:55,053 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:14:55,522 WARN L169 SmtUtils]: Spent 133.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 32 [2018-07-23 16:14:57,689 WARN L169 SmtUtils]: Spent 117.00 ms on a formula simplification that was a NOOP. DAG size: 47 [2018-07-23 16:14:58,032 WARN L169 SmtUtils]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:14:59,512 WARN L169 SmtUtils]: Spent 203.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-07-23 16:15:01,010 WARN L169 SmtUtils]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:15:03,732 WARN L169 SmtUtils]: Spent 171.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-07-23 16:15:04,666 WARN L169 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 44 [2018-07-23 16:15:05,141 WARN L169 SmtUtils]: Spent 175.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:15:05,520 WARN L169 SmtUtils]: Spent 195.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-07-23 16:15:08,887 WARN L169 SmtUtils]: Spent 242.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2018-07-23 16:15:14,416 WARN L169 SmtUtils]: Spent 203.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-07-23 16:15:20,004 WARN L169 SmtUtils]: Spent 296.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2018-07-23 16:15:22,323 WARN L169 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 47 [2018-07-23 16:15:22,888 WARN L169 SmtUtils]: Spent 292.00 ms on a formula simplification that was a NOOP. DAG size: 73 [2018-07-23 16:15:42,081 WARN L169 SmtUtils]: Spent 307.00 ms on a formula simplification that was a NOOP. DAG size: 73 [2018-07-23 16:15:49,033 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:15:49,034 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-07-23 16:15:49,034 INFO L450 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-07-23 16:15:49,035 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-07-23 16:15:49,035 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=413, Invalid=1069, Unknown=0, NotChecked=0, Total=1482 [2018-07-23 16:15:49,036 INFO L87 Difference]: Start difference. First operand 143 states and 257 transitions. Second operand 8 states. [2018-07-23 16:15:49,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:15:49,555 INFO L93 Difference]: Finished difference Result 219 states and 392 transitions. [2018-07-23 16:15:49,555 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-07-23 16:15:49,556 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 75 [2018-07-23 16:15:49,556 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:15:49,558 INFO L225 Difference]: With dead ends: 219 [2018-07-23 16:15:49,558 INFO L226 Difference]: Without dead ends: 217 [2018-07-23 16:15:49,560 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 72947 GetRequests, 72843 SyntacticMatches, 67 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1794 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=413, Invalid=1069, Unknown=0, NotChecked=0, Total=1482 [2018-07-23 16:15:49,560 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 217 states. [2018-07-23 16:15:49,591 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 217 to 110. [2018-07-23 16:15:49,591 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 110 states. [2018-07-23 16:15:49,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 197 transitions. [2018-07-23 16:15:49,592 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 197 transitions. Word has length 75 [2018-07-23 16:15:49,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:15:49,592 INFO L471 AbstractCegarLoop]: Abstraction has 110 states and 197 transitions. [2018-07-23 16:15:49,593 INFO L472 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-07-23 16:15:49,593 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 197 transitions. [2018-07-23 16:15:49,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2018-07-23 16:15:49,594 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:15:49,594 INFO L353 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:15:49,595 INFO L414 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:15:49,595 INFO L82 PathProgramCache]: Analyzing trace with hash -2139351754, now seen corresponding path program 1 times [2018-07-23 16:15:49,595 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:15:54,766 WARN L169 SmtUtils]: Spent 137.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:16:01,335 WARN L169 SmtUtils]: Spent 142.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:16:02,769 WARN L169 SmtUtils]: Spent 183.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2018-07-23 16:16:14,013 WARN L169 SmtUtils]: Spent 193.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2018-07-23 16:16:17,420 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:16:17,420 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-07-23 16:16:17,421 INFO L450 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-07-23 16:16:17,421 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-07-23 16:16:17,421 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=161, Invalid=391, Unknown=0, NotChecked=0, Total=552 [2018-07-23 16:16:17,421 INFO L87 Difference]: Start difference. First operand 110 states and 197 transitions. Second operand 8 states. [2018-07-23 16:16:18,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:16:18,118 INFO L93 Difference]: Finished difference Result 204 states and 366 transitions. [2018-07-23 16:16:18,118 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-07-23 16:16:18,118 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 77 [2018-07-23 16:16:18,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:16:18,120 INFO L225 Difference]: With dead ends: 204 [2018-07-23 16:16:18,120 INFO L226 Difference]: Without dead ends: 202 [2018-07-23 16:16:18,121 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 57596 GetRequests, 57524 SyntacticMatches, 50 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 631 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=161, Invalid=391, Unknown=0, NotChecked=0, Total=552 [2018-07-23 16:16:18,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states. [2018-07-23 16:16:18,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 189. [2018-07-23 16:16:18,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 189 states. [2018-07-23 16:16:18,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 189 states to 189 states and 341 transitions. [2018-07-23 16:16:18,182 INFO L78 Accepts]: Start accepts. Automaton has 189 states and 341 transitions. Word has length 77 [2018-07-23 16:16:18,183 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:16:18,183 INFO L471 AbstractCegarLoop]: Abstraction has 189 states and 341 transitions. [2018-07-23 16:16:18,183 INFO L472 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-07-23 16:16:18,183 INFO L276 IsEmpty]: Start isEmpty. Operand 189 states and 341 transitions. [2018-07-23 16:16:18,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2018-07-23 16:16:18,188 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:16:18,188 INFO L353 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 6, 6, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:16:18,189 INFO L414 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:16:18,189 INFO L82 PathProgramCache]: Analyzing trace with hash -1420619136, now seen corresponding path program 1 times [2018-07-23 16:16:18,189 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:16:21,394 WARN L169 SmtUtils]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 47 [2018-07-23 16:16:21,646 WARN L169 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:16:23,180 WARN L169 SmtUtils]: Spent 140.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-07-23 16:16:24,704 WARN L169 SmtUtils]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 51 [2018-07-23 16:16:27,745 WARN L169 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 60 [2018-07-23 16:16:28,783 WARN L169 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 44 [2018-07-23 16:16:29,201 WARN L169 SmtUtils]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:16:29,602 WARN L169 SmtUtils]: Spent 201.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-07-23 16:16:33,721 WARN L169 SmtUtils]: Spent 241.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2018-07-23 16:16:39,756 WARN L169 SmtUtils]: Spent 196.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-07-23 16:16:46,142 WARN L169 SmtUtils]: Spent 249.00 ms on a formula simplification that was a NOOP. DAG size: 70 [2018-07-23 16:16:49,077 WARN L169 SmtUtils]: Spent 177.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2018-07-23 16:16:49,677 WARN L169 SmtUtils]: Spent 319.00 ms on a formula simplification that was a NOOP. DAG size: 73 [2018-07-23 16:16:55,745 WARN L169 SmtUtils]: Spent 356.00 ms on a formula simplification that was a NOOP. DAG size: 80 [2018-07-23 16:17:13,034 WARN L169 SmtUtils]: Spent 325.00 ms on a formula simplification that was a NOOP. DAG size: 73 [2018-07-23 16:17:22,206 WARN L169 SmtUtils]: Spent 362.00 ms on a formula simplification that was a NOOP. DAG size: 80 [2018-07-23 16:17:27,385 WARN L169 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 50 [2018-07-23 16:17:28,265 WARN L169 SmtUtils]: Spent 461.00 ms on a formula simplification that was a NOOP. DAG size: 83 [2018-07-23 16:18:09,915 WARN L169 SmtUtils]: Spent 416.00 ms on a formula simplification that was a NOOP. DAG size: 83 [2018-07-23 16:18:24,200 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-23 16:18:24,200 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-07-23 16:18:24,201 INFO L450 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-07-23 16:18:24,201 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-07-23 16:18:24,202 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=623, Invalid=1633, Unknown=0, NotChecked=0, Total=2256 [2018-07-23 16:18:24,202 INFO L87 Difference]: Start difference. First operand 189 states and 341 transitions. Second operand 9 states. [2018-07-23 16:18:24,851 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-23 16:18:24,851 INFO L93 Difference]: Finished difference Result 305 states and 549 transitions. [2018-07-23 16:18:24,852 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-07-23 16:18:24,852 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 85 [2018-07-23 16:18:24,852 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-23 16:18:24,855 INFO L225 Difference]: With dead ends: 305 [2018-07-23 16:18:24,855 INFO L226 Difference]: Without dead ends: 303 [2018-07-23 16:18:24,857 INFO L573 BasicCegarLoop]: 0 DeclaredPredicates, 125506 GetRequests, 125379 SyntacticMatches, 81 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2762 ImplicationChecksByTransitivity, 11.2s TimeCoverageRelationStatistics Valid=623, Invalid=1633, Unknown=0, NotChecked=0, Total=2256 [2018-07-23 16:18:24,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2018-07-23 16:18:24,897 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 145. [2018-07-23 16:18:24,898 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 145 states. [2018-07-23 16:18:24,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 261 transitions. [2018-07-23 16:18:24,898 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 261 transitions. Word has length 85 [2018-07-23 16:18:24,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-23 16:18:24,899 INFO L471 AbstractCegarLoop]: Abstraction has 145 states and 261 transitions. [2018-07-23 16:18:24,899 INFO L472 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-07-23 16:18:24,899 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 261 transitions. [2018-07-23 16:18:24,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2018-07-23 16:18:24,900 INFO L345 BasicCegarLoop]: Found error trace [2018-07-23 16:18:24,900 INFO L353 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-07-23 16:18:24,900 INFO L414 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0AssertViolationASSERT]=== [2018-07-23 16:18:24,900 INFO L82 PathProgramCache]: Analyzing trace with hash 1115038680, now seen corresponding path program 1 times [2018-07-23 16:18:24,900 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-23 16:18:29,635 WARN L169 SmtUtils]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 47 [2018-07-23 16:18:30,469 WARN L169 SmtUtils]: Spent 140.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:18:37,698 WARN L169 SmtUtils]: Spent 144.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-07-23 16:18:39,268 WARN L169 SmtUtils]: Spent 191.00 ms on a formula simplification that was a NOOP. DAG size: 61 Received shutdown request... [2018-07-23 16:18:45,437 WARN L540 AbstractCegarLoop]: Verification canceled [2018-07-23 16:18:45,443 WARN L202 ceAbstractionStarter]: Timeout [2018-07-23 16:18:45,443 INFO L202 PluginConnector]: Adding new model s3_srvr_1.cil.c_23.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.07 04:18:45 BoogieIcfgContainer [2018-07-23 16:18:45,443 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-07-23 16:18:45,446 INFO L168 Benchmark]: Toolchain (without parser) took 282800.79 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -96.5 MB). Free memory was 1.5 GB in the beginning and 889.5 MB in the end (delta: 587.8 MB). Peak memory consumption was 491.4 MB. Max. memory is 7.1 GB. [2018-07-23 16:18:45,447 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.20 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-07-23 16:18:45,448 INFO L168 Benchmark]: Boogie Preprocessor took 77.88 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-07-23 16:18:45,448 INFO L168 Benchmark]: RCFGBuilder took 832.83 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 31.7 MB). Peak memory consumption was 31.7 MB. Max. memory is 7.1 GB. [2018-07-23 16:18:45,449 INFO L168 Benchmark]: TraceAbstraction took 281883.93 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -96.5 MB). Free memory was 1.4 GB in the beginning and 889.5 MB in the end (delta: 556.1 MB). Peak memory consumption was 459.7 MB. Max. memory is 7.1 GB. [2018-07-23 16:18:45,452 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.20 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 77.88 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 832.83 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 31.7 MB). Peak memory consumption was 31.7 MB. Max. memory is 7.1 GB. * TraceAbstraction took 281883.93 ms. Allocated memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: -96.5 MB). Free memory was 1.4 GB in the beginning and 889.5 MB in the end (delta: 556.1 MB). Peak memory consumption was 459.7 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 516]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 516). Cancelled while BasicCegarLoop was analyzing trace of length 87 with TraceHistMax 7, while Pdr was Timeout or canceled while running Pdr. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 25 locations, 1 error locations. TIMEOUT Result, 281.8s OverallTime, 11 OverallIterations, 7 TraceHistogramMax, 4.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 250 SDtfs, 807 SDslu, 45 SDs, 0 SdLazy, 927 SolverSat, 518 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 3.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 366176 GetRequests, 365555 SyntacticMatches, 413 SemanticMatches, 208 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7470 ImplicationChecksByTransitivity, 34.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=189occurred in iteration=9, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 10 MinimizatonAttempts, 428 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 256.0s PdrRuntime, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/s3_srvr_1.cil.c_23.bpl_AutomizerBpl-pdr.epf_AutomizerBpl.xml/Csv-Benchmark-0-2018-07-23_16-18-45-465.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/s3_srvr_1.cil.c_23.bpl_AutomizerBpl-pdr.epf_AutomizerBpl.xml/Csv-TraceAbstractionBenchmarks-0-2018-07-23_16-18-45-465.csv Completed graceful shutdown