/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_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 14:12:59,317 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 14:12:59,319 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 14:12:59,352 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 14:12:59,352 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 14:12:59,353 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 14:12:59,355 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 14:12:59,357 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 14:12:59,358 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 14:12:59,361 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 14:12:59,361 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 14:12:59,362 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 14:12:59,363 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 14:12:59,364 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 14:12:59,365 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 14:12:59,365 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 14:12:59,366 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 14:12:59,366 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 14:12:59,369 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 14:12:59,372 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 14:12:59,374 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 14:12:59,374 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 14:12:59,375 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 14:12:59,375 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 14:12:59,376 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 14:12:59,380 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 14:12:59,380 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 14:12:59,381 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 14:12:59,381 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 14:12:59,381 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 14:12:59,382 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 14:12:59,382 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 14:12:59,383 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 14:12:59,384 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 14:12:59,384 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 14:12:59,385 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 14:12:59,385 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 14:12:59,385 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 14:12:59,385 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 14:12:59,385 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 14:12:59,386 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 14:12:59,387 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 14:12:59,387 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-15 14:12:59,395 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 14:12:59,395 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 14:12:59,396 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 14:12:59,396 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 14:12:59,396 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 14:12:59,396 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 14:12:59,396 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 14:12:59,396 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 14:12:59,396 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 14:12:59,397 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 14:12:59,397 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 14:12:59,397 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 14:12:59,397 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 14:12:59,397 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 14:12:59,397 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 14:12:59,398 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 14:12:59,398 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 14:12:59,398 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 14:12:59,398 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 14:12:59,398 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 14:12:59,398 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 14:12:59,398 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-15 14:12:59,398 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-15 14:12:59,564 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 14:12:59,585 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 14:12:59,587 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 14:12:59,587 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 14:12:59,588 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 14:12:59,589 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound20.c [2022-04-15 14:12:59,651 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d4bea1b72/cc9c6fcf187b4d07be69aa9f3f0fea44/FLAG58397d0e5 [2022-04-15 14:12:59,994 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 14:12:59,994 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound20.c [2022-04-15 14:12:59,999 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d4bea1b72/cc9c6fcf187b4d07be69aa9f3f0fea44/FLAG58397d0e5 [2022-04-15 14:13:00,007 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d4bea1b72/cc9c6fcf187b4d07be69aa9f3f0fea44 [2022-04-15 14:13:00,009 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 14:13:00,010 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 14:13:00,021 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 14:13:00,021 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 14:13:00,023 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 14:13:00,024 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,025 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7aa2f323 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00, skipping insertion in model container [2022-04-15 14:13:00,025 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,029 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 14:13:00,041 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 14:13:00,159 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_valuebound20.c[525,538] [2022-04-15 14:13:00,180 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 14:13:00,187 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 14:13:00,195 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_valuebound20.c[525,538] [2022-04-15 14:13:00,207 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 14:13:00,215 INFO L208 MainTranslator]: Completed translation [2022-04-15 14:13:00,215 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00 WrapperNode [2022-04-15 14:13:00,215 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 14:13:00,216 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 14:13:00,216 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 14:13:00,216 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 14:13:00,222 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,223 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,227 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,227 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,231 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,234 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,235 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,236 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 14:13:00,237 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 14:13:00,237 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 14:13:00,237 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 14:13:00,238 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (1/1) ... [2022-04-15 14:13:00,242 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 14:13:00,251 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 14:13:00,259 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-15 14:13:00,267 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-15 14:13:00,290 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 14:13:00,291 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 14:13:00,291 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 14:13:00,291 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 14:13:00,291 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 14:13:00,291 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 14:13:00,292 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 14:13:00,292 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 14:13:00,292 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 14:13:00,292 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 14:13:00,292 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-15 14:13:00,292 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 14:13:00,293 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 14:13:00,293 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 14:13:00,293 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 14:13:00,295 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 14:13:00,295 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 14:13:00,295 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 14:13:00,295 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 14:13:00,295 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 14:13:00,340 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 14:13:00,341 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 14:13:00,494 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 14:13:00,519 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 14:13:00,520 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-15 14:13:00,521 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 02:13:00 BoogieIcfgContainer [2022-04-15 14:13:00,521 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 14:13:00,522 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 14:13:00,522 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 14:13:00,525 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 14:13:00,525 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 02:13:00" (1/3) ... [2022-04-15 14:13:00,525 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3e124951 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 02:13:00, skipping insertion in model container [2022-04-15 14:13:00,525 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 02:13:00" (2/3) ... [2022-04-15 14:13:00,526 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3e124951 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 02:13:00, skipping insertion in model container [2022-04-15 14:13:00,526 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 02:13:00" (3/3) ... [2022-04-15 14:13:00,527 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_valuebound20.c [2022-04-15 14:13:00,530 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 14:13:00,530 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 14:13:00,560 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 14:13:00,566 INFO L340 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 [2022-04-15 14:13:00,566 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 14:13:00,587 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-15 14:13:00,592 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-15 14:13:00,592 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 14:13:00,593 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 14:13:00,593 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 14:13:00,596 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 14:13:00,596 INFO L85 PathProgramCache]: Analyzing trace with hash 223850557, now seen corresponding path program 1 times [2022-04-15 14:13:00,601 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 14:13:00,601 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1240885184] [2022-04-15 14:13:00,608 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 14:13:00,608 INFO L85 PathProgramCache]: Analyzing trace with hash 223850557, now seen corresponding path program 2 times [2022-04-15 14:13:00,610 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 14:13:00,611 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [997590805] [2022-04-15 14:13:00,611 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 14:13:00,611 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 14:13:00,687 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:00,726 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 14:13:00,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:00,748 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-15 14:13:00,748 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 14:13:00,748 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-15 14:13:00,749 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 14:13:00,750 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:00,754 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 14:13:00,755 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 14:13:00,755 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 14:13:00,755 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-15 14:13:00,755 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-15 14:13:00,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:00,760 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 14:13:00,761 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 14:13:00,761 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 14:13:00,761 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-15 14:13:00,762 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-15 14:13:00,762 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-15 14:13:00,762 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 14:13:00,762 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-15 14:13:00,763 INFO L272 TraceCheckUtils]: 4: Hoare triple {41#true} call #t~ret5 := main(); {41#true} is VALID [2022-04-15 14:13:00,763 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-15 14:13:00,763 INFO L272 TraceCheckUtils]: 6: Hoare triple {41#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 20 then 1 else 0)); {41#true} is VALID [2022-04-15 14:13:00,763 INFO L290 TraceCheckUtils]: 7: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 14:13:00,763 INFO L290 TraceCheckUtils]: 8: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 14:13:00,764 INFO L290 TraceCheckUtils]: 9: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 14:13:00,764 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-15 14:13:00,764 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-15 14:13:00,764 INFO L290 TraceCheckUtils]: 12: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 14:13:00,764 INFO L290 TraceCheckUtils]: 13: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 14:13:00,765 INFO L290 TraceCheckUtils]: 14: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 14:13:00,765 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-15 14:13:00,765 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-15 14:13:00,765 INFO L290 TraceCheckUtils]: 17: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-15 14:13:00,765 INFO L290 TraceCheckUtils]: 18: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-15 14:13:00,765 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-15 14:13:00,766 INFO L290 TraceCheckUtils]: 20: Hoare triple {42#false} ~cond := #in~cond; {42#false} is VALID [2022-04-15 14:13:00,766 INFO L290 TraceCheckUtils]: 21: Hoare triple {42#false} assume 0 == ~cond; {42#false} is VALID [2022-04-15 14:13:00,766 INFO L290 TraceCheckUtils]: 22: Hoare triple {42#false} assume !false; {42#false} is VALID [2022-04-15 14:13:00,766 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-15 14:13:00,767 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 14:13:00,767 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [997590805] [2022-04-15 14:13:00,767 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [997590805] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:13:00,767 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:13:00,767 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 14:13:00,769 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 14:13:00,769 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1240885184] [2022-04-15 14:13:00,769 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1240885184] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:13:00,769 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:13:00,770 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 14:13:00,770 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1909886429] [2022-04-15 14:13:00,770 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 14:13:00,773 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-15 14:13:00,774 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 14:13:00,776 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-15 14:13:00,794 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-15 14:13:00,795 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 14:13:00,795 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 14:13:00,808 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 14:13:00,808 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 14:13:00,810 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-15 14:13:02,912 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-15 14:13:05,738 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-15 14:13:05,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:13:05,767 INFO L93 Difference]: Finished difference Result 69 states and 113 transitions. [2022-04-15 14:13:05,767 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 14:13:05,768 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-15 14:13:05,768 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 14:13:05,769 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-15 14:13:05,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-15 14:13:05,793 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-15 14:13:05,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-15 14:13:05,799 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 113 transitions. [2022-04-15 14:13:05,942 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-15 14:13:05,949 INFO L225 Difference]: With dead ends: 69 [2022-04-15 14:13:05,949 INFO L226 Difference]: Without dead ends: 33 [2022-04-15 14:13:05,951 INFO L912 BasicCegarLoop]: 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-15 14:13:05,953 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 19 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 14 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2022-04-15 14:13:05,954 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 42 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 10 Invalid, 2 Unknown, 0 Unchecked, 4.1s Time] [2022-04-15 14:13:05,964 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-15 14:13:05,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-15 14:13:05,978 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 14:13:05,980 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-15 14:13:05,983 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-15 14:13:05,985 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-15 14:13:05,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:13:05,989 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-15 14:13:05,989 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-15 14:13:05,990 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:13:05,990 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:13:05,990 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-15 14:13:05,991 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-15 14:13:05,994 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:13:05,995 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-15 14:13:05,995 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-15 14:13:05,997 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:13:05,997 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:13:05,998 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 14:13:05,998 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 14:13:05,998 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-15 14:13:06,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2022-04-15 14:13:06,009 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 23 [2022-04-15 14:13:06,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 14:13:06,010 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2022-04-15 14:13:06,011 INFO L479 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-15 14:13:06,011 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 33 states and 44 transitions. [2022-04-15 14:13:06,059 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-15 14:13:06,059 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-15 14:13:06,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-15 14:13:06,061 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 14:13:06,061 INFO L499 BasicCegarLoop]: 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-15 14:13:06,062 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 14:13:06,062 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 14:13:06,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 14:13:06,064 INFO L85 PathProgramCache]: Analyzing trace with hash -563604624, now seen corresponding path program 1 times [2022-04-15 14:13:06,064 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 14:13:06,067 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1726181663] [2022-04-15 14:13:06,073 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 14:13:06,073 INFO L85 PathProgramCache]: Analyzing trace with hash -563604624, now seen corresponding path program 2 times [2022-04-15 14:13:06,074 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 14:13:06,074 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [802040197] [2022-04-15 14:13:06,074 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 14:13:06,075 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 14:13:06,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:06,276 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 14:13:06,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:06,283 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-15 14:13:06,283 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 14:13:06,283 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {327#true} {327#true} #103#return; {327#true} is VALID [2022-04-15 14:13:06,284 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 14:13:06,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:06,288 INFO L290 TraceCheckUtils]: 0: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 14:13:06,288 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 14:13:06,289 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 14:13:06,289 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #81#return; {327#true} is VALID [2022-04-15 14:13:06,289 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-15 14:13:06,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:06,293 INFO L290 TraceCheckUtils]: 0: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 14:13:06,293 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 14:13:06,294 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 14:13:06,294 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #83#return; {327#true} is VALID [2022-04-15 14:13:06,294 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-15 14:13:06,295 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-15 14:13:06,295 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 14:13:06,295 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #103#return; {327#true} is VALID [2022-04-15 14:13:06,295 INFO L272 TraceCheckUtils]: 4: Hoare triple {327#true} call #t~ret5 := main(); {327#true} is VALID [2022-04-15 14:13:06,295 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-15 14:13:06,295 INFO L272 TraceCheckUtils]: 6: Hoare triple {327#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 20 then 1 else 0)); {327#true} is VALID [2022-04-15 14:13:06,296 INFO L290 TraceCheckUtils]: 7: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 14:13:06,296 INFO L290 TraceCheckUtils]: 8: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 14:13:06,296 INFO L290 TraceCheckUtils]: 9: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 14:13:06,296 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {327#true} {327#true} #81#return; {327#true} is VALID [2022-04-15 14:13:06,296 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-15 14:13:06,297 INFO L290 TraceCheckUtils]: 12: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 14:13:06,297 INFO L290 TraceCheckUtils]: 13: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 14:13:06,297 INFO L290 TraceCheckUtils]: 14: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 14:13:06,297 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {327#true} {327#true} #83#return; {327#true} is VALID [2022-04-15 14:13:06,298 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-15 14:13:06,298 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-15 14:13:06,299 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-15 14:13:06,300 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-15 14:13:06,301 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-15 14:13:06,301 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-15 14:13:06,302 INFO L290 TraceCheckUtils]: 22: Hoare triple {343#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {328#false} is VALID [2022-04-15 14:13:06,302 INFO L290 TraceCheckUtils]: 23: Hoare triple {328#false} assume !false; {328#false} is VALID [2022-04-15 14:13:06,302 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-15 14:13:06,302 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 14:13:06,302 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [802040197] [2022-04-15 14:13:06,303 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [802040197] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:13:06,303 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:13:06,303 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 14:13:06,303 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 14:13:06,303 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1726181663] [2022-04-15 14:13:06,303 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1726181663] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:13:06,303 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:13:06,303 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 14:13:06,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1934886287] [2022-04-15 14:13:06,304 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 14:13:06,304 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-15 14:13:06,305 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 14:13:06,305 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-15 14:13:06,321 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-15 14:13:06,321 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-15 14:13:06,321 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 14:13:06,322 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-15 14:13:06,322 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-15 14:13:06,322 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-15 14:13:14,226 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-15 14:13:19,995 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-15 14:13:22,012 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-15 14:13:24,024 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-15 14:13:26,039 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.04s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 14:13:28,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:13:28,764 INFO L93 Difference]: Finished difference Result 67 states and 97 transitions. [2022-04-15 14:13:28,764 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 14:13:28,764 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-15 14:13:28,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 14:13:28,765 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-15 14:13:28,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 97 transitions. [2022-04-15 14:13:28,767 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-15 14:13:28,769 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 97 transitions. [2022-04-15 14:13:28,770 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 97 transitions. [2022-04-15 14:13:28,894 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 97 edges. 97 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 14:13:28,896 INFO L225 Difference]: With dead ends: 67 [2022-04-15 14:13:28,896 INFO L226 Difference]: Without dead ends: 49 [2022-04-15 14:13:28,897 INFO L912 BasicCegarLoop]: 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-15 14:13:28,897 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 34 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 41 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 14.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 59 SdHoareTripleChecker+Invalid, 251 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 14.4s IncrementalHoareTripleChecker+Time [2022-04-15 14:13:28,898 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 59 Invalid, 251 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 206 Invalid, 4 Unknown, 0 Unchecked, 14.4s Time] [2022-04-15 14:13:28,899 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2022-04-15 14:13:28,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 47. [2022-04-15 14:13:28,922 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 14:13:28,923 INFO L82 GeneralOperation]: Start isEquivalent. First operand 49 states. Second operand has 47 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 14:13:28,924 INFO L74 IsIncluded]: Start isIncluded. First operand 49 states. Second operand has 47 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 14:13:28,928 INFO L87 Difference]: Start difference. First operand 49 states. Second operand has 47 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 14:13:28,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:13:28,931 INFO L93 Difference]: Finished difference Result 49 states and 68 transitions. [2022-04-15 14:13:28,931 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 68 transitions. [2022-04-15 14:13:28,932 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:13:28,932 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:13:28,932 INFO L74 IsIncluded]: Start isIncluded. First operand has 47 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 49 states. [2022-04-15 14:13:28,932 INFO L87 Difference]: Start difference. First operand has 47 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 49 states. [2022-04-15 14:13:28,935 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:13:28,935 INFO L93 Difference]: Finished difference Result 49 states and 68 transitions. [2022-04-15 14:13:28,935 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 68 transitions. [2022-04-15 14:13:28,936 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:13:28,936 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:13:28,936 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 14:13:28,936 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 14:13:28,937 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 14:13:28,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 64 transitions. [2022-04-15 14:13:28,939 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 64 transitions. Word has length 24 [2022-04-15 14:13:28,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 14:13:28,939 INFO L478 AbstractCegarLoop]: Abstraction has 47 states and 64 transitions. [2022-04-15 14:13:28,939 INFO L479 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-15 14:13:28,939 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 47 states and 64 transitions. [2022-04-15 14:13:29,097 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 64 edges. 64 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 14:13:29,097 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 64 transitions. [2022-04-15 14:13:29,098 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-15 14:13:29,098 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 14:13:29,098 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 14:13:29,098 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-15 14:13:29,098 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 14:13:29,099 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 14:13:29,099 INFO L85 PathProgramCache]: Analyzing trace with hash -5094773, now seen corresponding path program 1 times [2022-04-15 14:13:29,099 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 14:13:29,099 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [290240314] [2022-04-15 14:13:29,099 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 14:13:29,099 INFO L85 PathProgramCache]: Analyzing trace with hash -5094773, now seen corresponding path program 2 times [2022-04-15 14:13:29,099 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 14:13:29,100 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1095165543] [2022-04-15 14:13:29,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 14:13:29,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 14:13:29,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:29,206 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 14:13:29,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:29,217 INFO L290 TraceCheckUtils]: 0: Hoare triple {700#(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); {683#true} is VALID [2022-04-15 14:13:29,217 INFO L290 TraceCheckUtils]: 1: Hoare triple {683#true} assume true; {683#true} is VALID [2022-04-15 14:13:29,217 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {683#true} {683#true} #103#return; {683#true} is VALID [2022-04-15 14:13:29,217 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 14:13:29,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:29,226 INFO L290 TraceCheckUtils]: 0: Hoare triple {683#true} ~cond := #in~cond; {683#true} is VALID [2022-04-15 14:13:29,226 INFO L290 TraceCheckUtils]: 1: Hoare triple {683#true} assume !(0 == ~cond); {683#true} is VALID [2022-04-15 14:13:29,226 INFO L290 TraceCheckUtils]: 2: Hoare triple {683#true} assume true; {683#true} is VALID [2022-04-15 14:13:29,226 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {683#true} {683#true} #81#return; {683#true} is VALID [2022-04-15 14:13:29,227 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-15 14:13:29,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:13:29,234 INFO L290 TraceCheckUtils]: 0: Hoare triple {683#true} ~cond := #in~cond; {683#true} is VALID [2022-04-15 14:13:29,234 INFO L290 TraceCheckUtils]: 1: Hoare triple {683#true} assume !(0 == ~cond); {683#true} is VALID [2022-04-15 14:13:29,234 INFO L290 TraceCheckUtils]: 2: Hoare triple {683#true} assume true; {683#true} is VALID [2022-04-15 14:13:29,234 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {683#true} {683#true} #83#return; {683#true} is VALID [2022-04-15 14:13:29,235 INFO L272 TraceCheckUtils]: 0: Hoare triple {683#true} call ULTIMATE.init(); {700#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 14:13:29,235 INFO L290 TraceCheckUtils]: 1: Hoare triple {700#(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); {683#true} is VALID [2022-04-15 14:13:29,235 INFO L290 TraceCheckUtils]: 2: Hoare triple {683#true} assume true; {683#true} is VALID [2022-04-15 14:13:29,236 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {683#true} {683#true} #103#return; {683#true} is VALID [2022-04-15 14:13:29,236 INFO L272 TraceCheckUtils]: 4: Hoare triple {683#true} call #t~ret5 := main(); {683#true} is VALID [2022-04-15 14:13:29,236 INFO L290 TraceCheckUtils]: 5: Hoare triple {683#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {683#true} is VALID [2022-04-15 14:13:29,236 INFO L272 TraceCheckUtils]: 6: Hoare triple {683#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 20 then 1 else 0)); {683#true} is VALID [2022-04-15 14:13:29,237 INFO L290 TraceCheckUtils]: 7: Hoare triple {683#true} ~cond := #in~cond; {683#true} is VALID [2022-04-15 14:13:29,237 INFO L290 TraceCheckUtils]: 8: Hoare triple {683#true} assume !(0 == ~cond); {683#true} is VALID [2022-04-15 14:13:29,238 INFO L290 TraceCheckUtils]: 9: Hoare triple {683#true} assume true; {683#true} is VALID [2022-04-15 14:13:29,238 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {683#true} {683#true} #81#return; {683#true} is VALID [2022-04-15 14:13:29,238 INFO L272 TraceCheckUtils]: 11: Hoare triple {683#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {683#true} is VALID [2022-04-15 14:13:29,238 INFO L290 TraceCheckUtils]: 12: Hoare triple {683#true} ~cond := #in~cond; {683#true} is VALID [2022-04-15 14:13:29,238 INFO L290 TraceCheckUtils]: 13: Hoare triple {683#true} assume !(0 == ~cond); {683#true} is VALID [2022-04-15 14:13:29,238 INFO L290 TraceCheckUtils]: 14: Hoare triple {683#true} assume true; {683#true} is VALID [2022-04-15 14:13:29,238 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {683#true} {683#true} #83#return; {683#true} is VALID [2022-04-15 14:13:29,239 INFO L290 TraceCheckUtils]: 16: Hoare triple {683#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 14:13:29,239 INFO L290 TraceCheckUtils]: 17: Hoare triple {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 14:13:29,240 INFO L290 TraceCheckUtils]: 18: Hoare triple {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 14:13:29,240 INFO L290 TraceCheckUtils]: 19: Hoare triple {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 14:13:29,241 INFO L290 TraceCheckUtils]: 20: Hoare triple {696#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {697#(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-15 14:13:29,243 INFO L290 TraceCheckUtils]: 21: Hoare triple {697#(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; {697#(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-15 14:13:29,245 INFO L272 TraceCheckUtils]: 22: Hoare triple {697#(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)); {698#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 14:13:29,246 INFO L290 TraceCheckUtils]: 23: Hoare triple {698#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {699#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 14:13:29,246 INFO L290 TraceCheckUtils]: 24: Hoare triple {699#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {684#false} is VALID [2022-04-15 14:13:29,247 INFO L290 TraceCheckUtils]: 25: Hoare triple {684#false} assume !false; {684#false} is VALID [2022-04-15 14:13:29,247 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-15 14:13:29,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 14:13:29,248 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1095165543] [2022-04-15 14:13:29,248 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1095165543] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:13:29,248 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:13:29,248 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 14:13:29,248 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 14:13:29,248 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [290240314] [2022-04-15 14:13:29,249 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [290240314] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:13:29,249 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:13:29,249 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 14:13:29,249 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1918222013] [2022-04-15 14:13:29,249 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 14:13:29,250 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-15 14:13:29,250 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 14:13:29,250 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-15 14:13:29,264 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-15 14:13:29,264 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-15 14:13:29,264 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 14:13:29,265 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-15 14:13:29,265 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-15 14:13:29,265 INFO L87 Difference]: Start difference. First operand 47 states and 64 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-15 14:13:39,187 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-15 14:13:43,686 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.47s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-15 14:13:47,248 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.56s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-15 14:13:51,055 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-15 14:13:53,057 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-15 14:14:03,368 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-15 14:14:05,372 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-15 14:14:05,405 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:05,405 INFO L93 Difference]: Finished difference Result 70 states and 100 transitions. [2022-04-15 14:14:05,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 14:14:05,406 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-15 14:14:05,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 14:14:05,407 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-15 14:14:05,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 80 transitions. [2022-04-15 14:14:05,412 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-15 14:14:05,415 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 80 transitions. [2022-04-15 14:14:05,415 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 80 transitions. [2022-04-15 14:14:05,641 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 80 edges. 80 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 14:14:05,643 INFO L225 Difference]: With dead ends: 70 [2022-04-15 14:14:05,643 INFO L226 Difference]: Without dead ends: 66 [2022-04-15 14:14:05,644 INFO L912 BasicCegarLoop]: 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-15 14:14:05,644 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 36 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 63 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 22.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 271 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 63 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 22.1s IncrementalHoareTripleChecker+Time [2022-04-15 14:14:05,644 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [46 Valid, 49 Invalid, 271 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [63 Valid, 201 Invalid, 7 Unknown, 0 Unchecked, 22.1s Time] [2022-04-15 14:14:05,645 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-15 14:14:05,669 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-04-15 14:14:05,669 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 14:14:05,669 INFO L82 GeneralOperation]: Start isEquivalent. First operand 66 states. Second operand has 64 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 28 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-15 14:14:05,670 INFO L74 IsIncluded]: Start isIncluded. First operand 66 states. Second operand has 64 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 28 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-15 14:14:05,670 INFO L87 Difference]: Start difference. First operand 66 states. Second operand has 64 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 28 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-15 14:14:05,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:05,673 INFO L93 Difference]: Finished difference Result 66 states and 94 transitions. [2022-04-15 14:14:05,673 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 94 transitions. [2022-04-15 14:14:05,674 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:14:05,674 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:14:05,675 INFO L74 IsIncluded]: Start isIncluded. First operand has 64 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 28 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) Second operand 66 states. [2022-04-15 14:14:05,675 INFO L87 Difference]: Start difference. First operand has 64 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 28 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) Second operand 66 states. [2022-04-15 14:14:05,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:05,678 INFO L93 Difference]: Finished difference Result 66 states and 94 transitions. [2022-04-15 14:14:05,678 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 94 transitions. [2022-04-15 14:14:05,679 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:14:05,679 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:14:05,679 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 14:14:05,679 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 14:14:05,679 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 30 states have (on average 1.2333333333333334) internal successors, (37), 33 states have internal predecessors, (37), 28 states have call successors, (28), 6 states have call predecessors, (28), 5 states have return successors, (25), 24 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-15 14:14:05,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 90 transitions. [2022-04-15 14:14:05,682 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 90 transitions. Word has length 26 [2022-04-15 14:14:05,682 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 14:14:05,682 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 90 transitions. [2022-04-15 14:14:05,682 INFO L479 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-15 14:14:05,682 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 64 states and 90 transitions. [2022-04-15 14:14:06,079 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-15 14:14:06,079 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 90 transitions. [2022-04-15 14:14:06,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-15 14:14:06,080 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 14:14:06,080 INFO L499 BasicCegarLoop]: 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-15 14:14:06,080 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-15 14:14:06,080 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 14:14:06,081 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 14:14:06,081 INFO L85 PathProgramCache]: Analyzing trace with hash -2000886032, now seen corresponding path program 1 times [2022-04-15 14:14:06,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 14:14:06,081 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1203379867] [2022-04-15 14:14:06,081 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 14:14:06,081 INFO L85 PathProgramCache]: Analyzing trace with hash -2000886032, now seen corresponding path program 2 times [2022-04-15 14:14:06,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 14:14:06,081 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [108975906] [2022-04-15 14:14:06,081 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 14:14:06,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 14:14:06,092 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 14:14:06,093 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [998641688] [2022-04-15 14:14:06,093 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 14:14:06,093 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 14:14:06,093 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 14:14:06,094 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-15 14:14:06,105 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-15 14:14:06,157 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 14:14:06,158 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 14:14:06,163 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-15 14:14:06,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:14:06,181 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 14:14:06,353 INFO L272 TraceCheckUtils]: 0: Hoare triple {1113#true} call ULTIMATE.init(); {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L290 TraceCheckUtils]: 1: Hoare triple {1113#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); {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L290 TraceCheckUtils]: 2: Hoare triple {1113#true} assume true; {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1113#true} {1113#true} #103#return; {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L272 TraceCheckUtils]: 4: Hoare triple {1113#true} call #t~ret5 := main(); {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L290 TraceCheckUtils]: 5: Hoare triple {1113#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L272 TraceCheckUtils]: 6: Hoare triple {1113#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 20 then 1 else 0)); {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L290 TraceCheckUtils]: 7: Hoare triple {1113#true} ~cond := #in~cond; {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L290 TraceCheckUtils]: 8: Hoare triple {1113#true} assume !(0 == ~cond); {1113#true} is VALID [2022-04-15 14:14:06,354 INFO L290 TraceCheckUtils]: 9: Hoare triple {1113#true} assume true; {1113#true} is VALID [2022-04-15 14:14:06,355 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1113#true} {1113#true} #81#return; {1113#true} is VALID [2022-04-15 14:14:06,355 INFO L272 TraceCheckUtils]: 11: Hoare triple {1113#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1113#true} is VALID [2022-04-15 14:14:06,355 INFO L290 TraceCheckUtils]: 12: Hoare triple {1113#true} ~cond := #in~cond; {1113#true} is VALID [2022-04-15 14:14:06,355 INFO L290 TraceCheckUtils]: 13: Hoare triple {1113#true} assume !(0 == ~cond); {1113#true} is VALID [2022-04-15 14:14:06,355 INFO L290 TraceCheckUtils]: 14: Hoare triple {1113#true} assume true; {1113#true} is VALID [2022-04-15 14:14:06,355 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1113#true} {1113#true} #83#return; {1113#true} is VALID [2022-04-15 14:14:06,356 INFO L290 TraceCheckUtils]: 16: Hoare triple {1113#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 14:14:06,356 INFO L290 TraceCheckUtils]: 17: Hoare triple {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 14:14:06,357 INFO L290 TraceCheckUtils]: 18: Hoare triple {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 14:14:06,357 INFO L290 TraceCheckUtils]: 19: Hoare triple {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 14:14:06,357 INFO L272 TraceCheckUtils]: 20: Hoare triple {1166#(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)); {1113#true} is VALID [2022-04-15 14:14:06,357 INFO L290 TraceCheckUtils]: 21: Hoare triple {1113#true} ~cond := #in~cond; {1113#true} is VALID [2022-04-15 14:14:06,357 INFO L290 TraceCheckUtils]: 22: Hoare triple {1113#true} assume !(0 == ~cond); {1113#true} is VALID [2022-04-15 14:14:06,357 INFO L290 TraceCheckUtils]: 23: Hoare triple {1113#true} assume true; {1113#true} is VALID [2022-04-15 14:14:06,358 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {1113#true} {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #85#return; {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 14:14:06,358 INFO L272 TraceCheckUtils]: 25: Hoare triple {1166#(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)); {1113#true} is VALID [2022-04-15 14:14:06,358 INFO L290 TraceCheckUtils]: 26: Hoare triple {1113#true} ~cond := #in~cond; {1113#true} is VALID [2022-04-15 14:14:06,358 INFO L290 TraceCheckUtils]: 27: Hoare triple {1113#true} assume !(0 == ~cond); {1113#true} is VALID [2022-04-15 14:14:06,359 INFO L290 TraceCheckUtils]: 28: Hoare triple {1113#true} assume true; {1113#true} is VALID [2022-04-15 14:14:06,359 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1113#true} {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #87#return; {1166#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 14:14:06,360 INFO L272 TraceCheckUtils]: 30: Hoare triple {1166#(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)); {1209#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 14:14:06,361 INFO L290 TraceCheckUtils]: 31: Hoare triple {1209#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1213#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 14:14:06,361 INFO L290 TraceCheckUtils]: 32: Hoare triple {1213#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1114#false} is VALID [2022-04-15 14:14:06,361 INFO L290 TraceCheckUtils]: 33: Hoare triple {1114#false} assume !false; {1114#false} is VALID [2022-04-15 14:14:06,361 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-15 14:14:06,361 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 14:14:06,362 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 14:14:06,362 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [108975906] [2022-04-15 14:14:06,362 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 14:14:06,362 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [998641688] [2022-04-15 14:14:06,362 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [998641688] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:14:06,362 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:14:06,362 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 14:14:06,363 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 14:14:06,363 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1203379867] [2022-04-15 14:14:06,363 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1203379867] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:14:06,363 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:14:06,363 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 14:14:06,363 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [164248266] [2022-04-15 14:14:06,363 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 14:14:06,363 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-15 14:14:06,364 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 14:14:06,364 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-15 14:14:06,389 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-15 14:14:06,389 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 14:14:06,389 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 14:14:06,390 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 14:14:06,390 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 14:14:06,390 INFO L87 Difference]: Start difference. First operand 64 states and 90 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-15 14:14:14,471 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:14,471 INFO L93 Difference]: Finished difference Result 75 states and 99 transitions. [2022-04-15 14:14:14,471 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 14:14:14,472 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-15 14:14:14,472 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 14:14:14,472 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-15 14:14:14,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 14:14:14,473 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-15 14:14:14,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 14:14:14,474 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-15 14:14:14,538 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-15 14:14:14,539 INFO L225 Difference]: With dead ends: 75 [2022-04-15 14:14:14,539 INFO L226 Difference]: Without dead ends: 52 [2022-04-15 14:14:14,540 INFO L912 BasicCegarLoop]: 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-15 14:14:14,540 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 6 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2022-04-15 14:14:14,541 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 144 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2022-04-15 14:14:14,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-15 14:14:14,574 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-04-15 14:14:14,574 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 14:14:14,574 INFO L82 GeneralOperation]: Start isEquivalent. First operand 52 states. Second operand has 52 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 22 states have call successors, (22), 5 states have call predecessors, (22), 4 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:14,575 INFO L74 IsIncluded]: Start isIncluded. First operand 52 states. Second operand has 52 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 22 states have call successors, (22), 5 states have call predecessors, (22), 4 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:14,575 INFO L87 Difference]: Start difference. First operand 52 states. Second operand has 52 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 22 states have call successors, (22), 5 states have call predecessors, (22), 4 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:14,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:14,577 INFO L93 Difference]: Finished difference Result 52 states and 72 transitions. [2022-04-15 14:14:14,577 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-15 14:14:14,577 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:14:14,577 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:14:14,578 INFO L74 IsIncluded]: Start isIncluded. First operand has 52 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 22 states have call successors, (22), 5 states have call predecessors, (22), 4 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) Second operand 52 states. [2022-04-15 14:14:14,578 INFO L87 Difference]: Start difference. First operand has 52 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 22 states have call successors, (22), 5 states have call predecessors, (22), 4 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) Second operand 52 states. [2022-04-15 14:14:14,580 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:14,580 INFO L93 Difference]: Finished difference Result 52 states and 72 transitions. [2022-04-15 14:14:14,580 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-15 14:14:14,580 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:14:14,580 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:14:14,581 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 14:14:14,581 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 14:14:14,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 22 states have call successors, (22), 5 states have call predecessors, (22), 4 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:14,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 72 transitions. [2022-04-15 14:14:14,583 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 72 transitions. Word has length 34 [2022-04-15 14:14:14,583 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 14:14:14,583 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 72 transitions. [2022-04-15 14:14:14,583 INFO L479 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-15 14:14:14,583 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 52 states and 72 transitions. [2022-04-15 14:14:16,955 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 72 edges. 71 inductive. 0 not inductive. 1 times theorem prover too weak to decide inductivity. [2022-04-15 14:14:16,967 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 72 transitions. [2022-04-15 14:14:16,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-15 14:14:16,968 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 14:14:16,968 INFO L499 BasicCegarLoop]: 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-15 14:14:16,976 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-15 14:14:17,171 WARN L460 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-15 14:14:17,172 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 14:14:17,172 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 14:14:17,172 INFO L85 PathProgramCache]: Analyzing trace with hash -965267381, now seen corresponding path program 1 times [2022-04-15 14:14:17,172 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 14:14:17,172 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [153436766] [2022-04-15 14:14:17,173 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 14:14:17,173 INFO L85 PathProgramCache]: Analyzing trace with hash -965267381, now seen corresponding path program 2 times [2022-04-15 14:14:17,173 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 14:14:17,173 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [637826218] [2022-04-15 14:14:17,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 14:14:17,173 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 14:14:17,183 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 14:14:17,183 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1701952494] [2022-04-15 14:14:17,183 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 14:14:17,183 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 14:14:17,184 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 14:14:17,184 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-15 14:14:17,185 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-15 14:14:17,257 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 14:14:17,257 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 14:14:17,258 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 14:14:17,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 14:14:17,269 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 14:14:17,386 INFO L272 TraceCheckUtils]: 0: Hoare triple {1579#true} call ULTIMATE.init(); {1579#true} is VALID [2022-04-15 14:14:17,386 INFO L290 TraceCheckUtils]: 1: Hoare triple {1579#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); {1579#true} is VALID [2022-04-15 14:14:17,386 INFO L290 TraceCheckUtils]: 2: Hoare triple {1579#true} assume true; {1579#true} is VALID [2022-04-15 14:14:17,386 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1579#true} {1579#true} #103#return; {1579#true} is VALID [2022-04-15 14:14:17,386 INFO L272 TraceCheckUtils]: 4: Hoare triple {1579#true} call #t~ret5 := main(); {1579#true} is VALID [2022-04-15 14:14:17,386 INFO L290 TraceCheckUtils]: 5: Hoare triple {1579#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1579#true} is VALID [2022-04-15 14:14:17,386 INFO L272 TraceCheckUtils]: 6: Hoare triple {1579#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 20 then 1 else 0)); {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L290 TraceCheckUtils]: 7: Hoare triple {1579#true} ~cond := #in~cond; {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L290 TraceCheckUtils]: 8: Hoare triple {1579#true} assume !(0 == ~cond); {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L290 TraceCheckUtils]: 9: Hoare triple {1579#true} assume true; {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1579#true} {1579#true} #81#return; {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L272 TraceCheckUtils]: 11: Hoare triple {1579#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L290 TraceCheckUtils]: 12: Hoare triple {1579#true} ~cond := #in~cond; {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L290 TraceCheckUtils]: 13: Hoare triple {1579#true} assume !(0 == ~cond); {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L290 TraceCheckUtils]: 14: Hoare triple {1579#true} assume true; {1579#true} is VALID [2022-04-15 14:14:17,387 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1579#true} {1579#true} #83#return; {1579#true} is VALID [2022-04-15 14:14:17,388 INFO L290 TraceCheckUtils]: 16: Hoare triple {1579#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,388 INFO L290 TraceCheckUtils]: 17: Hoare triple {1632#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,388 INFO L290 TraceCheckUtils]: 18: Hoare triple {1632#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,389 INFO L290 TraceCheckUtils]: 19: Hoare triple {1632#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,389 INFO L290 TraceCheckUtils]: 20: Hoare triple {1632#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,389 INFO L290 TraceCheckUtils]: 21: Hoare triple {1632#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,389 INFO L272 TraceCheckUtils]: 22: Hoare triple {1632#(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)); {1579#true} is VALID [2022-04-15 14:14:17,390 INFO L290 TraceCheckUtils]: 23: Hoare triple {1579#true} ~cond := #in~cond; {1579#true} is VALID [2022-04-15 14:14:17,390 INFO L290 TraceCheckUtils]: 24: Hoare triple {1579#true} assume !(0 == ~cond); {1579#true} is VALID [2022-04-15 14:14:17,390 INFO L290 TraceCheckUtils]: 25: Hoare triple {1579#true} assume true; {1579#true} is VALID [2022-04-15 14:14:17,390 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {1579#true} {1632#(and (= main_~p~0 0) (= main_~h~0 0))} #85#return; {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,390 INFO L272 TraceCheckUtils]: 27: Hoare triple {1632#(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)); {1579#true} is VALID [2022-04-15 14:14:17,390 INFO L290 TraceCheckUtils]: 28: Hoare triple {1579#true} ~cond := #in~cond; {1579#true} is VALID [2022-04-15 14:14:17,390 INFO L290 TraceCheckUtils]: 29: Hoare triple {1579#true} assume !(0 == ~cond); {1579#true} is VALID [2022-04-15 14:14:17,390 INFO L290 TraceCheckUtils]: 30: Hoare triple {1579#true} assume true; {1579#true} is VALID [2022-04-15 14:14:17,391 INFO L284 TraceCheckUtils]: 31: Hoare quadruple {1579#true} {1632#(and (= main_~p~0 0) (= main_~h~0 0))} #87#return; {1632#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 14:14:17,392 INFO L272 TraceCheckUtils]: 32: Hoare triple {1632#(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)); {1681#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 14:14:17,393 INFO L290 TraceCheckUtils]: 33: Hoare triple {1681#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1685#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 14:14:17,393 INFO L290 TraceCheckUtils]: 34: Hoare triple {1685#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1580#false} is VALID [2022-04-15 14:14:17,393 INFO L290 TraceCheckUtils]: 35: Hoare triple {1580#false} assume !false; {1580#false} is VALID [2022-04-15 14:14:17,393 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-15 14:14:17,393 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 14:14:17,394 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 14:14:17,394 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [637826218] [2022-04-15 14:14:17,394 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 14:14:17,394 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1701952494] [2022-04-15 14:14:17,394 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1701952494] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:14:17,394 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:14:17,394 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 14:14:17,394 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 14:14:17,394 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [153436766] [2022-04-15 14:14:17,394 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [153436766] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 14:14:17,394 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 14:14:17,394 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 14:14:17,395 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1436823363] [2022-04-15 14:14:17,395 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 14:14:17,395 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-15 14:14:17,395 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 14:14:17,395 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-15 14:14:17,414 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-15 14:14:17,414 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 14:14:17,414 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 14:14:17,415 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 14:14:17,415 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 14:14:17,415 INFO L87 Difference]: Start difference. First operand 52 states and 72 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-15 14:14:22,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-15 14:14:24,936 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:24,936 INFO L93 Difference]: Finished difference Result 62 states and 80 transitions. [2022-04-15 14:14:24,936 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 14:14:24,936 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-15 14:14:24,936 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 14:14:24,936 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-15 14:14:24,938 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-15 14:14:24,938 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-15 14:14:24,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-15 14:14:24,939 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 65 transitions. [2022-04-15 14:14:24,999 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-15 14:14:25,001 INFO L225 Difference]: With dead ends: 62 [2022-04-15 14:14:25,001 INFO L226 Difference]: Without dead ends: 59 [2022-04-15 14:14:25,001 INFO L912 BasicCegarLoop]: 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-15 14:14:25,002 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 6 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 150 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2022-04-15 14:14:25,002 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 150 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 45 Invalid, 1 Unknown, 0 Unchecked, 2.6s Time] [2022-04-15 14:14:25,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2022-04-15 14:14:25,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2022-04-15 14:14:25,040 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 14:14:25,041 INFO L82 GeneralOperation]: Start isEquivalent. First operand 59 states. Second operand has 59 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:25,041 INFO L74 IsIncluded]: Start isIncluded. First operand 59 states. Second operand has 59 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:25,041 INFO L87 Difference]: Start difference. First operand 59 states. Second operand has 59 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:25,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:25,043 INFO L93 Difference]: Finished difference Result 59 states and 76 transitions. [2022-04-15 14:14:25,043 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 76 transitions. [2022-04-15 14:14:25,043 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:14:25,043 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:14:25,044 INFO L74 IsIncluded]: Start isIncluded. First operand has 59 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) Second operand 59 states. [2022-04-15 14:14:25,044 INFO L87 Difference]: Start difference. First operand has 59 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) Second operand 59 states. [2022-04-15 14:14:25,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 14:14:25,046 INFO L93 Difference]: Finished difference Result 59 states and 76 transitions. [2022-04-15 14:14:25,046 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 76 transitions. [2022-04-15 14:14:25,046 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 14:14:25,046 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 14:14:25,046 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 14:14:25,046 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 14:14:25,047 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 33 states have internal predecessors, (36), 21 states have call successors, (21), 7 states have call predecessors, (21), 6 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-15 14:14:25,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 76 transitions. [2022-04-15 14:14:25,052 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 76 transitions. Word has length 36 [2022-04-15 14:14:25,052 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 14:14:25,053 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 76 transitions. [2022-04-15 14:14:25,054 INFO L479 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-15 14:14:25,054 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 59 states and 76 transitions. [2022-04-15 14:14:25,361 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 76 edges. 76 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 14:14:25,362 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 76 transitions. [2022-04-15 14:14:25,362 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-04-15 14:14:25,362 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 14:14:25,363 INFO L499 BasicCegarLoop]: 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-15 14:14:25,368 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-15 14:14:25,567 WARN L460 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-15 14:14:25,567 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 14:14:25,568 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 14:14:25,568 INFO L85 PathProgramCache]: Analyzing trace with hash 1670386034, now seen corresponding path program 1 times [2022-04-15 14:14:25,568 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 14:14:25,568 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [565431807] [2022-04-15 14:14:25,568 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 14:14:25,568 INFO L85 PathProgramCache]: Analyzing trace with hash 1670386034, now seen corresponding path program 2 times [2022-04-15 14:14:25,568 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 14:14:25,568 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1313581079] [2022-04-15 14:14:25,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 14:14:25,568 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 14:14:25,592 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 14:14:25,592 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [42120263] [2022-04-15 14:14:25,592 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 14:14:25,592 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 14:14:25,592 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 14:14:25,599 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-15 14:14:25,600 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process