java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_glob3_iny.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:23:12,293 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:23:12,295 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:23:12,313 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:23:12,313 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:23:12,314 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:23:12,315 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:23:12,316 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:23:12,318 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:23:12,318 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:23:12,319 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:23:12,319 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:23:12,320 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:23:12,323 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:23:12,324 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:23:12,324 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:23:12,326 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:23:12,337 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:23:12,339 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:23:12,340 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:23:12,341 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:23:12,347 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:23:12,347 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:23:12,347 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:23:12,348 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:23:12,349 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:23:12,349 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:23:12,350 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:23:12,351 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:23:12,351 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:23:12,352 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:23:12,352 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:23:12,353 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:23:12,353 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:23:12,354 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:23:12,354 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 13:23:12,381 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:23:12,382 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:23:12,382 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:23:12,382 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:23:12,383 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:23:12,383 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:23:12,383 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:23:12,388 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:23:12,388 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:23:12,388 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:23:12,389 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:23:12,389 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:23:12,389 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:23:12,389 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:23:12,389 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:23:12,390 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:23:12,390 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:23:12,390 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:23:12,390 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:23:12,390 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:23:12,390 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:23:12,393 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:23:12,393 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:23:12,443 INFO ]: Repository-Root is: /tmp [2018-06-25 13:23:12,463 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:23:12,465 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:23:12,466 INFO ]: Initializing SmtParser... [2018-06-25 13:23:12,466 INFO ]: SmtParser initialized [2018-06-25 13:23:12,467 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_glob3_iny.c.smt2 [2018-06-25 13:23:12,468 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/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-06-25 13:23:12,564 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_glob3_iny.c.smt2 unknown [2018-06-25 13:23:13,038 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/NetBSD_glob3_iny.c.smt2 [2018-06-25 13:23:13,043 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:23:13,050 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:23:13,050 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:23:13,050 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:23:13,050 INFO ]: ChcToBoogie initialized [2018-06-25 13:23:13,053 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,119 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13 Unit [2018-06-25 13:23:13,120 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:23:13,120 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:23:13,120 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:23:13,120 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:23:13,142 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,142 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,159 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,159 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,172 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,183 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,186 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... [2018-06-25 13:23:13,190 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:23:13,190 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:23:13,190 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:23:13,190 INFO ]: RCFGBuilder initialized [2018-06-25 13:23:13,200 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (1/1) ... 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 -t:2000 (exit command is (exit), workingDir is null) [2018-06-25 13:23:13,220 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:23:13,220 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:23:13,220 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:23:13,220 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:23:13,220 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:23:13,220 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:23:13,588 INFO ]: Using library mode [2018-06-25 13:23:13,589 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:23:13 BoogieIcfgContainer [2018-06-25 13:23:13,589 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:23:13,590 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:23:13,590 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:23:13,593 INFO ]: TraceAbstraction initialized [2018-06-25 13:23:13,593 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:23:13" (1/3) ... [2018-06-25 13:23:13,594 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1bde9488 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:23:13, skipping insertion in model container [2018-06-25 13:23:13,594 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:23:13" (2/3) ... [2018-06-25 13:23:13,594 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1bde9488 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:23:13, skipping insertion in model container [2018-06-25 13:23:13,594 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:23:13" (3/3) ... [2018-06-25 13:23:13,596 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:23:13,605 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:23:13,615 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:23:13,669 INFO ]: Using default assertion order modulation [2018-06-25 13:23:13,670 INFO ]: Interprodecural is true [2018-06-25 13:23:13,670 INFO ]: Hoare is false [2018-06-25 13:23:13,670 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:23:13,670 INFO ]: Backedges is TWOTRACK [2018-06-25 13:23:13,670 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:23:13,670 INFO ]: Difference is false [2018-06-25 13:23:13,670 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:23:13,670 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:23:13,683 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:23:13,699 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:23:13,699 INFO ]: Found error trace [2018-06-25 13:23:13,703 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:23:13,703 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:23:13,707 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-25 13:23:13,709 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:23:13,709 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:23:13,744 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:13,744 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:23:13,744 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:13,794 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:23:13,954 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:23:13,956 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:23:13,956 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:23:13,957 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:23:13,968 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:23:13,968 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:23:13,971 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:23:14,046 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:23:14,046 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:23:14,047 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:23:14,047 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:23:14,048 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:23:14,058 INFO ]: With dead ends: 9 [2018-06-25 13:23:14,058 INFO ]: Without dead ends: 9 [2018-06-25 13:23:14,060 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:23:14,079 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:23:14,093 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:23:14,095 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:23:14,095 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:23:14,096 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:23:14,096 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:23:14,096 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:23:14,096 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:23:14,097 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:23:14,097 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:23:14,097 INFO ]: Found error trace [2018-06-25 13:23:14,097 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:23:14,097 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:23:14,097 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-25 13:23:14,097 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:23:14,097 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:23:14,098 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:14,098 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:23:14,098 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:14,182 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:23:14,393 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:23:14,394 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:23:14,394 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:23:14,435 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:23:14,512 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:23:14,524 INFO ]: Computing forward predicates... [2018-06-25 13:23:15,273 WARN ]: Spent 342.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 4 [2018-06-25 13:23:16,372 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:23:16,409 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:23:16,409 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:23:16,409 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:23:16,410 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:23:16,410 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:23:16,410 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:23:16,699 WARN ]: Spent 240.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-25 13:23:16,772 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:23:16,772 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 13:23:16,772 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 13:23:16,772 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:23:16,772 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:23:16,773 INFO ]: With dead ends: 10 [2018-06-25 13:23:16,773 INFO ]: Without dead ends: 10 [2018-06-25 13:23:16,773 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:23:16,773 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 13:23:16,774 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 13:23:16,774 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 13:23:16,775 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 13:23:16,775 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 13:23:16,775 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:23:16,775 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 13:23:16,775 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:23:16,775 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 13:23:16,775 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 13:23:16,775 INFO ]: Found error trace [2018-06-25 13:23:16,775 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:23:16,775 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:23:16,776 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-25 13:23:16,776 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:23:16,776 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:23:16,776 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:16,776 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:23:16,776 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:16,865 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:23:17,131 WARN ]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-25 13:23:17,181 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:23:17,181 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:23:17,181 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:23:17,195 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:23:17,297 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:23:17,297 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:23:17,301 INFO ]: Computing forward predicates... [2018-06-25 13:23:17,858 WARN ]: Spent 142.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 14 [2018-06-25 13:23:17,998 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:23:21,150 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:23:31,014 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:23:31,041 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:23:31,041 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 13:23:31,041 INFO ]: Interpolant automaton has 6 states [2018-06-25 13:23:31,041 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 13:23:31,041 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:23:31,041 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 13:23:31,110 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:23:31,111 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:23:31,114 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:23:31,114 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 13:23:31,114 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:23:31,114 INFO ]: With dead ends: 11 [2018-06-25 13:23:31,114 INFO ]: Without dead ends: 11 [2018-06-25 13:23:31,114 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-25 13:23:31,115 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:23:31,115 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:23:31,115 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:23:31,115 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:23:31,116 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 13:23:31,116 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:23:31,116 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:23:31,116 INFO ]: Interpolant automaton has 6 states. [2018-06-25 13:23:31,116 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:23:31,116 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:23:31,116 INFO ]: Found error trace [2018-06-25 13:23:31,116 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:23:31,116 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:23:31,116 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-25 13:23:31,116 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:23:31,116 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:23:31,117 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:31,117 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:23:31,117 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:23:31,209 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:23:31,976 WARN ]: Spent 495.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-25 13:23:32,220 WARN ]: Spent 185.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-25 13:23:32,234 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:23:32,234 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:23:32,234 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:23:32,244 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:23:32,338 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 13:23:32,338 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:23:32,343 INFO ]: Computing forward predicates... [2018-06-25 13:23:33,568 WARN ]: Spent 726.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 15 [2018-06-25 13:23:39,448 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:23:39,754 WARN ]: expecting exponential blowup for input size 7 [2018-06-25 13:23:39,953 WARN ]: expecting exponential blowup for input size 7 Received shutdown request... [2018-06-25 13:24:21,525 INFO ]: Timeout while computing interpolants [2018-06-25 13:24:21,725 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:24:21,725 WARN ]: Verification canceled [2018-06-25 13:24:21,729 WARN ]: Timeout [2018-06-25 13:24:21,729 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:24:21 BoogieIcfgContainer [2018-06-25 13:24:21,729 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:24:21,730 INFO ]: Toolchain (without parser) took 68686.11 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 243.7 MB in the beginning and 192.7 MB in the end (delta: 51.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:24:21,730 INFO ]: SmtParser took 0.05 ms. Allocated memory is still 305.1 MB. Free memory is still 270.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:24:21,731 INFO ]: ChcToBoogie took 69.83 ms. Allocated memory is still 305.1 MB. Free memory was 243.7 MB in the beginning and 241.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:24:21,731 INFO ]: Boogie Preprocessor took 69.51 ms. Allocated memory is still 305.1 MB. Free memory was 241.7 MB in the beginning and 238.7 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:24:21,731 INFO ]: RCFGBuilder took 398.73 ms. Allocated memory is still 305.1 MB. Free memory was 238.7 MB in the beginning and 219.7 MB in the end (delta: 19.0 MB). Peak memory consumption was 19.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:24:21,732 INFO ]: TraceAbstraction took 68139.05 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 218.7 MB in the beginning and 192.7 MB in the end (delta: 26.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:24:21,738 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.05 ms. Allocated memory is still 305.1 MB. Free memory is still 270.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 69.83 ms. Allocated memory is still 305.1 MB. Free memory was 243.7 MB in the beginning and 241.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 69.51 ms. Allocated memory is still 305.1 MB. Free memory was 241.7 MB in the beginning and 238.7 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 398.73 ms. Allocated memory is still 305.1 MB. Free memory was 238.7 MB in the beginning and 219.7 MB in the end (delta: 19.0 MB). Peak memory consumption was 19.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 68139.05 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 218.7 MB in the beginning and 192.7 MB in the end (delta: 26.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 11 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 1097 quantified variables from 14 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 68.0s OverallTime, 4 OverallIterations, 3 TraceHistogramMax, 0.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 2 SDslu, 38 SDs, 0 SdLazy, 17 SolverSat, 5 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 30 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 1.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=11occurred in iteration=3, 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.0s AutomataMinimizationTime, 3 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 16.2s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 36 ConstructedInterpolants, 0 QuantifiedInterpolants, 1166 SizeOfPredicates, 12 NumberOfNonLiveVariables, 438 ConjunctsInSsa, 45 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 0/8 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/NetBSD_glob3_iny.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-24-21-748.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/NetBSD_glob3_iny.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-24-21-748.csv Completed graceful shutdown