/usr/bin/java -ea -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/lcm1_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-08 13:24:44,084 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-08 13:24:44,085 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-08 13:24:44,125 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-08 13:24:44,125 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-08 13:24:44,126 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-08 13:24:44,129 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-08 13:24:44,131 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-08 13:24:44,132 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-08 13:24:44,135 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-08 13:24:44,136 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-08 13:24:44,137 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-08 13:24:44,137 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-08 13:24:44,137 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-08 13:24:44,138 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-08 13:24:44,138 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-08 13:24:44,139 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-08 13:24:44,139 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-08 13:24:44,140 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-08 13:24:44,141 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-08 13:24:44,142 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-08 13:24:44,144 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-08 13:24:44,145 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-08 13:24:44,148 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-08 13:24:44,149 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-08 13:24:44,155 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-08 13:24:44,155 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-08 13:24:44,155 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-08 13:24:44,155 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-08 13:24:44,156 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-08 13:24:44,157 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-08 13:24:44,157 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-08 13:24:44,158 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-08 13:24:44,158 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-08 13:24:44,159 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-08 13:24:44,159 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-08 13:24:44,159 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-08 13:24:44,160 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-08 13:24:44,160 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-08 13:24:44,160 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-08 13:24:44,161 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-08 13:24:44,162 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-08 13:24:44,163 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-08 13:24:44,171 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-08 13:24:44,171 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-08 13:24:44,172 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-08 13:24:44,172 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-08 13:24:44,172 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-08 13:24:44,172 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-08 13:24:44,172 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-08 13:24:44,172 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-08 13:24:44,173 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-08 13:24:44,173 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-08 13:24:44,173 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-08 13:24:44,173 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 13:24:44,174 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-08 13:24:44,174 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-08 13:24:44,361 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-08 13:24:44,384 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-08 13:24:44,386 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-08 13:24:44,387 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-08 13:24:44,388 INFO L275 PluginConnector]: CDTParser initialized [2022-04-08 13:24:44,389 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/lcm1_unwindbound10.c [2022-04-08 13:24:44,427 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b6424f7b9/c71df9c71f06435187a6dfd60082d96d/FLAGe8f4f71ee [2022-04-08 13:24:44,796 INFO L306 CDTParser]: Found 1 translation units. [2022-04-08 13:24:44,797 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/lcm1_unwindbound10.c [2022-04-08 13:24:44,801 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b6424f7b9/c71df9c71f06435187a6dfd60082d96d/FLAGe8f4f71ee [2022-04-08 13:24:45,217 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b6424f7b9/c71df9c71f06435187a6dfd60082d96d [2022-04-08 13:24:45,219 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-08 13:24:45,219 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-08 13:24:45,220 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-08 13:24:45,221 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-08 13:24:45,222 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-08 13:24:45,223 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,224 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3ad8a205 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45, skipping insertion in model container [2022-04-08 13:24:45,224 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,229 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-08 13:24:45,240 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-08 13:24:45,335 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/lcm1_unwindbound10.c[552,565] [2022-04-08 13:24:45,348 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 13:24:45,354 INFO L203 MainTranslator]: Completed pre-run [2022-04-08 13:24:45,395 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/lcm1_unwindbound10.c[552,565] [2022-04-08 13:24:45,402 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-08 13:24:45,411 INFO L208 MainTranslator]: Completed translation [2022-04-08 13:24:45,412 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45 WrapperNode [2022-04-08 13:24:45,412 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-08 13:24:45,413 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-08 13:24:45,413 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-08 13:24:45,413 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-08 13:24:45,419 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,420 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,424 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,424 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,428 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,431 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,432 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,433 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-08 13:24:45,434 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-08 13:24:45,434 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-08 13:24:45,434 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-08 13:24:45,435 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (1/1) ... [2022-04-08 13:24:45,451 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-08 13:24:45,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 13:24:45,465 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-08 13:24:45,473 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-08 13:24:45,490 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-08 13:24:45,490 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-08 13:24:45,490 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-08 13:24:45,490 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-08 13:24:45,490 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-08 13:24:45,491 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-08 13:24:45,491 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-08 13:24:45,491 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-08 13:24:45,491 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-08 13:24:45,491 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-08 13:24:45,491 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-08 13:24:45,491 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-08 13:24:45,492 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-08 13:24:45,492 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-08 13:24:45,492 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-08 13:24:45,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-08 13:24:45,494 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-08 13:24:45,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-08 13:24:45,494 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-08 13:24:45,494 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-08 13:24:45,540 INFO L234 CfgBuilder]: Building ICFG [2022-04-08 13:24:45,541 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-08 13:24:45,688 INFO L275 CfgBuilder]: Performing block encoding [2022-04-08 13:24:45,693 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-08 13:24:45,693 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2022-04-08 13:24:45,695 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 01:24:45 BoogieIcfgContainer [2022-04-08 13:24:45,695 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-08 13:24:45,696 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-08 13:24:45,696 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-08 13:24:45,709 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-08 13:24:45,709 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.04 01:24:45" (1/3) ... [2022-04-08 13:24:45,710 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@356c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 01:24:45, skipping insertion in model container [2022-04-08 13:24:45,710 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.04 01:24:45" (2/3) ... [2022-04-08 13:24:45,710 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@356c0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.04 01:24:45, skipping insertion in model container [2022-04-08 13:24:45,710 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.04 01:24:45" (3/3) ... [2022-04-08 13:24:45,711 INFO L111 eAbstractionObserver]: Analyzing ICFG lcm1_unwindbound10.c [2022-04-08 13:24:45,715 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-08 13:24:45,715 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-08 13:24:45,749 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-08 13:24:45,754 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-08 13:24:45,754 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-08 13:24:45,767 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 23 states have (on average 1.5217391304347827) internal successors, (35), 24 states have internal predecessors, (35), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-08 13:24:45,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-04-08 13:24:45,772 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 13:24:45,773 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 13:24:45,773 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 13:24:45,777 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 13:24:45,777 INFO L85 PathProgramCache]: Analyzing trace with hash 1515787587, now seen corresponding path program 1 times [2022-04-08 13:24:45,782 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 13:24:45,783 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1717642084] [2022-04-08 13:24:45,790 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 13:24:45,790 INFO L85 PathProgramCache]: Analyzing trace with hash 1515787587, now seen corresponding path program 2 times [2022-04-08 13:24:45,792 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 13:24:45,792 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [963780496] [2022-04-08 13:24:45,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 13:24:45,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 13:24:45,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:45,900 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-08 13:24:45,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:45,915 INFO L290 TraceCheckUtils]: 0: Hoare triple {64#(and (= ~counter~0 |old(~counter~0)|) (= |#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(7, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(109, 2, 2, 1);call write~init~int(49, 2, 3, 1);call write~init~int(46, 2, 4, 1);call write~init~int(99, 2, 5, 1);call write~init~int(0, 2, 6, 1);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {43#true} is VALID [2022-04-08 13:24:45,915 INFO L290 TraceCheckUtils]: 1: Hoare triple {43#true} assume true; {43#true} is VALID [2022-04-08 13:24:45,915 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {43#true} {43#true} #111#return; {43#true} is VALID [2022-04-08 13:24:45,916 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-08 13:24:45,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:45,922 INFO L290 TraceCheckUtils]: 0: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,923 INFO L290 TraceCheckUtils]: 1: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,923 INFO L290 TraceCheckUtils]: 2: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,923 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {44#false} {43#true} #93#return; {44#false} is VALID [2022-04-08 13:24:45,923 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-08 13:24:45,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:45,929 INFO L290 TraceCheckUtils]: 0: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,929 INFO L290 TraceCheckUtils]: 1: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,930 INFO L290 TraceCheckUtils]: 2: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,930 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {44#false} {44#false} #95#return; {44#false} is VALID [2022-04-08 13:24:45,930 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2022-04-08 13:24:45,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:45,936 INFO L290 TraceCheckUtils]: 0: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,936 INFO L290 TraceCheckUtils]: 1: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,936 INFO L290 TraceCheckUtils]: 2: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,937 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {44#false} {44#false} #97#return; {44#false} is VALID [2022-04-08 13:24:45,937 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2022-04-08 13:24:45,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:45,942 INFO L290 TraceCheckUtils]: 0: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,942 INFO L290 TraceCheckUtils]: 1: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,943 INFO L290 TraceCheckUtils]: 2: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,943 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {44#false} {44#false} #99#return; {44#false} is VALID [2022-04-08 13:24:45,944 INFO L272 TraceCheckUtils]: 0: Hoare triple {43#true} call ULTIMATE.init(); {64#(and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-08 13:24:45,944 INFO L290 TraceCheckUtils]: 1: Hoare triple {64#(and (= ~counter~0 |old(~counter~0)|) (= |#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(7, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(109, 2, 2, 1);call write~init~int(49, 2, 3, 1);call write~init~int(46, 2, 4, 1);call write~init~int(99, 2, 5, 1);call write~init~int(0, 2, 6, 1);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {43#true} is VALID [2022-04-08 13:24:45,944 INFO L290 TraceCheckUtils]: 2: Hoare triple {43#true} assume true; {43#true} is VALID [2022-04-08 13:24:45,944 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {43#true} {43#true} #111#return; {43#true} is VALID [2022-04-08 13:24:45,945 INFO L272 TraceCheckUtils]: 4: Hoare triple {43#true} call #t~ret9 := main(); {43#true} is VALID [2022-04-08 13:24:45,945 INFO L290 TraceCheckUtils]: 5: Hoare triple {43#true} havoc ~a~0;havoc ~b~0;havoc ~x~0;havoc ~y~0;havoc ~u~0;havoc ~v~0;~a~0 := #t~nondet4;havoc #t~nondet4;~b~0 := #t~nondet5;havoc #t~nondet5; {43#true} is VALID [2022-04-08 13:24:45,945 INFO L272 TraceCheckUtils]: 6: Hoare triple {43#true} call assume_abort_if_not((if ~a~0 % 4294967296 >= 1 then 1 else 0)); {43#true} is VALID [2022-04-08 13:24:45,945 INFO L290 TraceCheckUtils]: 7: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,946 INFO L290 TraceCheckUtils]: 8: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,946 INFO L290 TraceCheckUtils]: 9: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,946 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {44#false} {43#true} #93#return; {44#false} is VALID [2022-04-08 13:24:45,946 INFO L272 TraceCheckUtils]: 11: Hoare triple {44#false} call assume_abort_if_not((if ~b~0 % 4294967296 >= 1 then 1 else 0)); {43#true} is VALID [2022-04-08 13:24:45,946 INFO L290 TraceCheckUtils]: 12: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,947 INFO L290 TraceCheckUtils]: 13: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,947 INFO L290 TraceCheckUtils]: 14: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,947 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {44#false} {44#false} #95#return; {44#false} is VALID [2022-04-08 13:24:45,947 INFO L272 TraceCheckUtils]: 16: Hoare triple {44#false} call assume_abort_if_not((if ~a~0 % 4294967296 <= 65535 then 1 else 0)); {43#true} is VALID [2022-04-08 13:24:45,947 INFO L290 TraceCheckUtils]: 17: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,948 INFO L290 TraceCheckUtils]: 18: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,948 INFO L290 TraceCheckUtils]: 19: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,948 INFO L284 TraceCheckUtils]: 20: Hoare quadruple {44#false} {44#false} #97#return; {44#false} is VALID [2022-04-08 13:24:45,948 INFO L272 TraceCheckUtils]: 21: Hoare triple {44#false} call assume_abort_if_not((if ~b~0 % 4294967296 <= 65535 then 1 else 0)); {43#true} is VALID [2022-04-08 13:24:45,949 INFO L290 TraceCheckUtils]: 22: Hoare triple {43#true} ~cond := #in~cond; {43#true} is VALID [2022-04-08 13:24:45,949 INFO L290 TraceCheckUtils]: 23: Hoare triple {43#true} assume 0 == ~cond;assume false; {44#false} is VALID [2022-04-08 13:24:45,949 INFO L290 TraceCheckUtils]: 24: Hoare triple {44#false} assume true; {44#false} is VALID [2022-04-08 13:24:45,949 INFO L284 TraceCheckUtils]: 25: Hoare quadruple {44#false} {44#false} #99#return; {44#false} is VALID [2022-04-08 13:24:45,949 INFO L290 TraceCheckUtils]: 26: Hoare triple {44#false} ~x~0 := ~a~0;~y~0 := ~b~0;~u~0 := ~b~0;~v~0 := 0; {44#false} is VALID [2022-04-08 13:24:45,950 INFO L290 TraceCheckUtils]: 27: Hoare triple {44#false} assume !true; {44#false} is VALID [2022-04-08 13:24:45,950 INFO L272 TraceCheckUtils]: 28: Hoare triple {44#false} call __VERIFIER_assert((if (~u~0 * ~y~0 + ~v~0 * ~y~0) % 4294967296 == ~a~0 * ~b~0 % 4294967296 then 1 else 0)); {44#false} is VALID [2022-04-08 13:24:45,950 INFO L290 TraceCheckUtils]: 29: Hoare triple {44#false} ~cond := #in~cond; {44#false} is VALID [2022-04-08 13:24:45,950 INFO L290 TraceCheckUtils]: 30: Hoare triple {44#false} assume 0 == ~cond; {44#false} is VALID [2022-04-08 13:24:45,950 INFO L290 TraceCheckUtils]: 31: Hoare triple {44#false} assume !false; {44#false} is VALID [2022-04-08 13:24:45,951 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-08 13:24:45,951 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 13:24:45,951 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [963780496] [2022-04-08 13:24:45,952 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [963780496] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 13:24:45,952 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 13:24:45,952 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 13:24:45,954 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 13:24:45,954 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1717642084] [2022-04-08 13:24:45,954 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1717642084] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 13:24:45,955 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 13:24:45,955 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-08 13:24:45,955 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [458431239] [2022-04-08 13:24:45,955 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 13:24:45,959 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 32 [2022-04-08 13:24:45,960 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 13:24:45,962 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:45,983 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 23 edges. 23 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:45,983 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-08 13:24:45,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 13:24:45,996 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-08 13:24:45,997 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-08 13:24:45,999 INFO L87 Difference]: Start difference. First operand has 40 states, 23 states have (on average 1.5217391304347827) internal successors, (35), 24 states have internal predecessors, (35), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:46,147 INFO L93 Difference]: Finished difference Result 74 states and 117 transitions. [2022-04-08 13:24:46,147 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-08 13:24:46,147 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 32 [2022-04-08 13:24:46,148 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 13:24:46,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 117 transitions. [2022-04-08 13:24:46,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,166 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 117 transitions. [2022-04-08 13:24:46,166 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 117 transitions. [2022-04-08 13:24:46,276 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 117 edges. 117 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:46,286 INFO L225 Difference]: With dead ends: 74 [2022-04-08 13:24:46,286 INFO L226 Difference]: Without dead ends: 36 [2022-04-08 13:24:46,289 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 15 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-08 13:24:46,293 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 13:24:46,295 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 51 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 13:24:46,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-04-08 13:24:46,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 35. [2022-04-08 13:24:46,323 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 13:24:46,324 INFO L82 GeneralOperation]: Start isEquivalent. First operand 36 states. Second operand has 35 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,325 INFO L74 IsIncluded]: Start isIncluded. First operand 36 states. Second operand has 35 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,326 INFO L87 Difference]: Start difference. First operand 36 states. Second operand has 35 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:46,335 INFO L93 Difference]: Finished difference Result 36 states and 48 transitions. [2022-04-08 13:24:46,335 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 13:24:46,336 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 13:24:46,336 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 13:24:46,337 INFO L74 IsIncluded]: Start isIncluded. First operand has 35 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 36 states. [2022-04-08 13:24:46,338 INFO L87 Difference]: Start difference. First operand has 35 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 36 states. [2022-04-08 13:24:46,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:46,350 INFO L93 Difference]: Finished difference Result 36 states and 48 transitions. [2022-04-08 13:24:46,350 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 48 transitions. [2022-04-08 13:24:46,351 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 13:24:46,351 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 13:24:46,351 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 13:24:46,351 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 13:24:46,352 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 47 transitions. [2022-04-08 13:24:46,354 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 47 transitions. Word has length 32 [2022-04-08 13:24:46,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 13:24:46,354 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 47 transitions. [2022-04-08 13:24:46,354 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,355 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 35 states and 47 transitions. [2022-04-08 13:24:46,399 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 47 edges. 47 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:46,399 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 47 transitions. [2022-04-08 13:24:46,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-08 13:24:46,401 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 13:24:46,401 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 13:24:46,401 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-08 13:24:46,402 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 13:24:46,402 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 13:24:46,402 INFO L85 PathProgramCache]: Analyzing trace with hash 182383832, now seen corresponding path program 1 times [2022-04-08 13:24:46,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 13:24:46,402 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [842294908] [2022-04-08 13:24:46,403 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 13:24:46,403 INFO L85 PathProgramCache]: Analyzing trace with hash 182383832, now seen corresponding path program 2 times [2022-04-08 13:24:46,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 13:24:46,403 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [471236368] [2022-04-08 13:24:46,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 13:24:46,404 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 13:24:46,427 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 13:24:46,427 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1351078592] [2022-04-08 13:24:46,427 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 13:24:46,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 13:24:46,428 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 13:24:46,439 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-08 13:24:46,440 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-08 13:24:46,495 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 13:24:46,495 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 13:24:46,497 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-08 13:24:46,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:46,535 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 13:24:46,718 INFO L272 TraceCheckUtils]: 0: Hoare triple {357#true} call ULTIMATE.init(); {357#true} is VALID [2022-04-08 13:24:46,719 INFO L290 TraceCheckUtils]: 1: Hoare triple {357#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(7, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(109, 2, 2, 1);call write~init~int(49, 2, 3, 1);call write~init~int(46, 2, 4, 1);call write~init~int(99, 2, 5, 1);call write~init~int(0, 2, 6, 1);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,719 INFO L290 TraceCheckUtils]: 2: Hoare triple {365#(<= ~counter~0 0)} assume true; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,720 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {365#(<= ~counter~0 0)} {357#true} #111#return; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,720 INFO L272 TraceCheckUtils]: 4: Hoare triple {365#(<= ~counter~0 0)} call #t~ret9 := main(); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,720 INFO L290 TraceCheckUtils]: 5: Hoare triple {365#(<= ~counter~0 0)} havoc ~a~0;havoc ~b~0;havoc ~x~0;havoc ~y~0;havoc ~u~0;havoc ~v~0;~a~0 := #t~nondet4;havoc #t~nondet4;~b~0 := #t~nondet5;havoc #t~nondet5; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,721 INFO L272 TraceCheckUtils]: 6: Hoare triple {365#(<= ~counter~0 0)} call assume_abort_if_not((if ~a~0 % 4294967296 >= 1 then 1 else 0)); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,721 INFO L290 TraceCheckUtils]: 7: Hoare triple {365#(<= ~counter~0 0)} ~cond := #in~cond; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,722 INFO L290 TraceCheckUtils]: 8: Hoare triple {365#(<= ~counter~0 0)} assume !(0 == ~cond); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,722 INFO L290 TraceCheckUtils]: 9: Hoare triple {365#(<= ~counter~0 0)} assume true; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,722 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {365#(<= ~counter~0 0)} {365#(<= ~counter~0 0)} #93#return; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,723 INFO L272 TraceCheckUtils]: 11: Hoare triple {365#(<= ~counter~0 0)} call assume_abort_if_not((if ~b~0 % 4294967296 >= 1 then 1 else 0)); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,723 INFO L290 TraceCheckUtils]: 12: Hoare triple {365#(<= ~counter~0 0)} ~cond := #in~cond; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,724 INFO L290 TraceCheckUtils]: 13: Hoare triple {365#(<= ~counter~0 0)} assume !(0 == ~cond); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,724 INFO L290 TraceCheckUtils]: 14: Hoare triple {365#(<= ~counter~0 0)} assume true; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,724 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {365#(<= ~counter~0 0)} {365#(<= ~counter~0 0)} #95#return; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,725 INFO L272 TraceCheckUtils]: 16: Hoare triple {365#(<= ~counter~0 0)} call assume_abort_if_not((if ~a~0 % 4294967296 <= 65535 then 1 else 0)); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,725 INFO L290 TraceCheckUtils]: 17: Hoare triple {365#(<= ~counter~0 0)} ~cond := #in~cond; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,726 INFO L290 TraceCheckUtils]: 18: Hoare triple {365#(<= ~counter~0 0)} assume !(0 == ~cond); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,726 INFO L290 TraceCheckUtils]: 19: Hoare triple {365#(<= ~counter~0 0)} assume true; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,727 INFO L284 TraceCheckUtils]: 20: Hoare quadruple {365#(<= ~counter~0 0)} {365#(<= ~counter~0 0)} #97#return; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,727 INFO L272 TraceCheckUtils]: 21: Hoare triple {365#(<= ~counter~0 0)} call assume_abort_if_not((if ~b~0 % 4294967296 <= 65535 then 1 else 0)); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,727 INFO L290 TraceCheckUtils]: 22: Hoare triple {365#(<= ~counter~0 0)} ~cond := #in~cond; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,728 INFO L290 TraceCheckUtils]: 23: Hoare triple {365#(<= ~counter~0 0)} assume !(0 == ~cond); {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,728 INFO L290 TraceCheckUtils]: 24: Hoare triple {365#(<= ~counter~0 0)} assume true; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,729 INFO L284 TraceCheckUtils]: 25: Hoare quadruple {365#(<= ~counter~0 0)} {365#(<= ~counter~0 0)} #99#return; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,729 INFO L290 TraceCheckUtils]: 26: Hoare triple {365#(<= ~counter~0 0)} ~x~0 := ~a~0;~y~0 := ~b~0;~u~0 := ~b~0;~v~0 := 0; {365#(<= ~counter~0 0)} is VALID [2022-04-08 13:24:46,729 INFO L290 TraceCheckUtils]: 27: Hoare triple {365#(<= ~counter~0 0)} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {444#(<= |main_#t~post6| 0)} is VALID [2022-04-08 13:24:46,730 INFO L290 TraceCheckUtils]: 28: Hoare triple {444#(<= |main_#t~post6| 0)} assume !(#t~post6 < 10);havoc #t~post6; {358#false} is VALID [2022-04-08 13:24:46,730 INFO L272 TraceCheckUtils]: 29: Hoare triple {358#false} call __VERIFIER_assert((if (~u~0 * ~y~0 + ~v~0 * ~y~0) % 4294967296 == ~a~0 * ~b~0 % 4294967296 then 1 else 0)); {358#false} is VALID [2022-04-08 13:24:46,730 INFO L290 TraceCheckUtils]: 30: Hoare triple {358#false} ~cond := #in~cond; {358#false} is VALID [2022-04-08 13:24:46,730 INFO L290 TraceCheckUtils]: 31: Hoare triple {358#false} assume 0 == ~cond; {358#false} is VALID [2022-04-08 13:24:46,731 INFO L290 TraceCheckUtils]: 32: Hoare triple {358#false} assume !false; {358#false} is VALID [2022-04-08 13:24:46,731 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-08 13:24:46,731 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 13:24:46,731 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 13:24:46,731 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [471236368] [2022-04-08 13:24:46,731 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 13:24:46,731 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1351078592] [2022-04-08 13:24:46,732 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1351078592] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 13:24:46,732 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 13:24:46,732 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 13:24:46,732 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 13:24:46,733 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [842294908] [2022-04-08 13:24:46,733 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [842294908] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 13:24:46,733 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 13:24:46,733 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-08 13:24:46,733 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [447153779] [2022-04-08 13:24:46,733 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 13:24:46,734 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-08 13:24:46,734 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 13:24:46,734 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,751 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 24 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:46,752 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-08 13:24:46,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 13:24:46,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-08 13:24:46,752 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 13:24:46,753 INFO L87 Difference]: Start difference. First operand 35 states and 47 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,832 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:46,832 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2022-04-08 13:24:46,832 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-08 13:24:46,832 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-08 13:24:46,833 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 13:24:46,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,835 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 58 transitions. [2022-04-08 13:24:46,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 58 transitions. [2022-04-08 13:24:46,836 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 4 states and 58 transitions. [2022-04-08 13:24:46,876 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 58 edges. 58 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:46,878 INFO L225 Difference]: With dead ends: 45 [2022-04-08 13:24:46,878 INFO L226 Difference]: Without dead ends: 37 [2022-04-08 13:24:46,878 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-08 13:24:46,879 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-08 13:24:46,879 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 115 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-08 13:24:46,880 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2022-04-08 13:24:46,890 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2022-04-08 13:24:46,890 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 13:24:46,891 INFO L82 GeneralOperation]: Start isEquivalent. First operand 37 states. Second operand has 37 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,891 INFO L74 IsIncluded]: Start isIncluded. First operand 37 states. Second operand has 37 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,891 INFO L87 Difference]: Start difference. First operand 37 states. Second operand has 37 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:46,893 INFO L93 Difference]: Finished difference Result 37 states and 49 transitions. [2022-04-08 13:24:46,893 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 49 transitions. [2022-04-08 13:24:46,894 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 13:24:46,894 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 13:24:46,894 INFO L74 IsIncluded]: Start isIncluded. First operand has 37 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 37 states. [2022-04-08 13:24:46,894 INFO L87 Difference]: Start difference. First operand has 37 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand 37 states. [2022-04-08 13:24:46,896 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:46,896 INFO L93 Difference]: Finished difference Result 37 states and 49 transitions. [2022-04-08 13:24:46,896 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 49 transitions. [2022-04-08 13:24:46,896 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 13:24:46,896 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 13:24:46,896 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 13:24:46,897 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 13:24:46,897 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-08 13:24:46,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 49 transitions. [2022-04-08 13:24:46,898 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 49 transitions. Word has length 33 [2022-04-08 13:24:46,898 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 13:24:46,898 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 49 transitions. [2022-04-08 13:24:46,899 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-08 13:24:46,899 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 37 states and 49 transitions. [2022-04-08 13:24:46,938 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 49 edges. 49 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:46,938 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 49 transitions. [2022-04-08 13:24:46,939 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-08 13:24:46,939 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 13:24:46,939 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-08 13:24:46,956 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-08 13:24:47,175 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 13:24:47,175 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 13:24:47,176 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 13:24:47,176 INFO L85 PathProgramCache]: Analyzing trace with hash 184052128, now seen corresponding path program 1 times [2022-04-08 13:24:47,176 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 13:24:47,176 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1513794748] [2022-04-08 13:24:47,177 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 13:24:47,179 INFO L85 PathProgramCache]: Analyzing trace with hash 184052128, now seen corresponding path program 2 times [2022-04-08 13:24:47,180 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 13:24:47,180 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484419374] [2022-04-08 13:24:47,180 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 13:24:47,180 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 13:24:47,221 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 13:24:47,221 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2134498087] [2022-04-08 13:24:47,221 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 13:24:47,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 13:24:47,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 13:24:47,231 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-08 13:24:47,232 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-08 13:24:47,287 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-08 13:24:47,288 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-08 13:24:47,289 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-08 13:24:47,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-08 13:24:47,298 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-08 13:24:47,443 INFO L272 TraceCheckUtils]: 0: Hoare triple {697#true} call ULTIMATE.init(); {697#true} is VALID [2022-04-08 13:24:47,443 INFO L290 TraceCheckUtils]: 1: Hoare triple {697#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(7, 2);call write~init~int(108, 2, 0, 1);call write~init~int(99, 2, 1, 1);call write~init~int(109, 2, 2, 1);call write~init~int(49, 2, 3, 1);call write~init~int(46, 2, 4, 1);call write~init~int(99, 2, 5, 1);call write~init~int(0, 2, 6, 1);call #Ultimate.allocInit(12, 3);~counter~0 := 0; {697#true} is VALID [2022-04-08 13:24:47,443 INFO L290 TraceCheckUtils]: 2: Hoare triple {697#true} assume true; {697#true} is VALID [2022-04-08 13:24:47,443 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {697#true} {697#true} #111#return; {697#true} is VALID [2022-04-08 13:24:47,443 INFO L272 TraceCheckUtils]: 4: Hoare triple {697#true} call #t~ret9 := main(); {697#true} is VALID [2022-04-08 13:24:47,444 INFO L290 TraceCheckUtils]: 5: Hoare triple {697#true} havoc ~a~0;havoc ~b~0;havoc ~x~0;havoc ~y~0;havoc ~u~0;havoc ~v~0;~a~0 := #t~nondet4;havoc #t~nondet4;~b~0 := #t~nondet5;havoc #t~nondet5; {697#true} is VALID [2022-04-08 13:24:47,444 INFO L272 TraceCheckUtils]: 6: Hoare triple {697#true} call assume_abort_if_not((if ~a~0 % 4294967296 >= 1 then 1 else 0)); {697#true} is VALID [2022-04-08 13:24:47,444 INFO L290 TraceCheckUtils]: 7: Hoare triple {697#true} ~cond := #in~cond; {697#true} is VALID [2022-04-08 13:24:47,444 INFO L290 TraceCheckUtils]: 8: Hoare triple {697#true} assume !(0 == ~cond); {697#true} is VALID [2022-04-08 13:24:47,444 INFO L290 TraceCheckUtils]: 9: Hoare triple {697#true} assume true; {697#true} is VALID [2022-04-08 13:24:47,444 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {697#true} {697#true} #93#return; {697#true} is VALID [2022-04-08 13:24:47,444 INFO L272 TraceCheckUtils]: 11: Hoare triple {697#true} call assume_abort_if_not((if ~b~0 % 4294967296 >= 1 then 1 else 0)); {697#true} is VALID [2022-04-08 13:24:47,444 INFO L290 TraceCheckUtils]: 12: Hoare triple {697#true} ~cond := #in~cond; {697#true} is VALID [2022-04-08 13:24:47,445 INFO L290 TraceCheckUtils]: 13: Hoare triple {697#true} assume !(0 == ~cond); {697#true} is VALID [2022-04-08 13:24:47,445 INFO L290 TraceCheckUtils]: 14: Hoare triple {697#true} assume true; {697#true} is VALID [2022-04-08 13:24:47,445 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {697#true} {697#true} #95#return; {697#true} is VALID [2022-04-08 13:24:47,445 INFO L272 TraceCheckUtils]: 16: Hoare triple {697#true} call assume_abort_if_not((if ~a~0 % 4294967296 <= 65535 then 1 else 0)); {697#true} is VALID [2022-04-08 13:24:47,445 INFO L290 TraceCheckUtils]: 17: Hoare triple {697#true} ~cond := #in~cond; {697#true} is VALID [2022-04-08 13:24:47,445 INFO L290 TraceCheckUtils]: 18: Hoare triple {697#true} assume !(0 == ~cond); {697#true} is VALID [2022-04-08 13:24:47,445 INFO L290 TraceCheckUtils]: 19: Hoare triple {697#true} assume true; {697#true} is VALID [2022-04-08 13:24:47,445 INFO L284 TraceCheckUtils]: 20: Hoare quadruple {697#true} {697#true} #97#return; {697#true} is VALID [2022-04-08 13:24:47,446 INFO L272 TraceCheckUtils]: 21: Hoare triple {697#true} call assume_abort_if_not((if ~b~0 % 4294967296 <= 65535 then 1 else 0)); {697#true} is VALID [2022-04-08 13:24:47,446 INFO L290 TraceCheckUtils]: 22: Hoare triple {697#true} ~cond := #in~cond; {697#true} is VALID [2022-04-08 13:24:47,446 INFO L290 TraceCheckUtils]: 23: Hoare triple {697#true} assume !(0 == ~cond); {697#true} is VALID [2022-04-08 13:24:47,446 INFO L290 TraceCheckUtils]: 24: Hoare triple {697#true} assume true; {697#true} is VALID [2022-04-08 13:24:47,446 INFO L284 TraceCheckUtils]: 25: Hoare quadruple {697#true} {697#true} #99#return; {697#true} is VALID [2022-04-08 13:24:47,459 INFO L290 TraceCheckUtils]: 26: Hoare triple {697#true} ~x~0 := ~a~0;~y~0 := ~b~0;~u~0 := ~b~0;~v~0 := 0; {780#(and (= main_~v~0 0) (= main_~b~0 main_~u~0) (= main_~a~0 main_~x~0))} is VALID [2022-04-08 13:24:47,460 INFO L290 TraceCheckUtils]: 27: Hoare triple {780#(and (= main_~v~0 0) (= main_~b~0 main_~u~0) (= main_~a~0 main_~x~0))} #t~post6 := ~counter~0;~counter~0 := 1 + #t~post6; {780#(and (= main_~v~0 0) (= main_~b~0 main_~u~0) (= main_~a~0 main_~x~0))} is VALID [2022-04-08 13:24:47,460 INFO L290 TraceCheckUtils]: 28: Hoare triple {780#(and (= main_~v~0 0) (= main_~b~0 main_~u~0) (= main_~a~0 main_~x~0))} assume !!(#t~post6 < 10);havoc #t~post6; {780#(and (= main_~v~0 0) (= main_~b~0 main_~u~0) (= main_~a~0 main_~x~0))} is VALID [2022-04-08 13:24:47,461 INFO L272 TraceCheckUtils]: 29: Hoare triple {780#(and (= main_~v~0 0) (= main_~b~0 main_~u~0) (= main_~a~0 main_~x~0))} call __VERIFIER_assert((if (~x~0 * ~u~0 + ~y~0 * ~v~0) % 4294967296 == ~a~0 * ~b~0 % 4294967296 then 1 else 0)); {790#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-08 13:24:47,462 INFO L290 TraceCheckUtils]: 30: Hoare triple {790#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {794#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-08 13:24:47,462 INFO L290 TraceCheckUtils]: 31: Hoare triple {794#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {698#false} is VALID [2022-04-08 13:24:47,462 INFO L290 TraceCheckUtils]: 32: Hoare triple {698#false} assume !false; {698#false} is VALID [2022-04-08 13:24:47,462 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-08 13:24:47,462 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-08 13:24:47,463 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-08 13:24:47,463 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484419374] [2022-04-08 13:24:47,463 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-08 13:24:47,463 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2134498087] [2022-04-08 13:24:47,463 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2134498087] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 13:24:47,463 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 13:24:47,463 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 13:24:47,463 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-08 13:24:47,464 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1513794748] [2022-04-08 13:24:47,464 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1513794748] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-08 13:24:47,464 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-08 13:24:47,464 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-08 13:24:47,464 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [28295694] [2022-04-08 13:24:47,464 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-08 13:24:47,464 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 33 [2022-04-08 13:24:47,465 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-08 13:24:47,465 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-08 13:24:47,480 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 24 edges. 24 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:47,481 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-08 13:24:47,481 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-08 13:24:47,481 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-08 13:24:47,481 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-08 13:24:47,481 INFO L87 Difference]: Start difference. First operand 37 states and 49 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-08 13:24:47,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:47,724 INFO L93 Difference]: Finished difference Result 57 states and 78 transitions. [2022-04-08 13:24:47,724 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-08 13:24:47,724 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 33 [2022-04-08 13:24:47,724 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-08 13:24:47,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-08 13:24:47,726 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 76 transitions. [2022-04-08 13:24:47,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-08 13:24:47,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 76 transitions. [2022-04-08 13:24:47,728 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 76 transitions. [2022-04-08 13:24:47,797 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 76 edges. 76 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:47,799 INFO L225 Difference]: With dead ends: 57 [2022-04-08 13:24:47,799 INFO L226 Difference]: Without dead ends: 55 [2022-04-08 13:24:47,802 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 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-08 13:24:47,803 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 16 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-08 13:24:47,804 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 138 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-08 13:24:47,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-08 13:24:47,824 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 53. [2022-04-08 13:24:47,824 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-08 13:24:47,826 INFO L82 GeneralOperation]: Start isEquivalent. First operand 55 states. Second operand has 53 states, 34 states have (on average 1.3823529411764706) internal successors, (47), 35 states have internal predecessors, (47), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 13:24:47,826 INFO L74 IsIncluded]: Start isIncluded. First operand 55 states. Second operand has 53 states, 34 states have (on average 1.3823529411764706) internal successors, (47), 35 states have internal predecessors, (47), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 13:24:47,827 INFO L87 Difference]: Start difference. First operand 55 states. Second operand has 53 states, 34 states have (on average 1.3823529411764706) internal successors, (47), 35 states have internal predecessors, (47), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 13:24:47,829 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:47,829 INFO L93 Difference]: Finished difference Result 55 states and 76 transitions. [2022-04-08 13:24:47,829 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2022-04-08 13:24:47,830 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 13:24:47,830 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 13:24:47,830 INFO L74 IsIncluded]: Start isIncluded. First operand has 53 states, 34 states have (on average 1.3823529411764706) internal successors, (47), 35 states have internal predecessors, (47), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 55 states. [2022-04-08 13:24:47,831 INFO L87 Difference]: Start difference. First operand has 53 states, 34 states have (on average 1.3823529411764706) internal successors, (47), 35 states have internal predecessors, (47), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand 55 states. [2022-04-08 13:24:47,832 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-08 13:24:47,833 INFO L93 Difference]: Finished difference Result 55 states and 76 transitions. [2022-04-08 13:24:47,833 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 76 transitions. [2022-04-08 13:24:47,833 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-08 13:24:47,833 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-08 13:24:47,833 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-08 13:24:47,833 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-08 13:24:47,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 34 states have (on average 1.3823529411764706) internal successors, (47), 35 states have internal predecessors, (47), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-08 13:24:47,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 73 transitions. [2022-04-08 13:24:47,838 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 73 transitions. Word has length 33 [2022-04-08 13:24:47,839 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-08 13:24:47,839 INFO L478 AbstractCegarLoop]: Abstraction has 53 states and 73 transitions. [2022-04-08 13:24:47,840 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-04-08 13:24:47,840 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 53 states and 73 transitions. [2022-04-08 13:24:47,910 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 73 edges. 73 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-08 13:24:47,910 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 73 transitions. [2022-04-08 13:24:47,913 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-04-08 13:24:47,913 INFO L491 BasicCegarLoop]: Found error trace [2022-04-08 13:24:47,913 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 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] [2022-04-08 13:24:47,955 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-08 13:24:48,114 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-08 13:24:48,114 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-08 13:24:48,115 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-08 13:24:48,115 INFO L85 PathProgramCache]: Analyzing trace with hash 758334593, now seen corresponding path program 1 times [2022-04-08 13:24:48,115 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-08 13:24:48,115 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [77516441] [2022-04-08 13:24:48,115 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-08 13:24:48,116 INFO L85 PathProgramCache]: Analyzing trace with hash 758334593, now seen corresponding path program 2 times [2022-04-08 13:24:48,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-08 13:24:48,116 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1153500807] [2022-04-08 13:24:48,116 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-08 13:24:48,116 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-08 13:24:48,129 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-08 13:24:48,129 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1447541253] [2022-04-08 13:24:48,129 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-08 13:24:48,129 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-08 13:24:48,129 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-08 13:24:48,130 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-08 13:24:48,146 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process