java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Taipan+AI_EQ_precise.epf -i ../../../trunk/examples/svcomp/memsafety/960521-1_true-valid-memsafety.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-2f49842 [2018-01-21 05:41:13,060 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-21 05:41:13,061 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-21 05:41:13,077 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-21 05:41:13,077 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-21 05:41:13,078 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-21 05:41:13,079 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-21 05:41:13,081 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-21 05:41:13,083 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-21 05:41:13,084 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-21 05:41:13,085 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-21 05:41:13,085 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-21 05:41:13,086 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-21 05:41:13,087 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-21 05:41:13,088 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-21 05:41:13,091 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-21 05:41:13,093 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-21 05:41:13,095 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-21 05:41:13,096 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-21 05:41:13,098 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-21 05:41:13,100 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-21 05:41:13,100 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-21 05:41:13,101 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-21 05:41:13,102 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-21 05:41:13,102 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-21 05:41:13,104 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-21 05:41:13,104 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-21 05:41:13,105 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-21 05:41:13,105 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-21 05:41:13,105 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-21 05:41:13,106 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-21 05:41:13,106 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/mempurity-32bit-Automizer_Taipan+AI_EQ_precise.epf [2018-01-21 05:41:13,114 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-21 05:41:13,115 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-21 05:41:13,115 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-21 05:41:13,116 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-21 05:41:13,116 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-21 05:41:13,116 INFO L133 SettingsManager]: * Weq Fattening=true [2018-01-21 05:41:13,116 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-21 05:41:13,116 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-21 05:41:13,116 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * Check allocation purity=true [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-01-21 05:41:13,117 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-21 05:41:13,118 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-01-21 05:41:13,118 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-21 05:41:13,118 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-01-21 05:41:13,118 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-01-21 05:41:13,118 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-21 05:41:13,118 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-01-21 05:41:13,119 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-21 05:41:13,119 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-21 05:41:13,119 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-21 05:41:13,119 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-21 05:41:13,119 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-21 05:41:13,119 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * Stop after first violation was found=false [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-21 05:41:13,120 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-01-21 05:41:13,121 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-21 05:41:13,121 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-21 05:41:13,154 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-21 05:41:13,164 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-21 05:41:13,167 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-21 05:41:13,168 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-21 05:41:13,169 INFO L276 PluginConnector]: CDTParser initialized [2018-01-21 05:41:13,169 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/memsafety/960521-1_true-valid-memsafety.i [2018-01-21 05:41:13,348 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-21 05:41:13,353 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-21 05:41:13,354 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-21 05:41:13,354 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-21 05:41:13,359 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-21 05:41:13,360 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,363 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6bfb951b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13, skipping insertion in model container [2018-01-21 05:41:13,363 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,378 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-21 05:41:13,415 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-21 05:41:13,533 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-21 05:41:13,551 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-21 05:41:13,559 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13 WrapperNode [2018-01-21 05:41:13,559 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-21 05:41:13,560 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-21 05:41:13,560 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-21 05:41:13,560 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-21 05:41:13,570 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,571 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,579 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,579 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,584 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,587 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,588 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... [2018-01-21 05:41:13,590 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-21 05:41:13,590 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-21 05:41:13,590 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-21 05:41:13,590 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-21 05:41:13,591 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-21 05:41:13,641 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-21 05:41:13,642 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-21 05:41:13,642 INFO L136 BoogieDeclarations]: Found implementation of procedure foo [2018-01-21 05:41:13,642 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-21 05:41:13,642 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-21 05:41:13,642 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-21 05:41:13,643 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-21 05:41:13,643 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-21 05:41:13,643 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-21 05:41:13,643 INFO L128 BoogieDeclarations]: Found specification of procedure malloc [2018-01-21 05:41:13,643 INFO L128 BoogieDeclarations]: Found specification of procedure free [2018-01-21 05:41:13,643 INFO L128 BoogieDeclarations]: Found specification of procedure foo [2018-01-21 05:41:13,643 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-21 05:41:13,644 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-21 05:41:13,644 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-21 05:41:13,814 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-21 05:41:13,814 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.01 05:41:13 BoogieIcfgContainer [2018-01-21 05:41:13,814 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-21 05:41:13,815 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-21 05:41:13,816 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-21 05:41:13,817 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-21 05:41:13,818 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.01 05:41:13" (1/3) ... [2018-01-21 05:41:13,818 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@121d5a95 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.01 05:41:13, skipping insertion in model container [2018-01-21 05:41:13,819 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.01 05:41:13" (2/3) ... [2018-01-21 05:41:13,819 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@121d5a95 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.01 05:41:13, skipping insertion in model container [2018-01-21 05:41:13,819 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.01 05:41:13" (3/3) ... [2018-01-21 05:41:13,820 INFO L105 eAbstractionObserver]: Analyzing ICFG 960521-1_true-valid-memsafety.i [2018-01-21 05:41:13,827 INFO L130 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-21 05:41:13,832 INFO L142 ceAbstractionStarter]: Appying trace abstraction to program that has 4 error locations. [2018-01-21 05:41:13,882 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 05:41:13,883 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 05:41:13,883 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 05:41:13,883 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 05:41:13,883 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 05:41:13,883 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 05:41:13,884 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 05:41:13,884 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.initErr0EnsuresViolation======== [2018-01-21 05:41:13,885 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 05:41:13,905 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states. [2018-01-21 05:41:13,911 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-01-21 05:41:13,911 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 05:41:13,912 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-01-21 05:41:13,912 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.initErr0EnsuresViolation]=== [2018-01-21 05:41:13,917 INFO L82 PathProgramCache]: Analyzing trace with hash 90336, now seen corresponding path program 1 times [2018-01-21 05:41:13,920 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 05:41:13,967 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:13,967 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:41:13,967 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:13,967 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 05:41:14,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 05:41:14,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2018-01-21 05:41:14,040 INFO L381 BasicCegarLoop]: Counterexample might be feasible [2018-01-21 05:41:14,048 WARN L343 cessorBacktranslator]: Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) [2018-01-21 05:41:14,057 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 05:41:14,057 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 05:41:14,058 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 05:41:14,058 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 05:41:14,058 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 05:41:14,058 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 05:41:14,058 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 05:41:14,058 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == fooErr0EnsuresViolation======== [2018-01-21 05:41:14,058 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 05:41:14,060 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states. [2018-01-21 05:41:14,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-01-21 05:41:14,061 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 05:41:14,061 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 05:41:14,061 INFO L371 AbstractCegarLoop]: === Iteration 1 === [fooErr0EnsuresViolation]=== [2018-01-21 05:41:14,062 INFO L82 PathProgramCache]: Analyzing trace with hash 935443697, now seen corresponding path program 1 times [2018-01-21 05:41:14,062 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 05:41:14,063 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,063 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:41:14,063 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,063 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 05:41:14,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 05:41:14,099 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 05:41:14,142 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 05:41:14,144 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 05:41:14,145 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-21 05:41:14,145 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 05:41:14,147 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-21 05:41:14,162 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-21 05:41:14,163 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 05:41:14,166 INFO L87 Difference]: Start difference. First operand 40 states. Second operand 2 states. [2018-01-21 05:41:14,192 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 05:41:14,192 INFO L93 Difference]: Finished difference Result 60 states and 67 transitions. [2018-01-21 05:41:14,192 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-21 05:41:14,260 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 18 [2018-01-21 05:41:14,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 05:41:14,268 INFO L225 Difference]: With dead ends: 60 [2018-01-21 05:41:14,269 INFO L226 Difference]: Without dead ends: 0 [2018-01-21 05:41:14,272 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 05:41:14,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2018-01-21 05:41:14,290 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2018-01-21 05:41:14,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 0 states. [2018-01-21 05:41:14,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2018-01-21 05:41:14,292 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 18 [2018-01-21 05:41:14,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 05:41:14,292 INFO L432 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2018-01-21 05:41:14,292 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-21 05:41:14,293 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2018-01-21 05:41:14,293 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2018-01-21 05:41:14,295 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 05:41:14,296 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 05:41:14,296 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 05:41:14,296 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 05:41:14,296 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 05:41:14,296 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 05:41:14,296 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 05:41:14,296 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == ULTIMATE.startErr0EnsuresViolation======== [2018-01-21 05:41:14,296 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 05:41:14,298 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states. [2018-01-21 05:41:14,300 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2018-01-21 05:41:14,300 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 05:41:14,300 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 05:41:14,300 INFO L371 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 05:41:14,300 INFO L82 PathProgramCache]: Analyzing trace with hash 1172106943, now seen corresponding path program 1 times [2018-01-21 05:41:14,300 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 05:41:14,302 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,302 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:41:14,302 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,302 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 05:41:14,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 05:41:14,322 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 05:41:14,348 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 05:41:14,348 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 05:41:14,348 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-21 05:41:14,348 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 05:41:14,349 INFO L409 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-01-21 05:41:14,349 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-01-21 05:41:14,349 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 05:41:14,349 INFO L87 Difference]: Start difference. First operand 40 states. Second operand 2 states. [2018-01-21 05:41:14,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 05:41:14,354 INFO L93 Difference]: Finished difference Result 60 states and 67 transitions. [2018-01-21 05:41:14,355 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-01-21 05:41:14,355 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 27 [2018-01-21 05:41:14,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 05:41:14,359 INFO L225 Difference]: With dead ends: 60 [2018-01-21 05:41:14,359 INFO L226 Difference]: Without dead ends: 36 [2018-01-21 05:41:14,359 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-01-21 05:41:14,360 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2018-01-21 05:41:14,369 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2018-01-21 05:41:14,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-01-21 05:41:14,370 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 38 transitions. [2018-01-21 05:41:14,371 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 38 transitions. Word has length 27 [2018-01-21 05:41:14,371 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 05:41:14,371 INFO L432 AbstractCegarLoop]: Abstraction has 36 states and 38 transitions. [2018-01-21 05:41:14,371 INFO L433 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-01-21 05:41:14,371 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 38 transitions. [2018-01-21 05:41:14,372 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-01-21 05:41:14,372 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 05:41:14,373 INFO L322 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 05:41:14,373 INFO L371 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 05:41:14,373 INFO L82 PathProgramCache]: Analyzing trace with hash -862637837, now seen corresponding path program 1 times [2018-01-21 05:41:14,373 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 05:41:14,374 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,374 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:41:14,375 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,375 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 05:41:14,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 05:41:14,396 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 05:41:14,456 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-21 05:41:14,456 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 05:41:14,456 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-21 05:41:14,456 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 05:41:14,458 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-21 05:41:14,458 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-21 05:41:14,458 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-21 05:41:14,459 INFO L87 Difference]: Start difference. First operand 36 states and 38 transitions. Second operand 3 states. [2018-01-21 05:41:14,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 05:41:14,503 INFO L93 Difference]: Finished difference Result 58 states and 62 transitions. [2018-01-21 05:41:14,503 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-21 05:41:14,504 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 29 [2018-01-21 05:41:14,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 05:41:14,505 INFO L225 Difference]: With dead ends: 58 [2018-01-21 05:41:14,505 INFO L226 Difference]: Without dead ends: 45 [2018-01-21 05:41:14,507 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-21 05:41:14,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-01-21 05:41:14,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 38. [2018-01-21 05:41:14,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 38 states. [2018-01-21 05:41:14,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 40 transitions. [2018-01-21 05:41:14,513 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 40 transitions. Word has length 29 [2018-01-21 05:41:14,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 05:41:14,513 INFO L432 AbstractCegarLoop]: Abstraction has 38 states and 40 transitions. [2018-01-21 05:41:14,513 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-21 05:41:14,514 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 40 transitions. [2018-01-21 05:41:14,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-01-21 05:41:14,515 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 05:41:14,515 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 05:41:14,515 INFO L371 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 05:41:14,515 INFO L82 PathProgramCache]: Analyzing trace with hash -1162981958, now seen corresponding path program 1 times [2018-01-21 05:41:14,516 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 05:41:14,517 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,517 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:41:14,517 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,517 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 05:41:14,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 05:41:14,534 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 05:41:14,596 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-21 05:41:14,597 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 05:41:14,597 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-21 05:41:14,597 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 05:41:14,597 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-21 05:41:14,598 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-21 05:41:14,598 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-01-21 05:41:14,598 INFO L87 Difference]: Start difference. First operand 38 states and 40 transitions. Second operand 5 states. [2018-01-21 05:41:14,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 05:41:14,649 INFO L93 Difference]: Finished difference Result 43 states and 44 transitions. [2018-01-21 05:41:14,650 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-21 05:41:14,650 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 33 [2018-01-21 05:41:14,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 05:41:14,651 INFO L225 Difference]: With dead ends: 43 [2018-01-21 05:41:14,651 INFO L226 Difference]: Without dead ends: 36 [2018-01-21 05:41:14,652 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-01-21 05:41:14,652 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2018-01-21 05:41:14,656 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 36. [2018-01-21 05:41:14,656 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-01-21 05:41:14,657 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 37 transitions. [2018-01-21 05:41:14,657 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 37 transitions. Word has length 33 [2018-01-21 05:41:14,658 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 05:41:14,658 INFO L432 AbstractCegarLoop]: Abstraction has 36 states and 37 transitions. [2018-01-21 05:41:14,658 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-21 05:41:14,658 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 37 transitions. [2018-01-21 05:41:14,659 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-01-21 05:41:14,659 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 05:41:14,659 INFO L322 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 05:41:14,659 INFO L371 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 05:41:14,659 INFO L82 PathProgramCache]: Analyzing trace with hash -1789723842, now seen corresponding path program 1 times [2018-01-21 05:41:14,660 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 05:41:14,661 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,661 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:41:14,661 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,661 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 05:41:14,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 05:41:14,676 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 05:41:14,736 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-21 05:41:14,736 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-21 05:41:14,736 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-21 05:41:14,736 INFO L252 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-01-21 05:41:14,737 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-21 05:41:14,737 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-21 05:41:14,737 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-01-21 05:41:14,738 INFO L87 Difference]: Start difference. First operand 36 states and 37 transitions. Second operand 5 states. [2018-01-21 05:41:14,799 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-21 05:41:14,799 INFO L93 Difference]: Finished difference Result 60 states and 62 transitions. [2018-01-21 05:41:14,799 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-01-21 05:41:14,799 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 33 [2018-01-21 05:41:14,800 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-21 05:41:14,800 INFO L225 Difference]: With dead ends: 60 [2018-01-21 05:41:14,801 INFO L226 Difference]: Without dead ends: 42 [2018-01-21 05:41:14,801 INFO L525 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-01-21 05:41:14,801 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2018-01-21 05:41:14,806 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 38. [2018-01-21 05:41:14,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 38 states. [2018-01-21 05:41:14,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 39 transitions. [2018-01-21 05:41:14,807 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 39 transitions. Word has length 33 [2018-01-21 05:41:14,807 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-21 05:41:14,808 INFO L432 AbstractCegarLoop]: Abstraction has 38 states and 39 transitions. [2018-01-21 05:41:14,808 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-21 05:41:14,808 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 39 transitions. [2018-01-21 05:41:14,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-01-21 05:41:14,809 INFO L314 BasicCegarLoop]: Found error trace [2018-01-21 05:41:14,809 INFO L322 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-21 05:41:14,809 INFO L371 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0EnsuresViolation]=== [2018-01-21 05:41:14,809 INFO L82 PathProgramCache]: Analyzing trace with hash -1424676713, now seen corresponding path program 1 times [2018-01-21 05:41:14,810 INFO L67 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-01-21 05:41:14,811 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,811 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:41:14,811 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-21 05:41:14,811 INFO L280 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-01-21 05:41:14,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 05:41:14,827 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-21 05:41:14,874 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-21 05:41:14,874 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 05:41:14,874 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-01-21 05:41:14,875 INFO L199 CegarAbsIntRunner]: Running AI on error trace of length 38 with the following transitions: [2018-01-21 05:41:14,877 INFO L201 CegarAbsIntRunner]: [0], [1], [3], [7], [10], [12], [13], [15], [19], [23], [26], [28], [29], [31], [35], [40], [41], [42], [43], [44], [45], [46], [47], [49], [56], [57], [58], [60], [61], [63], [64], [65], [66], [67], [68] [2018-01-21 05:41:14,924 INFO L147 AbstractInterpreter]: Using domain VPDomain [2018-01-21 05:41:14,925 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=2) Received shutdown request... [2018-01-21 05:42:17,354 WARN L571 FixpointEngine]: Received timeout, aborting fixpoint engine [2018-01-21 05:42:17,355 WARN L157 AbstractInterpreter]: Abstract interpretation run out of time [2018-01-21 05:42:17,356 INFO L434 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-01-21 05:42:17,356 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-21 05:42:17,357 INFO L187 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-21 05:42:17,366 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-21 05:42:17,367 INFO L280 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-01-21 05:42:17,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-21 05:42:17,409 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-21 05:42:17,416 INFO L175 TraceCheckSpWp]: Timeout while computing interpolants [2018-01-21 05:42:17,416 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-21 05:42:17,419 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-21 05:42:17,419 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-21 05:42:17,419 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-21 05:42:17,419 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-21 05:42:17,419 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-21 05:42:17,419 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-21 05:42:17,419 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-21 05:42:17,420 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == mainErr0EnsuresViolation======== [2018-01-21 05:42:17,420 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-21 05:42:17,422 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states. [2018-01-21 05:42:17,422 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-21 05:42:17,423 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.01 05:42:17 BoogieIcfgContainer [2018-01-21 05:42:17,423 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-21 05:42:17,424 INFO L168 Benchmark]: Toolchain (without parser) took 64075.19 ms. Allocated memory was 306.7 MB in the beginning and 1.7 GB in the end (delta: 1.3 GB). Free memory was 264.9 MB in the beginning and 637.5 MB in the end (delta: -372.6 MB). Peak memory consumption was 975.8 MB. Max. memory is 5.3 GB. [2018-01-21 05:42:17,425 INFO L168 Benchmark]: CDTParser took 0.11 ms. Allocated memory is still 306.7 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-21 05:42:17,426 INFO L168 Benchmark]: CACSL2BoogieTranslator took 206.04 ms. Allocated memory is still 306.7 MB. Free memory was 263.9 MB in the beginning and 253.8 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. [2018-01-21 05:42:17,426 INFO L168 Benchmark]: Boogie Preprocessor took 29.87 ms. Allocated memory is still 306.7 MB. Free memory was 253.8 MB in the beginning and 251.8 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 5.3 GB. [2018-01-21 05:42:17,426 INFO L168 Benchmark]: RCFGBuilder took 224.37 ms. Allocated memory is still 306.7 MB. Free memory was 251.8 MB in the beginning and 235.8 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 5.3 GB. [2018-01-21 05:42:17,427 INFO L168 Benchmark]: TraceAbstraction took 63607.82 ms. Allocated memory was 306.7 MB in the beginning and 1.7 GB in the end (delta: 1.3 GB). Free memory was 235.8 MB in the beginning and 637.5 MB in the end (delta: -401.7 MB). Peak memory consumption was 946.8 MB. Max. memory is 5.3 GB. [2018-01-21 05:42:17,428 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.11 ms. Allocated memory is still 306.7 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 206.04 ms. Allocated memory is still 306.7 MB. Free memory was 263.9 MB in the beginning and 253.8 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 29.87 ms. Allocated memory is still 306.7 MB. Free memory was 253.8 MB in the beginning and 251.8 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 5.3 GB. * RCFGBuilder took 224.37 ms. Allocated memory is still 306.7 MB. Free memory was 251.8 MB in the beginning and 235.8 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 5.3 GB. * TraceAbstraction took 63607.82 ms. Allocated memory was 306.7 MB in the beginning and 1.7 GB in the end (delta: 1.3 GB). Free memory was 235.8 MB in the beginning and 637.5 MB in the end (delta: -401.7 MB). Peak memory consumption was 946.8 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Generated EnsuresSpecification ensures #valid == old(#valid); is not ensure(true) * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - CounterExampleResult [Line: 1]: not all allocated memory was freed not all allocated memory was freed We found a FailurePath: [L619] int *a, *b; [L620] int n; VAL [\old(a)=4, \old(a)=7, \old(b)=2, \old(b)=3, \old(n)=5, a={0:0}, b={0:0}, n=0] - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.initErr0EnsuresViolation CFG has 4 procedures, 40 locations, 4 error locations. UNSAFE Result, 0.1s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=40occurred in iteration=0, 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, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 3 NumberOfCodeBlocks, 3 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 0 ConstructedInterpolants, 0 QuantifiedInterpolants, 0 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 0 InterpolantComputations, 0 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - PositiveResult [Line: 621]: all allocated memory was freed For all program executions holds that all allocated memory was freed at this location - StatisticsResult: Ultimate Automizer benchmark data for error location: fooErr0EnsuresViolation CFG has 4 procedures, 40 locations, 4 error locations. SAFE Result, 0.2s OverallTime, 1 OverallIterations, 1 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 41 SDtfs, 0 SDslu, 0 SDs, 0 SdLazy, 0 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=40occurred in iteration=0, 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, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 1 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.0s InterpolantComputationTime, 18 NumberOfCodeBlocks, 18 NumberOfCodeBlocksAsserted, 1 NumberOfCheckSat, 17 ConstructedInterpolants, 0 QuantifiedInterpolants, 289 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 1 InterpolantComputations, 1 PerfectInterpolantSequences, 0/0 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 1). Cancelled while BasicCegarLoop was analyzing trace of length 38 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 6 known predicates. - StatisticsResult: Ultimate Automizer benchmark data for error location: ULTIMATE.startErr0EnsuresViolation CFG has 4 procedures, 40 locations, 4 error locations. TIMEOUT Result, 63.1s OverallTime, 5 OverallIterations, 2 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 129 SDtfs, 74 SDslu, 129 SDs, 0 SdLazy, 66 SolverSat, 10 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=40occurred in iteration=0, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 62.4s AbstIntTime, 1 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 4 MinimizatonAttempts, 11 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.0s SatisfiabilityAnalysisTime, 0.2s InterpolantComputationTime, 122 NumberOfCodeBlocks, 122 NumberOfCodeBlocksAsserted, 4 NumberOfCheckSat, 118 ConstructedInterpolants, 0 QuantifiedInterpolants, 5476 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 4 InterpolantComputations, 4 PerfectInterpolantSequences, 4/4 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, REUSE_STATISTICS: No data available - TimeoutResultAtElement [Line: 629]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 629). Cancelled while IsEmpty was searching accepting run (input had 40 states). - StatisticsResult: Ultimate Automizer benchmark data for error location: mainErr0EnsuresViolation CFG has 4 procedures, 40 locations, 4 error locations. TIMEOUT Result, 0.0s OverallTime, 0 OverallIterations, 0 TraceHistogramMax, 0.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: No data available, PredicateUnifierStatistics: No data available, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=40occurred in iteration=0, 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, AutomataMinimizationStatistics: No data available, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: No data available, REUSE_STATISTICS: No data available RESULT: Ultimate proved your program to be incorrect! Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/960521-1_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_precise.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-21_05-42-17-437.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/960521-1_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_precise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-21_05-42-17-437.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/960521-1_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_precise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-1-2018-01-21_05-42-17-437.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/960521-1_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_precise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-2-2018-01-21_05-42-17-437.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/960521-1_true-valid-memsafety.i_mempurity-32bit-Automizer_Taipan+AI_EQ_precise.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-3-2018-01-21_05-42-17-437.csv Completed graceful shutdown