/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-fb4f59a-m [2022-04-28 11:36:02,153 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-28 11:36:02,154 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-28 11:36:02,179 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-28 11:36:02,179 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-28 11:36:02,180 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-28 11:36:02,183 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-28 11:36:02,187 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-28 11:36:02,188 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-28 11:36:02,189 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-28 11:36:02,189 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-28 11:36:02,190 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-28 11:36:02,190 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-28 11:36:02,191 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-28 11:36:02,191 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-28 11:36:02,192 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-28 11:36:02,192 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-28 11:36:02,193 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-28 11:36:02,193 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-28 11:36:02,194 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-28 11:36:02,195 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-28 11:36:02,196 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-28 11:36:02,196 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-28 11:36:02,197 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-28 11:36:02,197 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-28 11:36:02,199 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-28 11:36:02,199 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-28 11:36:02,199 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-28 11:36:02,200 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-28 11:36:02,200 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-28 11:36:02,200 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-28 11:36:02,200 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-28 11:36:02,201 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-28 11:36:02,201 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-28 11:36:02,202 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-28 11:36:02,202 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-28 11:36:02,202 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-28 11:36:02,203 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-28 11:36:02,203 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-28 11:36:02,203 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-28 11:36:02,203 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-28 11:36:02,204 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-28 11:36:02,205 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-28 11:36:02,210 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-28 11:36:02,211 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-28 11:36:02,211 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-28 11:36:02,212 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-28 11:36:02,212 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 11:36:02,213 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-28 11:36:02,213 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-28 11:36:02,370 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-28 11:36:02,388 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-28 11:36:02,390 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-28 11:36:02,390 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-28 11:36:02,392 INFO L275 PluginConnector]: CDTParser initialized [2022-04-28 11:36:02,393 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound50.c [2022-04-28 11:36:02,454 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4dece357b/554e8d1342ab4897975df96abdb91eab/FLAGad7182f6e [2022-04-28 11:36:02,782 INFO L306 CDTParser]: Found 1 translation units. [2022-04-28 11:36:02,783 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound50.c [2022-04-28 11:36:02,787 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4dece357b/554e8d1342ab4897975df96abdb91eab/FLAGad7182f6e [2022-04-28 11:36:02,795 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4dece357b/554e8d1342ab4897975df96abdb91eab [2022-04-28 11:36:02,797 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-28 11:36:02,798 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-28 11:36:02,799 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-28 11:36:02,799 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-28 11:36:02,805 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-28 11:36:02,806 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 11:36:02" (1/1) ... [2022-04-28 11:36:02,806 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5931ce6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:02, skipping insertion in model container [2022-04-28 11:36:02,806 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.04 11:36:02" (1/1) ... [2022-04-28 11:36:02,823 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-28 11:36:02,837 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-28 11:36:02,967 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound50.c[525,538] [2022-04-28 11:36:03,009 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 11:36:03,019 INFO L203 MainTranslator]: Completed pre-run [2022-04-28 11:36:03,030 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound50.c[525,538] [2022-04-28 11:36:03,054 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-28 11:36:03,071 INFO L208 MainTranslator]: Completed translation [2022-04-28 11:36:03,072 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03 WrapperNode [2022-04-28 11:36:03,072 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-28 11:36:03,073 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-28 11:36:03,073 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-28 11:36:03,073 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-28 11:36:03,080 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,081 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,088 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,088 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,093 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,096 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,097 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,098 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-28 11:36:03,099 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-28 11:36:03,099 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-28 11:36:03,099 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-28 11:36:03,100 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (1/1) ... [2022-04-28 11:36:03,105 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-28 11:36:03,111 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 11:36:03,123 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-28 11:36:03,129 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-28 11:36:03,148 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-28 11:36:03,148 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-28 11:36:03,148 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-28 11:36:03,148 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-28 11:36:03,148 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-28 11:36:03,148 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-28 11:36:03,148 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-28 11:36:03,148 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-28 11:36:03,148 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-28 11:36:03,149 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-28 11:36:03,202 INFO L234 CfgBuilder]: Building ICFG [2022-04-28 11:36:03,203 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-28 11:36:03,375 INFO L275 CfgBuilder]: Performing block encoding [2022-04-28 11:36:03,380 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-28 11:36:03,380 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-28 11:36:03,381 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 11:36:03 BoogieIcfgContainer [2022-04-28 11:36:03,381 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-28 11:36:03,383 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-28 11:36:03,383 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-28 11:36:03,385 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-28 11:36:03,385 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 28.04 11:36:02" (1/3) ... [2022-04-28 11:36:03,385 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a786ab9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 11:36:03, skipping insertion in model container [2022-04-28 11:36:03,386 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.04 11:36:03" (2/3) ... [2022-04-28 11:36:03,386 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a786ab9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.04 11:36:03, skipping insertion in model container [2022-04-28 11:36:03,386 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.04 11:36:03" (3/3) ... [2022-04-28 11:36:03,387 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_valuebound50.c [2022-04-28 11:36:03,396 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-28 11:36:03,396 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-28 11:36:03,424 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-28 11:36:03,429 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@2a1c734c, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@29804db5 [2022-04-28 11:36:03,429 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-28 11:36:03,435 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-28 11:36:03,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-28 11:36:03,440 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 11:36:03,440 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 11:36:03,441 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 11:36:03,444 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 11:36:03,444 INFO L85 PathProgramCache]: Analyzing trace with hash 223850557, now seen corresponding path program 1 times [2022-04-28 11:36:03,449 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 11:36:03,450 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [215328632] [2022-04-28 11:36:03,458 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 11:36:03,458 INFO L85 PathProgramCache]: Analyzing trace with hash 223850557, now seen corresponding path program 2 times [2022-04-28 11:36:03,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 11:36:03,460 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [166931360] [2022-04-28 11:36:03,461 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 11:36:03,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 11:36:03,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:03,582 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 11:36:03,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:03,608 INFO L290 TraceCheckUtils]: 0: Hoare triple {54#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {41#true} is VALID [2022-04-28 11:36:03,608 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-28 11:36:03,609 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-28 11:36:03,609 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-28 11:36:03,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:03,622 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-28 11:36:03,623 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-28 11:36:03,623 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-28 11:36:03,623 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-28 11:36:03,623 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-28 11:36:03,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:03,638 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-28 11:36:03,639 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-28 11:36:03,639 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-28 11:36:03,639 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-28 11:36:03,640 INFO L272 TraceCheckUtils]: 0: Hoare triple {41#true} call ULTIMATE.init(); {54#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-28 11:36:03,640 INFO L290 TraceCheckUtils]: 1: Hoare triple {54#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {41#true} is VALID [2022-04-28 11:36:03,641 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-28 11:36:03,641 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-28 11:36:03,641 INFO L272 TraceCheckUtils]: 4: Hoare triple {41#true} call #t~ret5 := main(); {41#true} is VALID [2022-04-28 11:36:03,641 INFO L290 TraceCheckUtils]: 5: Hoare triple {41#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {41#true} is VALID [2022-04-28 11:36:03,641 INFO L272 TraceCheckUtils]: 6: Hoare triple {41#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 50 then 1 else 0)); {41#true} is VALID [2022-04-28 11:36:03,641 INFO L290 TraceCheckUtils]: 7: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-28 11:36:03,642 INFO L290 TraceCheckUtils]: 8: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-28 11:36:03,642 INFO L290 TraceCheckUtils]: 9: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-28 11:36:03,642 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-28 11:36:03,642 INFO L272 TraceCheckUtils]: 11: Hoare triple {42#false} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {41#true} is VALID [2022-04-28 11:36:03,643 INFO L290 TraceCheckUtils]: 12: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-28 11:36:03,643 INFO L290 TraceCheckUtils]: 13: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-28 11:36:03,643 INFO L290 TraceCheckUtils]: 14: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-28 11:36:03,643 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-28 11:36:03,643 INFO L290 TraceCheckUtils]: 16: Hoare triple {42#false} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {42#false} is VALID [2022-04-28 11:36:03,644 INFO L290 TraceCheckUtils]: 17: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-28 11:36:03,644 INFO L290 TraceCheckUtils]: 18: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-28 11:36:03,644 INFO L272 TraceCheckUtils]: 19: Hoare triple {42#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {42#false} is VALID [2022-04-28 11:36:03,644 INFO L290 TraceCheckUtils]: 20: Hoare triple {42#false} ~cond := #in~cond; {42#false} is VALID [2022-04-28 11:36:03,644 INFO L290 TraceCheckUtils]: 21: Hoare triple {42#false} assume 0 == ~cond; {42#false} is VALID [2022-04-28 11:36:03,644 INFO L290 TraceCheckUtils]: 22: Hoare triple {42#false} assume !false; {42#false} is VALID [2022-04-28 11:36:03,645 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-28 11:36:03,650 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 11:36:03,650 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [166931360] [2022-04-28 11:36:03,651 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [166931360] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:36:03,651 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:36:03,651 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 11:36:03,653 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 11:36:03,653 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [215328632] [2022-04-28 11:36:03,654 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [215328632] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:36:03,654 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:36:03,654 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-28 11:36:03,654 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [308867408] [2022-04-28 11:36:03,654 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 11:36:03,658 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-28 11:36:03,659 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 11:36:03,661 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 11:36:03,687 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 20 edges. 20 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:36:03,688 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-28 11:36:03,688 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 11:36:03,710 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-28 11:36:03,711 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-28 11:36:03,713 INFO L87 Difference]: Start difference. First operand has 38 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 11:36:05,124 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:36:05,124 INFO L93 Difference]: Finished difference Result 69 states and 113 transitions. [2022-04-28 11:36:05,124 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-28 11:36:05,125 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-28 11:36:05,125 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 11:36:05,126 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 11:36:05,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-28 11:36:05,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 11:36:05,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-28 11:36:05,150 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 113 transitions. [2022-04-28 11:36:05,287 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 113 edges. 113 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:36:05,297 INFO L225 Difference]: With dead ends: 69 [2022-04-28 11:36:05,298 INFO L226 Difference]: Without dead ends: 33 [2022-04-28 11:36:05,300 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-28 11:36:05,302 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-04-28 11:36:05,303 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-04-28 11:36:05,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-28 11:36:05,339 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-28 11:36:05,339 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 11:36:05,340 INFO L82 GeneralOperation]: Start isEquivalent. First operand 33 states. Second operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 11:36:05,341 INFO L74 IsIncluded]: Start isIncluded. First operand 33 states. Second operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 11:36:05,341 INFO L87 Difference]: Start difference. First operand 33 states. Second operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 11:36:05,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:36:05,345 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-28 11:36:05,345 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-28 11:36:05,346 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:36:05,346 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:36:05,346 INFO L74 IsIncluded]: Start isIncluded. First operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 33 states. [2022-04-28 11:36:05,347 INFO L87 Difference]: Start difference. First operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 33 states. [2022-04-28 11:36:05,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:36:05,350 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-28 11:36:05,350 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-28 11:36:05,351 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:36:05,351 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:36:05,351 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 11:36:05,351 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 11:36:05,352 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-28 11:36:05,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2022-04-28 11:36:05,355 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 23 [2022-04-28 11:36:05,355 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 11:36:05,356 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2022-04-28 11:36:05,356 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-28 11:36:05,356 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 33 states and 44 transitions. [2022-04-28 11:36:05,414 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:36:05,414 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-28 11:36:05,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-28 11:36:05,416 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 11:36:05,417 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 11:36:05,417 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-28 11:36:05,418 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 11:36:05,419 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 11:36:05,419 INFO L85 PathProgramCache]: Analyzing trace with hash -563604624, now seen corresponding path program 1 times [2022-04-28 11:36:05,419 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 11:36:05,419 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [485339620] [2022-04-28 11:36:05,421 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 11:36:05,421 INFO L85 PathProgramCache]: Analyzing trace with hash -563604624, now seen corresponding path program 2 times [2022-04-28 11:36:05,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 11:36:05,424 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1085360561] [2022-04-28 11:36:05,424 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 11:36:05,425 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 11:36:05,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:05,669 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 11:36:05,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:05,691 INFO L290 TraceCheckUtils]: 0: Hoare triple {344#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {327#true} is VALID [2022-04-28 11:36:05,691 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-28 11:36:05,692 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {327#true} {327#true} #103#return; {327#true} is VALID [2022-04-28 11:36:05,692 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-28 11:36:05,694 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:05,698 INFO L290 TraceCheckUtils]: 0: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-28 11:36:05,699 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-28 11:36:05,699 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-28 11:36:05,700 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #81#return; {327#true} is VALID [2022-04-28 11:36:05,700 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-28 11:36:05,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:36:05,709 INFO L290 TraceCheckUtils]: 0: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-28 11:36:05,710 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-28 11:36:05,711 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-28 11:36:05,711 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #83#return; {327#true} is VALID [2022-04-28 11:36:05,712 INFO L272 TraceCheckUtils]: 0: Hoare triple {327#true} call ULTIMATE.init(); {344#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-28 11:36:05,712 INFO L290 TraceCheckUtils]: 1: Hoare triple {344#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {327#true} is VALID [2022-04-28 11:36:05,712 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-28 11:36:05,715 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #103#return; {327#true} is VALID [2022-04-28 11:36:05,715 INFO L272 TraceCheckUtils]: 4: Hoare triple {327#true} call #t~ret5 := main(); {327#true} is VALID [2022-04-28 11:36:05,716 INFO L290 TraceCheckUtils]: 5: Hoare triple {327#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {327#true} is VALID [2022-04-28 11:36:05,717 INFO L272 TraceCheckUtils]: 6: Hoare triple {327#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 50 then 1 else 0)); {327#true} is VALID [2022-04-28 11:36:05,717 INFO L290 TraceCheckUtils]: 7: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-28 11:36:05,717 INFO L290 TraceCheckUtils]: 8: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-28 11:36:05,718 INFO L290 TraceCheckUtils]: 9: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-28 11:36:05,720 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {327#true} {327#true} #81#return; {327#true} is VALID [2022-04-28 11:36:05,720 INFO L272 TraceCheckUtils]: 11: Hoare triple {327#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {327#true} is VALID [2022-04-28 11:36:05,721 INFO L290 TraceCheckUtils]: 12: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-28 11:36:05,721 INFO L290 TraceCheckUtils]: 13: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-28 11:36:05,721 INFO L290 TraceCheckUtils]: 14: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-28 11:36:05,721 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {327#true} {327#true} #83#return; {327#true} is VALID [2022-04-28 11:36:05,722 INFO L290 TraceCheckUtils]: 16: Hoare triple {327#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-28 11:36:05,723 INFO L290 TraceCheckUtils]: 17: Hoare triple {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !false; {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-28 11:36:05,724 INFO L290 TraceCheckUtils]: 18: Hoare triple {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-28 11:36:05,724 INFO L290 TraceCheckUtils]: 19: Hoare triple {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} assume !false; {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-28 11:36:05,726 INFO L272 TraceCheckUtils]: 20: Hoare triple {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {342#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-28 11:36:05,726 INFO L290 TraceCheckUtils]: 21: Hoare triple {342#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {343#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-28 11:36:05,727 INFO L290 TraceCheckUtils]: 22: Hoare triple {343#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {328#false} is VALID [2022-04-28 11:36:05,727 INFO L290 TraceCheckUtils]: 23: Hoare triple {328#false} assume !false; {328#false} is VALID [2022-04-28 11:36:05,729 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-28 11:36:05,729 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 11:36:05,730 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1085360561] [2022-04-28 11:36:05,730 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1085360561] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:36:05,730 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:36:05,730 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-28 11:36:05,730 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 11:36:05,731 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [485339620] [2022-04-28 11:36:05,731 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [485339620] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:36:05,732 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:36:05,732 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-28 11:36:05,732 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [120428441] [2022-04-28 11:36:05,732 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 11:36:05,734 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2022-04-28 11:36:05,734 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 11:36:05,735 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:36:05,758 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:36:05,759 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-28 11:36:05,759 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 11:36:05,759 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-28 11:36:05,759 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-28 11:36:05,760 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:36:09,636 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:11,638 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:13,640 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:15,642 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:21,764 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 6.09s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:36:27,003 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 5.24s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:36:32,276 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 5.27s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:36:37,539 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 5.26s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:36:39,544 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:41,547 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:43,549 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:45,551 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:49,283 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:36:51,137 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:37:03,220 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.07s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:37:03,675 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:03,676 INFO L93 Difference]: Finished difference Result 68 states and 98 transitions. [2022-04-28 11:37:03,676 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-28 11:37:03,676 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2022-04-28 11:37:03,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 11:37:03,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:03,680 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 98 transitions. [2022-04-28 11:37:03,680 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:03,683 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 98 transitions. [2022-04-28 11:37:03,683 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 98 transitions. [2022-04-28 11:37:03,869 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 98 edges. 98 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:03,871 INFO L225 Difference]: With dead ends: 68 [2022-04-28 11:37:03,871 INFO L226 Difference]: Without dead ends: 48 [2022-04-28 11:37:03,871 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-28 11:37:03,873 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 35 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 193 mSolverCounterSat, 50 mSolverCounterUnsat, 13 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 48.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 54 SdHoareTripleChecker+Invalid, 256 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 193 IncrementalHoareTripleChecker+Invalid, 13 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 48.2s IncrementalHoareTripleChecker+Time [2022-04-28 11:37:03,873 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 54 Invalid, 256 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 193 Invalid, 13 Unknown, 0 Unchecked, 48.2s Time] [2022-04-28 11:37:03,874 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-28 11:37:03,892 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2022-04-28 11:37:03,893 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 11:37:03,893 INFO L82 GeneralOperation]: Start isEquivalent. First operand 48 states. Second operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-28 11:37:03,893 INFO L74 IsIncluded]: Start isIncluded. First operand 48 states. Second operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-28 11:37:03,894 INFO L87 Difference]: Start difference. First operand 48 states. Second operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-28 11:37:03,896 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:03,896 INFO L93 Difference]: Finished difference Result 48 states and 65 transitions. [2022-04-28 11:37:03,897 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 65 transitions. [2022-04-28 11:37:03,897 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:03,897 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:03,898 INFO L74 IsIncluded]: Start isIncluded. First operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 48 states. [2022-04-28 11:37:03,898 INFO L87 Difference]: Start difference. First operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 48 states. [2022-04-28 11:37:03,901 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:03,901 INFO L93 Difference]: Finished difference Result 48 states and 65 transitions. [2022-04-28 11:37:03,901 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 65 transitions. [2022-04-28 11:37:03,901 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:03,901 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:03,902 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 11:37:03,902 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 11:37:03,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-28 11:37:03,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 65 transitions. [2022-04-28 11:37:03,904 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 65 transitions. Word has length 24 [2022-04-28 11:37:03,904 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 11:37:03,904 INFO L495 AbstractCegarLoop]: Abstraction has 48 states and 65 transitions. [2022-04-28 11:37:03,905 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:03,905 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 48 states and 65 transitions. [2022-04-28 11:37:04,065 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 65 edges. 65 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:04,065 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 65 transitions. [2022-04-28 11:37:04,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-28 11:37:04,066 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 11:37:04,066 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 11:37:04,066 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-28 11:37:04,067 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 11:37:04,067 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 11:37:04,067 INFO L85 PathProgramCache]: Analyzing trace with hash -5094773, now seen corresponding path program 1 times [2022-04-28 11:37:04,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 11:37:04,067 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [447226164] [2022-04-28 11:37:04,067 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 11:37:04,067 INFO L85 PathProgramCache]: Analyzing trace with hash -5094773, now seen corresponding path program 2 times [2022-04-28 11:37:04,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 11:37:04,068 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1642532646] [2022-04-28 11:37:04,068 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 11:37:04,068 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 11:37:04,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:37:04,219 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-28 11:37:04,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:37:04,225 INFO L290 TraceCheckUtils]: 0: Hoare triple {702#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {685#true} is VALID [2022-04-28 11:37:04,225 INFO L290 TraceCheckUtils]: 1: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-28 11:37:04,225 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {685#true} {685#true} #103#return; {685#true} is VALID [2022-04-28 11:37:04,225 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-28 11:37:04,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:37:04,229 INFO L290 TraceCheckUtils]: 0: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-28 11:37:04,229 INFO L290 TraceCheckUtils]: 1: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-28 11:37:04,229 INFO L290 TraceCheckUtils]: 2: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-28 11:37:04,229 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {685#true} {685#true} #81#return; {685#true} is VALID [2022-04-28 11:37:04,230 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-28 11:37:04,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:37:04,232 INFO L290 TraceCheckUtils]: 0: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-28 11:37:04,233 INFO L290 TraceCheckUtils]: 1: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-28 11:37:04,233 INFO L290 TraceCheckUtils]: 2: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-28 11:37:04,233 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {685#true} {685#true} #83#return; {685#true} is VALID [2022-04-28 11:37:04,233 INFO L272 TraceCheckUtils]: 0: Hoare triple {685#true} call ULTIMATE.init(); {702#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-28 11:37:04,234 INFO L290 TraceCheckUtils]: 1: Hoare triple {702#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {685#true} is VALID [2022-04-28 11:37:04,234 INFO L290 TraceCheckUtils]: 2: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-28 11:37:04,234 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {685#true} {685#true} #103#return; {685#true} is VALID [2022-04-28 11:37:04,234 INFO L272 TraceCheckUtils]: 4: Hoare triple {685#true} call #t~ret5 := main(); {685#true} is VALID [2022-04-28 11:37:04,234 INFO L290 TraceCheckUtils]: 5: Hoare triple {685#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {685#true} is VALID [2022-04-28 11:37:04,234 INFO L272 TraceCheckUtils]: 6: Hoare triple {685#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 50 then 1 else 0)); {685#true} is VALID [2022-04-28 11:37:04,234 INFO L290 TraceCheckUtils]: 7: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-28 11:37:04,234 INFO L290 TraceCheckUtils]: 8: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-28 11:37:04,234 INFO L290 TraceCheckUtils]: 9: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-28 11:37:04,235 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {685#true} {685#true} #81#return; {685#true} is VALID [2022-04-28 11:37:04,235 INFO L272 TraceCheckUtils]: 11: Hoare triple {685#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {685#true} is VALID [2022-04-28 11:37:04,235 INFO L290 TraceCheckUtils]: 12: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-28 11:37:04,235 INFO L290 TraceCheckUtils]: 13: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-28 11:37:04,235 INFO L290 TraceCheckUtils]: 14: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-28 11:37:04,235 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {685#true} {685#true} #83#return; {685#true} is VALID [2022-04-28 11:37:04,236 INFO L290 TraceCheckUtils]: 16: Hoare triple {685#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-28 11:37:04,236 INFO L290 TraceCheckUtils]: 17: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-28 11:37:04,236 INFO L290 TraceCheckUtils]: 18: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-28 11:37:04,237 INFO L290 TraceCheckUtils]: 19: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-28 11:37:04,237 INFO L290 TraceCheckUtils]: 20: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-28 11:37:04,238 INFO L290 TraceCheckUtils]: 21: Hoare triple {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} assume !false; {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-28 11:37:04,239 INFO L272 TraceCheckUtils]: 22: Hoare triple {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {700#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-28 11:37:04,239 INFO L290 TraceCheckUtils]: 23: Hoare triple {700#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {701#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-28 11:37:04,240 INFO L290 TraceCheckUtils]: 24: Hoare triple {701#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {686#false} is VALID [2022-04-28 11:37:04,240 INFO L290 TraceCheckUtils]: 25: Hoare triple {686#false} assume !false; {686#false} is VALID [2022-04-28 11:37:04,240 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-04-28 11:37:04,240 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 11:37:04,240 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1642532646] [2022-04-28 11:37:04,240 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1642532646] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:37:04,240 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:37:04,240 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-28 11:37:04,240 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 11:37:04,241 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [447226164] [2022-04-28 11:37:04,241 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [447226164] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:37:04,241 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:37:04,241 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-28 11:37:04,241 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1661697641] [2022-04-28 11:37:04,241 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 11:37:04,241 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 26 [2022-04-28 11:37:04,241 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 11:37:04,242 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:04,255 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 22 edges. 22 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:04,256 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-28 11:37:04,256 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 11:37:04,256 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-28 11:37:04,256 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-28 11:37:04,257 INFO L87 Difference]: Start difference. First operand 48 states and 65 transitions. Second operand has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:08,974 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:37:13,673 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:37:17,198 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:37:23,567 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:37:25,577 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:37:28,353 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-28 11:37:31,347 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:31,348 INFO L93 Difference]: Finished difference Result 76 states and 111 transitions. [2022-04-28 11:37:31,348 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-28 11:37:31,348 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 26 [2022-04-28 11:37:31,348 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 11:37:31,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:31,350 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-28 11:37:31,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:31,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-28 11:37:31,352 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 90 transitions. [2022-04-28 11:37:31,684 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 90 edges. 90 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:31,686 INFO L225 Difference]: With dead ends: 76 [2022-04-28 11:37:31,686 INFO L226 Difference]: Without dead ends: 72 [2022-04-28 11:37:31,686 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-28 11:37:31,687 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 38 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 226 mSolverCounterSat, 76 mSolverCounterUnsat, 6 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 76 IncrementalHoareTripleChecker+Valid, 226 IncrementalHoareTripleChecker+Invalid, 6 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.7s IncrementalHoareTripleChecker+Time [2022-04-28 11:37:31,687 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 52 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [76 Valid, 226 Invalid, 6 Unknown, 0 Unchecked, 16.7s Time] [2022-04-28 11:37:31,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-04-28 11:37:31,714 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2022-04-28 11:37:31,714 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 11:37:31,714 INFO L82 GeneralOperation]: Start isEquivalent. First operand 72 states. Second operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-28 11:37:31,718 INFO L74 IsIncluded]: Start isIncluded. First operand 72 states. Second operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-28 11:37:31,718 INFO L87 Difference]: Start difference. First operand 72 states. Second operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-28 11:37:31,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:31,722 INFO L93 Difference]: Finished difference Result 72 states and 105 transitions. [2022-04-28 11:37:31,722 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 105 transitions. [2022-04-28 11:37:31,722 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:31,723 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:31,723 INFO L74 IsIncluded]: Start isIncluded. First operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) Second operand 72 states. [2022-04-28 11:37:31,723 INFO L87 Difference]: Start difference. First operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) Second operand 72 states. [2022-04-28 11:37:31,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:31,727 INFO L93 Difference]: Finished difference Result 72 states and 105 transitions. [2022-04-28 11:37:31,727 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 105 transitions. [2022-04-28 11:37:31,727 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:31,727 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:31,727 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 11:37:31,727 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 11:37:31,728 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-28 11:37:31,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 100 transitions. [2022-04-28 11:37:31,730 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 100 transitions. Word has length 26 [2022-04-28 11:37:31,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 11:37:31,731 INFO L495 AbstractCegarLoop]: Abstraction has 69 states and 100 transitions. [2022-04-28 11:37:31,731 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-28 11:37:31,731 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 69 states and 100 transitions. [2022-04-28 11:37:32,252 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 100 edges. 100 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:32,253 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 100 transitions. [2022-04-28 11:37:32,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-28 11:37:32,253 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 11:37:32,253 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 11:37:32,253 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-28 11:37:32,254 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 11:37:32,254 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 11:37:32,254 INFO L85 PathProgramCache]: Analyzing trace with hash -2000886032, now seen corresponding path program 1 times [2022-04-28 11:37:32,254 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 11:37:32,254 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1831744497] [2022-04-28 11:37:32,254 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 11:37:32,254 INFO L85 PathProgramCache]: Analyzing trace with hash -2000886032, now seen corresponding path program 2 times [2022-04-28 11:37:32,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 11:37:32,255 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1188214154] [2022-04-28 11:37:32,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 11:37:32,255 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 11:37:32,266 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 11:37:32,266 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1566550874] [2022-04-28 11:37:32,266 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 11:37:32,266 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 11:37:32,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 11:37:32,268 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-28 11:37:32,275 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-28 11:37:32,344 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 11:37:32,344 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 11:37:32,346 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-28 11:37:32,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:37:32,363 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 11:37:32,590 INFO L272 TraceCheckUtils]: 0: Hoare triple {1149#true} call ULTIMATE.init(); {1149#true} is VALID [2022-04-28 11:37:32,607 INFO L290 TraceCheckUtils]: 1: Hoare triple {1149#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {1149#true} is VALID [2022-04-28 11:37:32,608 INFO L290 TraceCheckUtils]: 2: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-28 11:37:32,608 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1149#true} {1149#true} #103#return; {1149#true} is VALID [2022-04-28 11:37:32,608 INFO L272 TraceCheckUtils]: 4: Hoare triple {1149#true} call #t~ret5 := main(); {1149#true} is VALID [2022-04-28 11:37:32,608 INFO L290 TraceCheckUtils]: 5: Hoare triple {1149#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1149#true} is VALID [2022-04-28 11:37:32,608 INFO L272 TraceCheckUtils]: 6: Hoare triple {1149#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 50 then 1 else 0)); {1149#true} is VALID [2022-04-28 11:37:32,608 INFO L290 TraceCheckUtils]: 7: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-28 11:37:32,610 INFO L290 TraceCheckUtils]: 8: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-28 11:37:32,610 INFO L290 TraceCheckUtils]: 9: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-28 11:37:32,610 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1149#true} {1149#true} #81#return; {1149#true} is VALID [2022-04-28 11:37:32,612 INFO L272 TraceCheckUtils]: 11: Hoare triple {1149#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1149#true} is VALID [2022-04-28 11:37:32,612 INFO L290 TraceCheckUtils]: 12: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-28 11:37:32,621 INFO L290 TraceCheckUtils]: 13: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-28 11:37:32,622 INFO L290 TraceCheckUtils]: 14: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-28 11:37:32,622 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1149#true} {1149#true} #83#return; {1149#true} is VALID [2022-04-28 11:37:32,625 INFO L290 TraceCheckUtils]: 16: Hoare triple {1149#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-28 11:37:32,625 INFO L290 TraceCheckUtils]: 17: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-28 11:37:32,626 INFO L290 TraceCheckUtils]: 18: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-28 11:37:32,627 INFO L290 TraceCheckUtils]: 19: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-28 11:37:32,627 INFO L272 TraceCheckUtils]: 20: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1149#true} is VALID [2022-04-28 11:37:32,627 INFO L290 TraceCheckUtils]: 21: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-28 11:37:32,627 INFO L290 TraceCheckUtils]: 22: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-28 11:37:32,627 INFO L290 TraceCheckUtils]: 23: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-28 11:37:32,628 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {1149#true} {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #85#return; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-28 11:37:32,628 INFO L272 TraceCheckUtils]: 25: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {1149#true} is VALID [2022-04-28 11:37:32,628 INFO L290 TraceCheckUtils]: 26: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-28 11:37:32,628 INFO L290 TraceCheckUtils]: 27: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-28 11:37:32,628 INFO L290 TraceCheckUtils]: 28: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-28 11:37:32,628 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1149#true} {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #87#return; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-28 11:37:32,629 INFO L272 TraceCheckUtils]: 30: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {1245#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 11:37:32,630 INFO L290 TraceCheckUtils]: 31: Hoare triple {1245#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1249#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 11:37:32,630 INFO L290 TraceCheckUtils]: 32: Hoare triple {1249#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1150#false} is VALID [2022-04-28 11:37:32,630 INFO L290 TraceCheckUtils]: 33: Hoare triple {1150#false} assume !false; {1150#false} is VALID [2022-04-28 11:37:32,630 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-04-28 11:37:32,630 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 11:37:32,631 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 11:37:32,631 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1188214154] [2022-04-28 11:37:32,631 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 11:37:32,631 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1566550874] [2022-04-28 11:37:32,631 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1566550874] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:37:32,631 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:37:32,631 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 11:37:32,632 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 11:37:32,632 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1831744497] [2022-04-28 11:37:32,632 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1831744497] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:37:32,632 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:37:32,632 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 11:37:32,632 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2011431420] [2022-04-28 11:37:32,632 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 11:37:32,632 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-04-28 11:37:32,633 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 11:37:32,633 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:32,655 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 28 edges. 28 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:32,655 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 11:37:32,655 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 11:37:32,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 11:37:32,655 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 11:37:32,656 INFO L87 Difference]: Start difference. First operand 69 states and 100 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:36,646 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-28 11:37:37,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:37,449 INFO L93 Difference]: Finished difference Result 80 states and 109 transitions. [2022-04-28 11:37:37,449 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 11:37:37,449 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-04-28 11:37:37,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 11:37:37,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:37,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 11:37:37,451 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:37,452 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-28 11:37:37,452 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-28 11:37:37,519 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:37,521 INFO L225 Difference]: With dead ends: 80 [2022-04-28 11:37:37,521 INFO L226 Difference]: Without dead ends: 57 [2022-04-28 11:37:37,521 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-28 11:37:37,522 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 6 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2022-04-28 11:37:37,522 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 144 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 54 Invalid, 1 Unknown, 0 Unchecked, 2.4s Time] [2022-04-28 11:37:37,523 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-04-28 11:37:37,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2022-04-28 11:37:37,552 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 11:37:37,552 INFO L82 GeneralOperation]: Start isEquivalent. First operand 57 states. Second operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-28 11:37:37,555 INFO L74 IsIncluded]: Start isIncluded. First operand 57 states. Second operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-28 11:37:37,556 INFO L87 Difference]: Start difference. First operand 57 states. Second operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-28 11:37:37,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:37,563 INFO L93 Difference]: Finished difference Result 57 states and 82 transitions. [2022-04-28 11:37:37,563 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 82 transitions. [2022-04-28 11:37:37,563 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:37,563 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:37,563 INFO L74 IsIncluded]: Start isIncluded. First operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand 57 states. [2022-04-28 11:37:37,564 INFO L87 Difference]: Start difference. First operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand 57 states. [2022-04-28 11:37:37,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:37,566 INFO L93 Difference]: Finished difference Result 57 states and 82 transitions. [2022-04-28 11:37:37,566 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 82 transitions. [2022-04-28 11:37:37,566 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:37,566 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:37,566 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 11:37:37,566 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 11:37:37,567 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-28 11:37:37,568 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 82 transitions. [2022-04-28 11:37:37,569 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 82 transitions. Word has length 34 [2022-04-28 11:37:37,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 11:37:37,570 INFO L495 AbstractCegarLoop]: Abstraction has 57 states and 82 transitions. [2022-04-28 11:37:37,570 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:37,570 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 57 states and 82 transitions. [2022-04-28 11:37:37,925 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 82 edges. 82 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:37,925 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 82 transitions. [2022-04-28 11:37:37,926 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-28 11:37:37,926 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 11:37:37,926 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 11:37:37,932 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-28 11:37:38,126 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 11:37:38,129 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 11:37:38,129 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 11:37:38,129 INFO L85 PathProgramCache]: Analyzing trace with hash -965267381, now seen corresponding path program 1 times [2022-04-28 11:37:38,129 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 11:37:38,129 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [783015395] [2022-04-28 11:37:38,130 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 11:37:38,130 INFO L85 PathProgramCache]: Analyzing trace with hash -965267381, now seen corresponding path program 2 times [2022-04-28 11:37:38,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 11:37:38,130 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1704733966] [2022-04-28 11:37:38,130 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 11:37:38,130 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 11:37:38,158 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 11:37:38,158 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1318718690] [2022-04-28 11:37:38,158 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 11:37:38,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 11:37:38,159 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 11:37:38,167 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-28 11:37:38,176 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-28 11:37:38,228 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-28 11:37:38,229 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-28 11:37:38,229 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-28 11:37:38,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-28 11:37:38,238 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-28 11:37:38,391 INFO L272 TraceCheckUtils]: 0: Hoare triple {1645#true} call ULTIMATE.init(); {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L290 TraceCheckUtils]: 1: Hoare triple {1645#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L290 TraceCheckUtils]: 2: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1645#true} {1645#true} #103#return; {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L272 TraceCheckUtils]: 4: Hoare triple {1645#true} call #t~ret5 := main(); {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L290 TraceCheckUtils]: 5: Hoare triple {1645#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L272 TraceCheckUtils]: 6: Hoare triple {1645#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 50 then 1 else 0)); {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L290 TraceCheckUtils]: 7: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L290 TraceCheckUtils]: 8: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L290 TraceCheckUtils]: 9: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-28 11:37:38,392 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1645#true} {1645#true} #81#return; {1645#true} is VALID [2022-04-28 11:37:38,393 INFO L272 TraceCheckUtils]: 11: Hoare triple {1645#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1645#true} is VALID [2022-04-28 11:37:38,393 INFO L290 TraceCheckUtils]: 12: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-28 11:37:38,393 INFO L290 TraceCheckUtils]: 13: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-28 11:37:38,393 INFO L290 TraceCheckUtils]: 14: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-28 11:37:38,393 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1645#true} {1645#true} #83#return; {1645#true} is VALID [2022-04-28 11:37:38,393 INFO L290 TraceCheckUtils]: 16: Hoare triple {1645#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,394 INFO L290 TraceCheckUtils]: 17: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,394 INFO L290 TraceCheckUtils]: 18: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,394 INFO L290 TraceCheckUtils]: 19: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,395 INFO L290 TraceCheckUtils]: 20: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,395 INFO L290 TraceCheckUtils]: 21: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,395 INFO L272 TraceCheckUtils]: 22: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1645#true} is VALID [2022-04-28 11:37:38,395 INFO L290 TraceCheckUtils]: 23: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-28 11:37:38,395 INFO L290 TraceCheckUtils]: 24: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-28 11:37:38,395 INFO L290 TraceCheckUtils]: 25: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-28 11:37:38,396 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {1645#true} {1698#(and (= main_~p~0 0) (= main_~h~0 0))} #85#return; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,396 INFO L272 TraceCheckUtils]: 27: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {1645#true} is VALID [2022-04-28 11:37:38,396 INFO L290 TraceCheckUtils]: 28: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-28 11:37:38,396 INFO L290 TraceCheckUtils]: 29: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-28 11:37:38,396 INFO L290 TraceCheckUtils]: 30: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-28 11:37:38,397 INFO L284 TraceCheckUtils]: 31: Hoare quadruple {1645#true} {1698#(and (= main_~p~0 0) (= main_~h~0 0))} #87#return; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-28 11:37:38,398 INFO L272 TraceCheckUtils]: 32: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {1747#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-28 11:37:38,399 INFO L290 TraceCheckUtils]: 33: Hoare triple {1747#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1751#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-28 11:37:38,399 INFO L290 TraceCheckUtils]: 34: Hoare triple {1751#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1646#false} is VALID [2022-04-28 11:37:38,399 INFO L290 TraceCheckUtils]: 35: Hoare triple {1646#false} assume !false; {1646#false} is VALID [2022-04-28 11:37:38,399 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-04-28 11:37:38,399 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-28 11:37:38,399 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-28 11:37:38,400 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1704733966] [2022-04-28 11:37:38,400 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-28 11:37:38,400 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1318718690] [2022-04-28 11:37:38,400 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1318718690] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:37:38,400 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:37:38,400 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 11:37:38,400 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-28 11:37:38,400 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [783015395] [2022-04-28 11:37:38,400 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [783015395] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-28 11:37:38,400 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-28 11:37:38,400 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-28 11:37:38,400 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [771395801] [2022-04-28 11:37:38,400 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-28 11:37:38,401 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-28 11:37:38,401 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-28 11:37:38,401 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:38,419 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 29 edges. 29 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:38,419 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-28 11:37:38,419 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-28 11:37:38,420 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-28 11:37:38,420 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-28 11:37:38,420 INFO L87 Difference]: Start difference. First operand 57 states and 82 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:43,793 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:43,794 INFO L93 Difference]: Finished difference Result 70 states and 95 transitions. [2022-04-28 11:37:43,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-28 11:37:43,794 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-28 11:37:43,794 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-28 11:37:43,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:43,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 69 transitions. [2022-04-28 11:37:43,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:43,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 69 transitions. [2022-04-28 11:37:43,797 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 69 transitions. [2022-04-28 11:37:43,869 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:43,872 INFO L225 Difference]: With dead ends: 70 [2022-04-28 11:37:43,872 INFO L226 Difference]: Without dead ends: 67 [2022-04-28 11:37:43,872 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-28 11:37:43,873 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-28 11:37:43,873 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 151 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-28 11:37:43,874 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-04-28 11:37:43,892 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2022-04-28 11:37:43,892 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-28 11:37:43,892 INFO L82 GeneralOperation]: Start isEquivalent. First operand 67 states. Second operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 11:37:43,892 INFO L74 IsIncluded]: Start isIncluded. First operand 67 states. Second operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 11:37:43,893 INFO L87 Difference]: Start difference. First operand 67 states. Second operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 11:37:43,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:43,895 INFO L93 Difference]: Finished difference Result 67 states and 91 transitions. [2022-04-28 11:37:43,895 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2022-04-28 11:37:43,896 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:43,896 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:43,896 INFO L74 IsIncluded]: Start isIncluded. First operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand 67 states. [2022-04-28 11:37:43,896 INFO L87 Difference]: Start difference. First operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand 67 states. [2022-04-28 11:37:43,898 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-28 11:37:43,899 INFO L93 Difference]: Finished difference Result 67 states and 91 transitions. [2022-04-28 11:37:43,899 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2022-04-28 11:37:43,899 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-28 11:37:43,899 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-28 11:37:43,899 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-28 11:37:43,899 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-28 11:37:43,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-28 11:37:43,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 91 transitions. [2022-04-28 11:37:43,902 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 91 transitions. Word has length 36 [2022-04-28 11:37:43,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-28 11:37:43,902 INFO L495 AbstractCegarLoop]: Abstraction has 67 states and 91 transitions. [2022-04-28 11:37:43,902 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-28 11:37:43,902 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 67 states and 91 transitions. [2022-04-28 11:37:44,208 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 91 edges. 91 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-28 11:37:44,209 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2022-04-28 11:37:44,209 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-04-28 11:37:44,209 INFO L187 NwaCegarLoop]: Found error trace [2022-04-28 11:37:44,210 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-28 11:37:44,218 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-28 11:37:44,413 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 11:37:44,414 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-28 11:37:44,414 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-28 11:37:44,414 INFO L85 PathProgramCache]: Analyzing trace with hash 1670386034, now seen corresponding path program 1 times [2022-04-28 11:37:44,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-28 11:37:44,415 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1272780804] [2022-04-28 11:37:44,415 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-28 11:37:44,415 INFO L85 PathProgramCache]: Analyzing trace with hash 1670386034, now seen corresponding path program 2 times [2022-04-28 11:37:44,415 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-28 11:37:44,415 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [675170609] [2022-04-28 11:37:44,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-28 11:37:44,415 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-28 11:37:44,446 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-28 11:37:44,446 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [516948867] [2022-04-28 11:37:44,446 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-28 11:37:44,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-28 11:37:44,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-28 11:37:44,456 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-28 11:37:44,457 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process