/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/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-fb4f59a-m [2022-04-27 12:18:33,322 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-27 12:18:33,324 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-27 12:18:33,349 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-27 12:18:33,349 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-27 12:18:33,350 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-27 12:18:33,351 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-27 12:18:33,352 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-27 12:18:33,354 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-27 12:18:33,354 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-27 12:18:33,355 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-27 12:18:33,357 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-27 12:18:33,358 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-27 12:18:33,358 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-27 12:18:33,359 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-27 12:18:33,360 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-27 12:18:33,361 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-27 12:18:33,361 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-27 12:18:33,363 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-27 12:18:33,366 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-27 12:18:33,376 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-27 12:18:33,376 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-27 12:18:33,377 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-27 12:18:33,378 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-27 12:18:33,379 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-27 12:18:33,381 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-27 12:18:33,381 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-27 12:18:33,382 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-27 12:18:33,382 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-27 12:18:33,383 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-27 12:18:33,383 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-27 12:18:33,384 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-27 12:18:33,384 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-27 12:18:33,385 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-27 12:18:33,385 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-27 12:18:33,386 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-27 12:18:33,386 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-27 12:18:33,387 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-27 12:18:33,387 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-27 12:18:33,388 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-27 12:18:33,388 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-27 12:18:33,389 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-27 12:18:33,390 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2022-04-27 12:18:33,409 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-27 12:18:33,409 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-27 12:18:33,410 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-04-27 12:18:33,410 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-04-27 12:18:33,411 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-27 12:18:33,411 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-27 12:18:33,416 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-27 12:18:33,416 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-27 12:18:33,416 INFO L138 SettingsManager]: * Use SBE=true [2022-04-27 12:18:33,417 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-27 12:18:33,417 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-27 12:18:33,417 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-27 12:18:33,418 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-27 12:18:33,419 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-27 12:18:33,419 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-27 12:18:33,419 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-27 12:18:33,419 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-27 12:18:33,419 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-27 12:18:33,420 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-27 12:18:33,420 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-27 12:18:33,420 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-27 12:18:33,420 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-27 12:18:33,420 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-27 12:18:33,420 INFO L138 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2022-04-27 12:18:33,420 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2022-04-27 12:18:33,421 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-27 12:18:33,421 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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-27 12:18:33,605 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-27 12:18:33,624 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-27 12:18:33,626 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-27 12:18:33,627 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-27 12:18:33,627 INFO L275 PluginConnector]: CDTParser initialized [2022-04-27 12:18:33,628 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound5.c [2022-04-27 12:18:33,680 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f883fc1de/73cd5ae542da4e38819ac8ace6a2e2b1/FLAG1f1adb8f7 [2022-04-27 12:18:34,042 INFO L306 CDTParser]: Found 1 translation units. [2022-04-27 12:18:34,042 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound5.c [2022-04-27 12:18:34,048 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f883fc1de/73cd5ae542da4e38819ac8ace6a2e2b1/FLAG1f1adb8f7 [2022-04-27 12:18:34,057 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f883fc1de/73cd5ae542da4e38819ac8ace6a2e2b1 [2022-04-27 12:18:34,059 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-27 12:18:34,060 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-27 12:18:34,061 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-27 12:18:34,061 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-27 12:18:34,064 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-27 12:18:34,064 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,065 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@309d4e24 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34, skipping insertion in model container [2022-04-27 12:18:34,065 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,075 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-27 12:18:34,087 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-27 12:18:34,201 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_valuebound5.c[525,538] [2022-04-27 12:18:34,249 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-27 12:18:34,260 INFO L203 MainTranslator]: Completed pre-run [2022-04-27 12:18:34,273 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_valuebound5.c[525,538] [2022-04-27 12:18:34,301 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-27 12:18:34,326 INFO L208 MainTranslator]: Completed translation [2022-04-27 12:18:34,327 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34 WrapperNode [2022-04-27 12:18:34,327 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-27 12:18:34,328 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-27 12:18:34,328 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-27 12:18:34,328 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-27 12:18:34,337 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,337 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,344 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,344 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,351 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,355 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,356 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,360 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-27 12:18:34,360 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-27 12:18:34,361 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-27 12:18:34,361 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-27 12:18:34,361 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (1/1) ... [2022-04-27 12:18:34,374 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-27 12:18:34,380 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 12:18:34,388 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-27 12:18:34,390 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-27 12:18:34,413 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-27 12:18:34,413 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-27 12:18:34,413 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-27 12:18:34,413 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-27 12:18:34,413 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-27 12:18:34,414 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-27 12:18:34,414 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-27 12:18:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-27 12:18:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-27 12:18:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-27 12:18:34,415 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-27 12:18:34,463 INFO L234 CfgBuilder]: Building ICFG [2022-04-27 12:18:34,465 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-27 12:18:34,612 INFO L275 CfgBuilder]: Performing block encoding [2022-04-27 12:18:34,618 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-27 12:18:34,618 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-27 12:18:34,624 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.04 12:18:34 BoogieIcfgContainer [2022-04-27 12:18:34,624 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-27 12:18:34,625 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-27 12:18:34,626 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-27 12:18:34,628 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-27 12:18:34,628 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 27.04 12:18:34" (1/3) ... [2022-04-27 12:18:34,629 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8da38a7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.04 12:18:34, skipping insertion in model container [2022-04-27 12:18:34,629 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 27.04 12:18:34" (2/3) ... [2022-04-27 12:18:34,629 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8da38a7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 27.04 12:18:34, skipping insertion in model container [2022-04-27 12:18:34,629 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 27.04 12:18:34" (3/3) ... [2022-04-27 12:18:34,630 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_valuebound5.c [2022-04-27 12:18:34,640 INFO L201 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-27 12:18:34,640 INFO L160 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-27 12:18:34,677 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-27 12:18:34,682 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@24e9aff2, mLbeIndependenceSettings=de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings@22ed0669 [2022-04-27 12:18:34,682 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-27 12:18:34,694 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-27 12:18:34,699 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-27 12:18:34,700 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 12:18:34,703 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 12:18:34,704 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 12:18:34,708 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 12:18:34,708 INFO L85 PathProgramCache]: Analyzing trace with hash 223850557, now seen corresponding path program 1 times [2022-04-27 12:18:34,716 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 12:18:34,716 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1968680638] [2022-04-27 12:18:34,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:18:34,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 12:18:34,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:34,853 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-27 12:18:34,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:34,870 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-27 12:18:34,870 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-27 12:18:34,871 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-27 12:18:34,871 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-27 12:18:34,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:34,878 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-27 12:18:34,879 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-27 12:18:34,879 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-27 12:18:34,880 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-27 12:18:34,880 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-27 12:18:34,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:34,887 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-27 12:18:34,887 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-27 12:18:34,887 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-27 12:18:34,888 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-27 12:18:34,889 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-27 12:18:34,889 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-27 12:18:34,889 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-27 12:18:34,889 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-27 12:18:34,890 INFO L272 TraceCheckUtils]: 4: Hoare triple {41#true} call #t~ret5 := main(); {41#true} is VALID [2022-04-27 12:18:34,890 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-27 12:18:34,890 INFO L272 TraceCheckUtils]: 6: Hoare triple {41#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 5 then 1 else 0)); {41#true} is VALID [2022-04-27 12:18:34,890 INFO L290 TraceCheckUtils]: 7: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-27 12:18:34,891 INFO L290 TraceCheckUtils]: 8: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-27 12:18:34,891 INFO L290 TraceCheckUtils]: 9: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-27 12:18:34,891 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-27 12:18:34,891 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-27 12:18:34,891 INFO L290 TraceCheckUtils]: 12: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-27 12:18:34,892 INFO L290 TraceCheckUtils]: 13: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-27 12:18:34,892 INFO L290 TraceCheckUtils]: 14: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-27 12:18:34,892 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-27 12:18:34,893 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-27 12:18:34,893 INFO L290 TraceCheckUtils]: 17: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-27 12:18:34,893 INFO L290 TraceCheckUtils]: 18: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-27 12:18:34,893 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-27 12:18:34,893 INFO L290 TraceCheckUtils]: 20: Hoare triple {42#false} ~cond := #in~cond; {42#false} is VALID [2022-04-27 12:18:34,894 INFO L290 TraceCheckUtils]: 21: Hoare triple {42#false} assume 0 == ~cond; {42#false} is VALID [2022-04-27 12:18:34,894 INFO L290 TraceCheckUtils]: 22: Hoare triple {42#false} assume !false; {42#false} is VALID [2022-04-27 12:18:34,894 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-27 12:18:34,895 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 12:18:34,895 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1968680638] [2022-04-27 12:18:34,895 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1968680638] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-27 12:18:34,896 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-27 12:18:34,896 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-27 12:18:34,897 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1656487630] [2022-04-27 12:18:34,898 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 12:18:34,902 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-27 12:18:34,903 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 12:18:34,906 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-27 12:18:34,932 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-27 12:18:34,932 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-27 12:18:34,933 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 12:18:34,963 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-27 12:18:34,963 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-27 12:18:34,965 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-27 12:18:42,408 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-27 12:18:43,390 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:18:43,390 INFO L93 Difference]: Finished difference Result 69 states and 113 transitions. [2022-04-27 12:18:43,390 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-27 12:18:43,391 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-27 12:18:43,391 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 12:18:43,392 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-27 12:18:43,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-27 12:18:43,401 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-27 12:18:43,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-27 12:18:43,410 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 113 transitions. [2022-04-27 12:18:43,552 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-27 12:18:43,563 INFO L225 Difference]: With dead ends: 69 [2022-04-27 12:18:43,563 INFO L226 Difference]: Without dead ends: 33 [2022-04-27 12:18:43,566 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-27 12:18:43,569 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 13 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2022-04-27 12:18:43,570 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 42 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 11 Invalid, 1 Unknown, 0 Unchecked, 2.2s Time] [2022-04-27 12:18:43,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-27 12:18:43,596 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-27 12:18:43,596 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 12:18:43,597 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-27 12:18:43,598 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-27 12:18:43,599 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-27 12:18:43,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:18:43,612 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-27 12:18:43,613 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-27 12:18:43,613 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:18:43,614 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:18:43,614 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-27 12:18:43,614 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-27 12:18:43,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:18:43,619 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-27 12:18:43,619 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-27 12:18:43,626 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:18:43,626 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:18:43,626 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 12:18:43,626 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 12:18:43,627 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-27 12:18:43,630 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2022-04-27 12:18:43,632 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 23 [2022-04-27 12:18:43,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 12:18:43,632 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2022-04-27 12:18:43,632 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-27 12:18:43,632 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-27 12:18:43,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-27 12:18:43,633 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 12:18:43,633 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 12:18:43,634 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-27 12:18:43,634 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 12:18:43,635 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 12:18:43,635 INFO L85 PathProgramCache]: Analyzing trace with hash -563604624, now seen corresponding path program 1 times [2022-04-27 12:18:43,635 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 12:18:43,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1400265040] [2022-04-27 12:18:43,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:18:43,635 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 12:18:43,690 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:43,894 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-27 12:18:43,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:43,914 INFO L290 TraceCheckUtils]: 0: Hoare triple {291#(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); {274#true} is VALID [2022-04-27 12:18:43,914 INFO L290 TraceCheckUtils]: 1: Hoare triple {274#true} assume true; {274#true} is VALID [2022-04-27 12:18:43,914 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {274#true} {274#true} #103#return; {274#true} is VALID [2022-04-27 12:18:43,914 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-27 12:18:43,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:43,936 INFO L290 TraceCheckUtils]: 0: Hoare triple {274#true} ~cond := #in~cond; {274#true} is VALID [2022-04-27 12:18:43,937 INFO L290 TraceCheckUtils]: 1: Hoare triple {274#true} assume !(0 == ~cond); {274#true} is VALID [2022-04-27 12:18:43,937 INFO L290 TraceCheckUtils]: 2: Hoare triple {274#true} assume true; {274#true} is VALID [2022-04-27 12:18:43,937 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {274#true} {274#true} #81#return; {274#true} is VALID [2022-04-27 12:18:43,937 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-27 12:18:43,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:18:43,944 INFO L290 TraceCheckUtils]: 0: Hoare triple {274#true} ~cond := #in~cond; {274#true} is VALID [2022-04-27 12:18:43,944 INFO L290 TraceCheckUtils]: 1: Hoare triple {274#true} assume !(0 == ~cond); {274#true} is VALID [2022-04-27 12:18:43,944 INFO L290 TraceCheckUtils]: 2: Hoare triple {274#true} assume true; {274#true} is VALID [2022-04-27 12:18:43,944 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {274#true} {274#true} #83#return; {274#true} is VALID [2022-04-27 12:18:43,968 INFO L272 TraceCheckUtils]: 0: Hoare triple {274#true} call ULTIMATE.init(); {291#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-27 12:18:43,968 INFO L290 TraceCheckUtils]: 1: Hoare triple {291#(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); {274#true} is VALID [2022-04-27 12:18:43,968 INFO L290 TraceCheckUtils]: 2: Hoare triple {274#true} assume true; {274#true} is VALID [2022-04-27 12:18:43,972 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {274#true} {274#true} #103#return; {274#true} is VALID [2022-04-27 12:18:43,972 INFO L272 TraceCheckUtils]: 4: Hoare triple {274#true} call #t~ret5 := main(); {274#true} is VALID [2022-04-27 12:18:43,973 INFO L290 TraceCheckUtils]: 5: Hoare triple {274#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {274#true} is VALID [2022-04-27 12:18:43,973 INFO L272 TraceCheckUtils]: 6: Hoare triple {274#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 5 then 1 else 0)); {274#true} is VALID [2022-04-27 12:18:43,975 INFO L290 TraceCheckUtils]: 7: Hoare triple {274#true} ~cond := #in~cond; {274#true} is VALID [2022-04-27 12:18:43,975 INFO L290 TraceCheckUtils]: 8: Hoare triple {274#true} assume !(0 == ~cond); {274#true} is VALID [2022-04-27 12:18:43,976 INFO L290 TraceCheckUtils]: 9: Hoare triple {274#true} assume true; {274#true} is VALID [2022-04-27 12:18:43,976 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {274#true} {274#true} #81#return; {274#true} is VALID [2022-04-27 12:18:43,976 INFO L272 TraceCheckUtils]: 11: Hoare triple {274#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {274#true} is VALID [2022-04-27 12:18:43,976 INFO L290 TraceCheckUtils]: 12: Hoare triple {274#true} ~cond := #in~cond; {274#true} is VALID [2022-04-27 12:18:43,977 INFO L290 TraceCheckUtils]: 13: Hoare triple {274#true} assume !(0 == ~cond); {274#true} is VALID [2022-04-27 12:18:43,977 INFO L290 TraceCheckUtils]: 14: Hoare triple {274#true} assume true; {274#true} is VALID [2022-04-27 12:18:43,977 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {274#true} {274#true} #83#return; {274#true} is VALID [2022-04-27 12:18:43,978 INFO L290 TraceCheckUtils]: 16: Hoare triple {274#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {287#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-27 12:18:43,979 INFO L290 TraceCheckUtils]: 17: Hoare triple {287#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !false; {287#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-27 12:18:43,981 INFO L290 TraceCheckUtils]: 18: Hoare triple {287#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {288#(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-27 12:18:43,982 INFO L290 TraceCheckUtils]: 19: Hoare triple {288#(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; {288#(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-27 12:18:43,983 INFO L272 TraceCheckUtils]: 20: Hoare triple {288#(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)); {289#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-27 12:18:43,983 INFO L290 TraceCheckUtils]: 21: Hoare triple {289#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {290#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-27 12:18:43,984 INFO L290 TraceCheckUtils]: 22: Hoare triple {290#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {275#false} is VALID [2022-04-27 12:18:43,984 INFO L290 TraceCheckUtils]: 23: Hoare triple {275#false} assume !false; {275#false} is VALID [2022-04-27 12:18:43,986 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-27 12:18:43,986 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 12:18:43,986 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1400265040] [2022-04-27 12:18:43,987 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1400265040] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-27 12:18:43,987 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-27 12:18:43,987 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-27 12:18:43,987 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1812009285] [2022-04-27 12:18:43,987 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 12:18:43,989 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-27 12:18:43,989 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 12:18:43,990 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-27 12:18:44,017 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-27 12:18:44,018 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-27 12:18:44,021 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 12:18:44,022 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-27 12:18:44,023 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-27 12:18:44,023 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-27 12:18:47,196 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-27 12:18:49,281 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-27 12:18:51,963 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-27 12:19:04,684 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-27 12:19:06,717 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-27 12:19:07,839 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-27 12:19:13,551 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-27 12:19:16,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-27 12:19:18,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:18,996 INFO L93 Difference]: Finished difference Result 46 states and 61 transitions. [2022-04-27 12:19:18,996 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-27 12:19:18,996 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-27 12:19:18,996 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 12:19:18,996 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-27 12:19:18,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 61 transitions. [2022-04-27 12:19:19,000 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-27 12:19:19,002 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 61 transitions. [2022-04-27 12:19:19,002 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 61 transitions. [2022-04-27 12:19:19,263 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 61 edges. 61 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 12:19:19,265 INFO L225 Difference]: With dead ends: 46 [2022-04-27 12:19:19,265 INFO L226 Difference]: Without dead ends: 44 [2022-04-27 12:19:19,265 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-27 12:19:19,266 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 32 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 175 mSolverCounterSat, 25 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 20.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 55 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 175 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.9s IncrementalHoareTripleChecker+Time [2022-04-27 12:19:19,267 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 55 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 175 Invalid, 7 Unknown, 0 Unchecked, 20.9s Time] [2022-04-27 12:19:19,267 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-27 12:19:19,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 42. [2022-04-27 12:19:19,286 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 12:19:19,286 INFO L82 GeneralOperation]: Start isEquivalent. First operand 44 states. Second operand has 42 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-27 12:19:19,288 INFO L74 IsIncluded]: Start isIncluded. First operand 44 states. Second operand has 42 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-27 12:19:19,290 INFO L87 Difference]: Start difference. First operand 44 states. Second operand has 42 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-27 12:19:19,293 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:19,293 INFO L93 Difference]: Finished difference Result 44 states and 59 transitions. [2022-04-27 12:19:19,293 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 59 transitions. [2022-04-27 12:19:19,294 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:19:19,294 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:19:19,295 INFO L74 IsIncluded]: Start isIncluded. First operand has 42 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 44 states. [2022-04-27 12:19:19,298 INFO L87 Difference]: Start difference. First operand has 42 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) Second operand 44 states. [2022-04-27 12:19:19,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:19,307 INFO L93 Difference]: Finished difference Result 44 states and 59 transitions. [2022-04-27 12:19:19,307 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 59 transitions. [2022-04-27 12:19:19,308 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:19:19,308 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:19:19,308 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 12:19:19,308 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 12:19:19,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 24 states have internal predecessors, (27), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-27 12:19:19,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 55 transitions. [2022-04-27 12:19:19,311 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 55 transitions. Word has length 24 [2022-04-27 12:19:19,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 12:19:19,311 INFO L495 AbstractCegarLoop]: Abstraction has 42 states and 55 transitions. [2022-04-27 12:19:19,312 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-27 12:19:19,312 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 55 transitions. [2022-04-27 12:19:19,312 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-27 12:19:19,312 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 12:19:19,312 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 12:19:19,313 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-27 12:19:19,313 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 12:19:19,313 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 12:19:19,313 INFO L85 PathProgramCache]: Analyzing trace with hash -5094773, now seen corresponding path program 1 times [2022-04-27 12:19:19,313 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 12:19:19,313 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1832611958] [2022-04-27 12:19:19,314 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:19:19,314 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 12:19:19,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:19,761 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-27 12:19:19,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:19,786 INFO L290 TraceCheckUtils]: 0: Hoare triple {543#(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); {526#true} is VALID [2022-04-27 12:19:19,786 INFO L290 TraceCheckUtils]: 1: Hoare triple {526#true} assume true; {526#true} is VALID [2022-04-27 12:19:19,787 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {526#true} {526#true} #103#return; {526#true} is VALID [2022-04-27 12:19:19,787 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-27 12:19:19,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:19,797 INFO L290 TraceCheckUtils]: 0: Hoare triple {526#true} ~cond := #in~cond; {526#true} is VALID [2022-04-27 12:19:19,797 INFO L290 TraceCheckUtils]: 1: Hoare triple {526#true} assume !(0 == ~cond); {526#true} is VALID [2022-04-27 12:19:19,797 INFO L290 TraceCheckUtils]: 2: Hoare triple {526#true} assume true; {526#true} is VALID [2022-04-27 12:19:19,797 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {526#true} {526#true} #81#return; {526#true} is VALID [2022-04-27 12:19:19,798 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-27 12:19:19,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:19,806 INFO L290 TraceCheckUtils]: 0: Hoare triple {526#true} ~cond := #in~cond; {526#true} is VALID [2022-04-27 12:19:19,806 INFO L290 TraceCheckUtils]: 1: Hoare triple {526#true} assume !(0 == ~cond); {526#true} is VALID [2022-04-27 12:19:19,807 INFO L290 TraceCheckUtils]: 2: Hoare triple {526#true} assume true; {526#true} is VALID [2022-04-27 12:19:19,807 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {526#true} {526#true} #83#return; {526#true} is VALID [2022-04-27 12:19:19,808 INFO L272 TraceCheckUtils]: 0: Hoare triple {526#true} call ULTIMATE.init(); {543#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-27 12:19:19,808 INFO L290 TraceCheckUtils]: 1: Hoare triple {543#(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); {526#true} is VALID [2022-04-27 12:19:19,808 INFO L290 TraceCheckUtils]: 2: Hoare triple {526#true} assume true; {526#true} is VALID [2022-04-27 12:19:19,808 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {526#true} {526#true} #103#return; {526#true} is VALID [2022-04-27 12:19:19,808 INFO L272 TraceCheckUtils]: 4: Hoare triple {526#true} call #t~ret5 := main(); {526#true} is VALID [2022-04-27 12:19:19,808 INFO L290 TraceCheckUtils]: 5: Hoare triple {526#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {526#true} is VALID [2022-04-27 12:19:19,808 INFO L272 TraceCheckUtils]: 6: Hoare triple {526#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 5 then 1 else 0)); {526#true} is VALID [2022-04-27 12:19:19,809 INFO L290 TraceCheckUtils]: 7: Hoare triple {526#true} ~cond := #in~cond; {526#true} is VALID [2022-04-27 12:19:19,809 INFO L290 TraceCheckUtils]: 8: Hoare triple {526#true} assume !(0 == ~cond); {526#true} is VALID [2022-04-27 12:19:19,809 INFO L290 TraceCheckUtils]: 9: Hoare triple {526#true} assume true; {526#true} is VALID [2022-04-27 12:19:19,810 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {526#true} {526#true} #81#return; {526#true} is VALID [2022-04-27 12:19:19,810 INFO L272 TraceCheckUtils]: 11: Hoare triple {526#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {526#true} is VALID [2022-04-27 12:19:19,810 INFO L290 TraceCheckUtils]: 12: Hoare triple {526#true} ~cond := #in~cond; {526#true} is VALID [2022-04-27 12:19:19,810 INFO L290 TraceCheckUtils]: 13: Hoare triple {526#true} assume !(0 == ~cond); {526#true} is VALID [2022-04-27 12:19:19,810 INFO L290 TraceCheckUtils]: 14: Hoare triple {526#true} assume true; {526#true} is VALID [2022-04-27 12:19:19,810 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {526#true} {526#true} #83#return; {526#true} is VALID [2022-04-27 12:19:19,811 INFO L290 TraceCheckUtils]: 16: Hoare triple {526#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-27 12:19:19,811 INFO L290 TraceCheckUtils]: 17: Hoare triple {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-27 12:19:19,812 INFO L290 TraceCheckUtils]: 18: Hoare triple {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-27 12:19:19,812 INFO L290 TraceCheckUtils]: 19: Hoare triple {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-27 12:19:19,815 INFO L290 TraceCheckUtils]: 20: Hoare triple {539#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {540#(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-27 12:19:19,816 INFO L290 TraceCheckUtils]: 21: Hoare triple {540#(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; {540#(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-27 12:19:19,817 INFO L272 TraceCheckUtils]: 22: Hoare triple {540#(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)); {541#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-27 12:19:19,817 INFO L290 TraceCheckUtils]: 23: Hoare triple {541#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {542#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-27 12:19:19,818 INFO L290 TraceCheckUtils]: 24: Hoare triple {542#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {527#false} is VALID [2022-04-27 12:19:19,818 INFO L290 TraceCheckUtils]: 25: Hoare triple {527#false} assume !false; {527#false} is VALID [2022-04-27 12:19:19,819 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-27 12:19:19,819 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 12:19:19,819 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1832611958] [2022-04-27 12:19:19,819 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1832611958] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-27 12:19:19,819 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-27 12:19:19,819 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-27 12:19:19,820 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [50089903] [2022-04-27 12:19:19,820 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 12:19:19,821 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-27 12:19:19,821 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 12:19:19,821 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-27 12:19:19,837 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-27 12:19:19,837 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-27 12:19:19,838 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 12:19:19,839 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-27 12:19:19,839 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-27 12:19:19,840 INFO L87 Difference]: Start difference. First operand 42 states and 55 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-27 12:19:26,186 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-27 12:19:28,512 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-27 12:19:30,207 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.61s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-27 12:19:39,112 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:39,113 INFO L93 Difference]: Finished difference Result 71 states and 102 transitions. [2022-04-27 12:19:39,113 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-27 12:19:39,113 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-27 12:19:39,113 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 12:19:39,113 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-27 12:19:39,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 91 transitions. [2022-04-27 12:19:39,117 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-27 12:19:39,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 91 transitions. [2022-04-27 12:19:39,120 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 91 transitions. [2022-04-27 12:19:39,659 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 91 edges. 91 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 12:19:39,662 INFO L225 Difference]: With dead ends: 71 [2022-04-27 12:19:39,662 INFO L226 Difference]: Without dead ends: 65 [2022-04-27 12:19:39,663 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-27 12:19:39,664 INFO L413 NwaCegarLoop]: 26 mSDtfsCounter, 37 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 225 mSolverCounterSat, 80 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 307 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Valid, 225 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.0s IncrementalHoareTripleChecker+Time [2022-04-27 12:19:39,664 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 48 Invalid, 307 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 225 Invalid, 2 Unknown, 0 Unchecked, 10.0s Time] [2022-04-27 12:19:39,665 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-04-27 12:19:39,683 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 58. [2022-04-27 12:19:39,683 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 12:19:39,683 INFO L82 GeneralOperation]: Start isEquivalent. First operand 65 states. Second operand has 58 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 33 states have internal predecessors, (36), 23 states have call successors, (23), 6 states have call predecessors, (23), 5 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) [2022-04-27 12:19:39,684 INFO L74 IsIncluded]: Start isIncluded. First operand 65 states. Second operand has 58 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 33 states have internal predecessors, (36), 23 states have call successors, (23), 6 states have call predecessors, (23), 5 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) [2022-04-27 12:19:39,684 INFO L87 Difference]: Start difference. First operand 65 states. Second operand has 58 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 33 states have internal predecessors, (36), 23 states have call successors, (23), 6 states have call predecessors, (23), 5 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) [2022-04-27 12:19:39,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:39,689 INFO L93 Difference]: Finished difference Result 65 states and 92 transitions. [2022-04-27 12:19:39,689 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 92 transitions. [2022-04-27 12:19:39,690 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:19:39,690 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:19:39,691 INFO L74 IsIncluded]: Start isIncluded. First operand has 58 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 33 states have internal predecessors, (36), 23 states have call successors, (23), 6 states have call predecessors, (23), 5 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) Second operand 65 states. [2022-04-27 12:19:39,691 INFO L87 Difference]: Start difference. First operand has 58 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 33 states have internal predecessors, (36), 23 states have call successors, (23), 6 states have call predecessors, (23), 5 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) Second operand 65 states. [2022-04-27 12:19:39,695 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:39,695 INFO L93 Difference]: Finished difference Result 65 states and 92 transitions. [2022-04-27 12:19:39,695 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 92 transitions. [2022-04-27 12:19:39,696 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:19:39,697 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:19:39,697 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 12:19:39,697 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 12:19:39,697 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 29 states have (on average 1.2413793103448276) internal successors, (36), 33 states have internal predecessors, (36), 23 states have call successors, (23), 6 states have call predecessors, (23), 5 states have return successors, (20), 18 states have call predecessors, (20), 20 states have call successors, (20) [2022-04-27 12:19:39,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 79 transitions. [2022-04-27 12:19:39,700 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 79 transitions. Word has length 26 [2022-04-27 12:19:39,700 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 12:19:39,700 INFO L495 AbstractCegarLoop]: Abstraction has 58 states and 79 transitions. [2022-04-27 12:19:39,700 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-27 12:19:39,701 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 79 transitions. [2022-04-27 12:19:39,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-27 12:19:39,701 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 12:19:39,701 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 12:19:39,702 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-27 12:19:39,702 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 12:19:39,702 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 12:19:39,702 INFO L85 PathProgramCache]: Analyzing trace with hash -2000886032, now seen corresponding path program 1 times [2022-04-27 12:19:39,702 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 12:19:39,703 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1748257848] [2022-04-27 12:19:39,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:19:39,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 12:19:39,716 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 12:19:39,717 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [68425919] [2022-04-27 12:19:39,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:19:39,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 12:19:39,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 12:19:39,727 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-27 12:19:39,750 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-27 12:19:39,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:39,860 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-27 12:19:39,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:39,879 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 12:19:40,238 INFO L272 TraceCheckUtils]: 0: Hoare triple {887#true} call ULTIMATE.init(); {887#true} is VALID [2022-04-27 12:19:40,238 INFO L290 TraceCheckUtils]: 1: Hoare triple {887#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); {887#true} is VALID [2022-04-27 12:19:40,239 INFO L290 TraceCheckUtils]: 2: Hoare triple {887#true} assume true; {887#true} is VALID [2022-04-27 12:19:40,239 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {887#true} {887#true} #103#return; {887#true} is VALID [2022-04-27 12:19:40,239 INFO L272 TraceCheckUtils]: 4: Hoare triple {887#true} call #t~ret5 := main(); {887#true} is VALID [2022-04-27 12:19:40,239 INFO L290 TraceCheckUtils]: 5: Hoare triple {887#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {887#true} is VALID [2022-04-27 12:19:40,239 INFO L272 TraceCheckUtils]: 6: Hoare triple {887#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 5 then 1 else 0)); {887#true} is VALID [2022-04-27 12:19:40,239 INFO L290 TraceCheckUtils]: 7: Hoare triple {887#true} ~cond := #in~cond; {887#true} is VALID [2022-04-27 12:19:40,239 INFO L290 TraceCheckUtils]: 8: Hoare triple {887#true} assume !(0 == ~cond); {887#true} is VALID [2022-04-27 12:19:40,240 INFO L290 TraceCheckUtils]: 9: Hoare triple {887#true} assume true; {887#true} is VALID [2022-04-27 12:19:40,240 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {887#true} {887#true} #81#return; {887#true} is VALID [2022-04-27 12:19:40,240 INFO L272 TraceCheckUtils]: 11: Hoare triple {887#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {887#true} is VALID [2022-04-27 12:19:40,240 INFO L290 TraceCheckUtils]: 12: Hoare triple {887#true} ~cond := #in~cond; {887#true} is VALID [2022-04-27 12:19:40,240 INFO L290 TraceCheckUtils]: 13: Hoare triple {887#true} assume !(0 == ~cond); {887#true} is VALID [2022-04-27 12:19:40,240 INFO L290 TraceCheckUtils]: 14: Hoare triple {887#true} assume true; {887#true} is VALID [2022-04-27 12:19:40,240 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {887#true} {887#true} #83#return; {887#true} is VALID [2022-04-27 12:19:40,241 INFO L290 TraceCheckUtils]: 16: Hoare triple {887#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-27 12:19:40,241 INFO L290 TraceCheckUtils]: 17: Hoare triple {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-27 12:19:40,242 INFO L290 TraceCheckUtils]: 18: Hoare triple {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-27 12:19:40,242 INFO L290 TraceCheckUtils]: 19: Hoare triple {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-27 12:19:40,242 INFO L272 TraceCheckUtils]: 20: Hoare triple {940#(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)); {887#true} is VALID [2022-04-27 12:19:40,243 INFO L290 TraceCheckUtils]: 21: Hoare triple {887#true} ~cond := #in~cond; {887#true} is VALID [2022-04-27 12:19:40,243 INFO L290 TraceCheckUtils]: 22: Hoare triple {887#true} assume !(0 == ~cond); {887#true} is VALID [2022-04-27 12:19:40,243 INFO L290 TraceCheckUtils]: 23: Hoare triple {887#true} assume true; {887#true} is VALID [2022-04-27 12:19:40,243 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {887#true} {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #85#return; {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-27 12:19:40,244 INFO L272 TraceCheckUtils]: 25: Hoare triple {940#(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)); {887#true} is VALID [2022-04-27 12:19:40,244 INFO L290 TraceCheckUtils]: 26: Hoare triple {887#true} ~cond := #in~cond; {887#true} is VALID [2022-04-27 12:19:40,244 INFO L290 TraceCheckUtils]: 27: Hoare triple {887#true} assume !(0 == ~cond); {887#true} is VALID [2022-04-27 12:19:40,244 INFO L290 TraceCheckUtils]: 28: Hoare triple {887#true} assume true; {887#true} is VALID [2022-04-27 12:19:40,245 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {887#true} {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #87#return; {940#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-27 12:19:40,246 INFO L272 TraceCheckUtils]: 30: Hoare triple {940#(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)); {983#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 12:19:40,246 INFO L290 TraceCheckUtils]: 31: Hoare triple {983#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {987#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 12:19:40,246 INFO L290 TraceCheckUtils]: 32: Hoare triple {987#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {888#false} is VALID [2022-04-27 12:19:40,247 INFO L290 TraceCheckUtils]: 33: Hoare triple {888#false} assume !false; {888#false} is VALID [2022-04-27 12:19:40,247 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-27 12:19:40,247 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-27 12:19:40,247 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 12:19:40,247 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1748257848] [2022-04-27 12:19:40,248 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 12:19:40,248 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [68425919] [2022-04-27 12:19:40,248 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [68425919] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-27 12:19:40,248 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-27 12:19:40,248 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-27 12:19:40,248 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1253905241] [2022-04-27 12:19:40,248 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 12:19:40,249 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-27 12:19:40,249 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 12:19:40,249 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-27 12:19:40,298 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-27 12:19:40,298 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-27 12:19:40,298 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 12:19:40,299 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-27 12:19:40,299 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-27 12:19:40,299 INFO L87 Difference]: Start difference. First operand 58 states and 79 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-27 12:19:47,618 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-27 12:19:49,608 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:49,609 INFO L93 Difference]: Finished difference Result 104 states and 145 transitions. [2022-04-27 12:19:49,609 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-27 12:19:49,609 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-27 12:19:49,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 12:19:49,609 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-27 12:19:49,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 94 transitions. [2022-04-27 12:19:49,612 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-27 12:19:49,613 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 94 transitions. [2022-04-27 12:19:49,613 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 94 transitions. [2022-04-27 12:19:49,723 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 94 edges. 94 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-27 12:19:49,725 INFO L225 Difference]: With dead ends: 104 [2022-04-27 12:19:49,725 INFO L226 Difference]: Without dead ends: 51 [2022-04-27 12:19:49,726 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-27 12:19:49,727 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 6 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 3 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2022-04-27 12:19:49,727 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 144 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 54 Invalid, 1 Unknown, 0 Unchecked, 2.8s Time] [2022-04-27 12:19:49,728 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-04-27 12:19:49,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2022-04-27 12:19:49,766 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 12:19:49,767 INFO L82 GeneralOperation]: Start isEquivalent. First operand 51 states. Second operand has 51 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 21 states have call successors, (21), 5 states have call predecessors, (21), 4 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-27 12:19:49,767 INFO L74 IsIncluded]: Start isIncluded. First operand 51 states. Second operand has 51 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 21 states have call successors, (21), 5 states have call predecessors, (21), 4 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-27 12:19:49,767 INFO L87 Difference]: Start difference. First operand 51 states. Second operand has 51 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 21 states have call successors, (21), 5 states have call predecessors, (21), 4 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-27 12:19:49,770 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:49,770 INFO L93 Difference]: Finished difference Result 51 states and 70 transitions. [2022-04-27 12:19:49,770 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 70 transitions. [2022-04-27 12:19:49,771 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:19:49,771 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:19:49,771 INFO L74 IsIncluded]: Start isIncluded. First operand has 51 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 21 states have call successors, (21), 5 states have call predecessors, (21), 4 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) Second operand 51 states. [2022-04-27 12:19:49,771 INFO L87 Difference]: Start difference. First operand has 51 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 21 states have call successors, (21), 5 states have call predecessors, (21), 4 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) Second operand 51 states. [2022-04-27 12:19:49,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:19:49,774 INFO L93 Difference]: Finished difference Result 51 states and 70 transitions. [2022-04-27 12:19:49,774 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 70 transitions. [2022-04-27 12:19:49,774 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:19:49,774 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:19:49,774 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 12:19:49,774 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 12:19:49,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 21 states have call successors, (21), 5 states have call predecessors, (21), 4 states have return successors, (18), 17 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-27 12:19:49,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 70 transitions. [2022-04-27 12:19:49,784 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 70 transitions. Word has length 34 [2022-04-27 12:19:49,787 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 12:19:49,787 INFO L495 AbstractCegarLoop]: Abstraction has 51 states and 70 transitions. [2022-04-27 12:19:49,788 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-27 12:19:49,788 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 70 transitions. [2022-04-27 12:19:49,794 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-27 12:19:49,798 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 12:19:49,799 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 12:19:49,819 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-27 12:19:50,009 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 12:19:50,010 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 12:19:50,010 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 12:19:50,010 INFO L85 PathProgramCache]: Analyzing trace with hash -965267381, now seen corresponding path program 1 times [2022-04-27 12:19:50,010 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 12:19:50,010 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2092176171] [2022-04-27 12:19:50,010 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:19:50,010 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 12:19:50,025 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 12:19:50,025 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [633225944] [2022-04-27 12:19:50,025 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:19:50,026 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 12:19:50,026 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 12:19:50,037 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-27 12:19:50,039 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-27 12:19:50,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:50,124 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-27 12:19:50,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-27 12:19:50,134 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-27 12:19:50,316 INFO L272 TraceCheckUtils]: 0: Hoare triple {1336#true} call ULTIMATE.init(); {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L290 TraceCheckUtils]: 1: Hoare triple {1336#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); {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L290 TraceCheckUtils]: 2: Hoare triple {1336#true} assume true; {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1336#true} {1336#true} #103#return; {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L272 TraceCheckUtils]: 4: Hoare triple {1336#true} call #t~ret5 := main(); {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L290 TraceCheckUtils]: 5: Hoare triple {1336#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L272 TraceCheckUtils]: 6: Hoare triple {1336#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 5 then 1 else 0)); {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L290 TraceCheckUtils]: 7: Hoare triple {1336#true} ~cond := #in~cond; {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L290 TraceCheckUtils]: 8: Hoare triple {1336#true} assume !(0 == ~cond); {1336#true} is VALID [2022-04-27 12:19:50,317 INFO L290 TraceCheckUtils]: 9: Hoare triple {1336#true} assume true; {1336#true} is VALID [2022-04-27 12:19:50,318 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1336#true} {1336#true} #81#return; {1336#true} is VALID [2022-04-27 12:19:50,318 INFO L272 TraceCheckUtils]: 11: Hoare triple {1336#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1336#true} is VALID [2022-04-27 12:19:50,318 INFO L290 TraceCheckUtils]: 12: Hoare triple {1336#true} ~cond := #in~cond; {1336#true} is VALID [2022-04-27 12:19:50,318 INFO L290 TraceCheckUtils]: 13: Hoare triple {1336#true} assume !(0 == ~cond); {1336#true} is VALID [2022-04-27 12:19:50,318 INFO L290 TraceCheckUtils]: 14: Hoare triple {1336#true} assume true; {1336#true} is VALID [2022-04-27 12:19:50,318 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1336#true} {1336#true} #83#return; {1336#true} is VALID [2022-04-27 12:19:50,319 INFO L290 TraceCheckUtils]: 16: Hoare triple {1336#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,319 INFO L290 TraceCheckUtils]: 17: Hoare triple {1389#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,319 INFO L290 TraceCheckUtils]: 18: Hoare triple {1389#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,320 INFO L290 TraceCheckUtils]: 19: Hoare triple {1389#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,320 INFO L290 TraceCheckUtils]: 20: Hoare triple {1389#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,321 INFO L290 TraceCheckUtils]: 21: Hoare triple {1389#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,321 INFO L272 TraceCheckUtils]: 22: Hoare triple {1389#(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)); {1336#true} is VALID [2022-04-27 12:19:50,321 INFO L290 TraceCheckUtils]: 23: Hoare triple {1336#true} ~cond := #in~cond; {1336#true} is VALID [2022-04-27 12:19:50,321 INFO L290 TraceCheckUtils]: 24: Hoare triple {1336#true} assume !(0 == ~cond); {1336#true} is VALID [2022-04-27 12:19:50,321 INFO L290 TraceCheckUtils]: 25: Hoare triple {1336#true} assume true; {1336#true} is VALID [2022-04-27 12:19:50,322 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {1336#true} {1389#(and (= main_~p~0 0) (= main_~h~0 0))} #85#return; {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,322 INFO L272 TraceCheckUtils]: 27: Hoare triple {1389#(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)); {1336#true} is VALID [2022-04-27 12:19:50,322 INFO L290 TraceCheckUtils]: 28: Hoare triple {1336#true} ~cond := #in~cond; {1336#true} is VALID [2022-04-27 12:19:50,322 INFO L290 TraceCheckUtils]: 29: Hoare triple {1336#true} assume !(0 == ~cond); {1336#true} is VALID [2022-04-27 12:19:50,322 INFO L290 TraceCheckUtils]: 30: Hoare triple {1336#true} assume true; {1336#true} is VALID [2022-04-27 12:19:50,323 INFO L284 TraceCheckUtils]: 31: Hoare quadruple {1336#true} {1389#(and (= main_~p~0 0) (= main_~h~0 0))} #87#return; {1389#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-27 12:19:50,324 INFO L272 TraceCheckUtils]: 32: Hoare triple {1389#(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)); {1438#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-27 12:19:50,325 INFO L290 TraceCheckUtils]: 33: Hoare triple {1438#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1442#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-27 12:19:50,340 INFO L290 TraceCheckUtils]: 34: Hoare triple {1442#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1337#false} is VALID [2022-04-27 12:19:50,342 INFO L290 TraceCheckUtils]: 35: Hoare triple {1337#false} assume !false; {1337#false} is VALID [2022-04-27 12:19:50,343 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-27 12:19:50,343 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-27 12:19:50,343 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-27 12:19:50,343 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2092176171] [2022-04-27 12:19:50,343 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-27 12:19:50,344 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [633225944] [2022-04-27 12:19:50,344 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [633225944] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-27 12:19:50,344 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-27 12:19:50,344 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-27 12:19:50,344 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1826777234] [2022-04-27 12:19:50,344 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-27 12:19:50,345 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-27 12:19:50,345 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-27 12:19:50,345 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-27 12:19:50,373 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-27 12:19:50,373 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-27 12:19:50,374 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-27 12:19:50,374 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-27 12:19:50,374 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-27 12:19:50,375 INFO L87 Difference]: Start difference. First operand 51 states and 70 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-27 12:20:01,050 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-27 12:20:01,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:20:01,543 INFO L93 Difference]: Finished difference Result 68 states and 91 transitions. [2022-04-27 12:20:01,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-27 12:20:01,543 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-27 12:20:01,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-27 12:20:01,544 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-27 12:20:01,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-27 12:20:01,545 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-27 12:20:01,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 65 transitions. [2022-04-27 12:20:01,547 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 65 transitions. [2022-04-27 12:20:01,616 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-27 12:20:01,618 INFO L225 Difference]: With dead ends: 68 [2022-04-27 12:20:01,618 INFO L226 Difference]: Without dead ends: 65 [2022-04-27 12:20:01,619 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-27 12:20:01,619 INFO L413 NwaCegarLoop]: 48 mSDtfsCounter, 6 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.0s 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, 3.0s IncrementalHoareTripleChecker+Time [2022-04-27 12:20:01,620 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 150 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 45 Invalid, 1 Unknown, 0 Unchecked, 3.0s Time] [2022-04-27 12:20:01,620 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2022-04-27 12:20:01,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2022-04-27 12:20:01,646 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-27 12:20:01,647 INFO L82 GeneralOperation]: Start isEquivalent. First operand 65 states. Second operand has 65 states, 32 states have (on average 1.1875) internal successors, (38), 34 states have internal predecessors, (38), 26 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-27 12:20:01,648 INFO L74 IsIncluded]: Start isIncluded. First operand 65 states. Second operand has 65 states, 32 states have (on average 1.1875) internal successors, (38), 34 states have internal predecessors, (38), 26 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-27 12:20:01,648 INFO L87 Difference]: Start difference. First operand 65 states. Second operand has 65 states, 32 states have (on average 1.1875) internal successors, (38), 34 states have internal predecessors, (38), 26 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-27 12:20:01,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:20:01,654 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-04-27 12:20:01,654 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 87 transitions. [2022-04-27 12:20:01,656 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:20:01,656 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:20:01,657 INFO L74 IsIncluded]: Start isIncluded. First operand has 65 states, 32 states have (on average 1.1875) internal successors, (38), 34 states have internal predecessors, (38), 26 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand 65 states. [2022-04-27 12:20:01,658 INFO L87 Difference]: Start difference. First operand has 65 states, 32 states have (on average 1.1875) internal successors, (38), 34 states have internal predecessors, (38), 26 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand 65 states. [2022-04-27 12:20:01,662 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-27 12:20:01,663 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2022-04-27 12:20:01,663 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 87 transitions. [2022-04-27 12:20:01,663 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-27 12:20:01,663 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-27 12:20:01,663 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-27 12:20:01,663 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-27 12:20:01,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 32 states have (on average 1.1875) internal successors, (38), 34 states have internal predecessors, (38), 26 states have call successors, (26), 7 states have call predecessors, (26), 6 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-27 12:20:01,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 87 transitions. [2022-04-27 12:20:01,671 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 87 transitions. Word has length 36 [2022-04-27 12:20:01,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-27 12:20:01,673 INFO L495 AbstractCegarLoop]: Abstraction has 65 states and 87 transitions. [2022-04-27 12:20:01,673 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-27 12:20:01,673 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 87 transitions. [2022-04-27 12:20:01,676 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-04-27 12:20:01,676 INFO L187 NwaCegarLoop]: Found error trace [2022-04-27 12:20:01,676 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-27 12:20:01,695 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-27 12:20:01,881 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 12:20:01,881 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-27 12:20:01,881 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-27 12:20:01,881 INFO L85 PathProgramCache]: Analyzing trace with hash 1670386034, now seen corresponding path program 1 times [2022-04-27 12:20:01,882 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-27 12:20:01,882 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1061931559] [2022-04-27 12:20:01,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:20:01,882 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-27 12:20:01,895 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-27 12:20:01,896 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2006978983] [2022-04-27 12:20:01,896 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-27 12:20:01,896 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-27 12:20:01,896 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-27 12:20:01,909 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-27 12:20:01,910 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process