/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/acceleratedInterpolationJordan_32.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-e106359-m [2022-04-15 07:55:27,850 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-15 07:55:27,852 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-15 07:55:27,900 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-15 07:55:27,901 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-15 07:55:27,902 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-15 07:55:27,904 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-15 07:55:27,908 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-15 07:55:27,909 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-15 07:55:27,912 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-15 07:55:27,913 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-15 07:55:27,914 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-15 07:55:27,914 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-15 07:55:27,915 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-15 07:55:27,916 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-15 07:55:27,918 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-15 07:55:27,919 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-15 07:55:27,919 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-15 07:55:27,920 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-15 07:55:27,924 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-15 07:55:27,925 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-15 07:55:27,926 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-15 07:55:27,927 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-15 07:55:27,927 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-15 07:55:27,928 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-15 07:55:27,933 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-15 07:55:27,933 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-15 07:55:27,933 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-15 07:55:27,934 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-15 07:55:27,934 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-15 07:55:27,935 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-15 07:55:27,935 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-15 07:55:27,936 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-15 07:55:27,937 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-15 07:55:27,937 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-15 07:55:27,937 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-15 07:55:27,938 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-15 07:55:27,938 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-15 07:55:27,938 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-15 07:55:27,938 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-15 07:55:27,939 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-15 07:55:27,940 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-15 07:55:27,940 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationJordan_32.epf [2022-04-15 07:55:27,947 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-15 07:55:27,947 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-15 07:55:27,948 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-15 07:55:27,948 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-15 07:55:27,948 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-15 07:55:27,948 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-15 07:55:27,949 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-15 07:55:27,949 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-15 07:55:27,949 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-15 07:55:27,949 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-15 07:55:27,949 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-15 07:55:27,949 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-15 07:55:27,950 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-15 07:55:27,950 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-15 07:55:27,950 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-15 07:55:27,950 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-15 07:55:27,950 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-15 07:55:27,950 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-15 07:55:27,950 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 07:55:27,950 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-15 07:55:27,950 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-15 07:55:27,951 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-15 07:55:27,951 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-15 07:55:27,951 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-15 07:55:27,951 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=JORDAN [2022-04-15 07:55:27,951 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-15 07:55:28,144 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-15 07:55:28,157 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-15 07:55:28,159 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-15 07:55:28,159 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-15 07:55:28,161 INFO L275 PluginConnector]: CDTParser initialized [2022-04-15 07:55:28,162 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound100.c [2022-04-15 07:55:28,196 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/19314dc97/74344131b9de44189a31029e5513fa26/FLAG499a87c1f [2022-04-15 07:55:28,557 INFO L306 CDTParser]: Found 1 translation units. [2022-04-15 07:55:28,557 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound100.c [2022-04-15 07:55:28,563 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/19314dc97/74344131b9de44189a31029e5513fa26/FLAG499a87c1f [2022-04-15 07:55:28,574 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/19314dc97/74344131b9de44189a31029e5513fa26 [2022-04-15 07:55:28,576 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-15 07:55:28,577 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-15 07:55:28,581 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-15 07:55:28,581 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-15 07:55:28,583 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-15 07:55:28,584 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,585 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7ed9f379 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28, skipping insertion in model container [2022-04-15 07:55:28,585 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,590 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-15 07:55:28,603 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-15 07:55:28,734 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound100.c[525,538] [2022-04-15 07:55:28,771 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 07:55:28,780 INFO L203 MainTranslator]: Completed pre-run [2022-04-15 07:55:28,789 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/dijkstra-u_valuebound100.c[525,538] [2022-04-15 07:55:28,805 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-15 07:55:28,813 INFO L208 MainTranslator]: Completed translation [2022-04-15 07:55:28,814 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28 WrapperNode [2022-04-15 07:55:28,814 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-15 07:55:28,815 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-15 07:55:28,815 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-15 07:55:28,815 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-15 07:55:28,823 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,823 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,836 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,836 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,845 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,848 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,848 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,849 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-15 07:55:28,850 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-15 07:55:28,850 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-15 07:55:28,850 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-15 07:55:28,851 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (1/1) ... [2022-04-15 07:55:28,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-15 07:55:28,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:55:28,869 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-15 07:55:28,870 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-15 07:55:28,895 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-15 07:55:28,895 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-15 07:55:28,895 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-15 07:55:28,895 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-15 07:55:28,895 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-15 07:55:28,895 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-15 07:55:28,896 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-15 07:55:28,896 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-15 07:55:28,896 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-15 07:55:28,896 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-15 07:55:28,897 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-15 07:55:28,897 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-15 07:55:28,898 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-15 07:55:28,936 INFO L234 CfgBuilder]: Building ICFG [2022-04-15 07:55:28,937 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-15 07:55:29,084 INFO L275 CfgBuilder]: Performing block encoding [2022-04-15 07:55:29,104 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-15 07:55:29,104 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-15 07:55:29,106 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 07:55:29 BoogieIcfgContainer [2022-04-15 07:55:29,106 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-15 07:55:29,107 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-15 07:55:29,107 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-15 07:55:29,109 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-15 07:55:29,109 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.04 07:55:28" (1/3) ... [2022-04-15 07:55:29,109 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f143e84 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 07:55:29, skipping insertion in model container [2022-04-15 07:55:29,109 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.04 07:55:28" (2/3) ... [2022-04-15 07:55:29,110 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5f143e84 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.04 07:55:29, skipping insertion in model container [2022-04-15 07:55:29,110 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.04 07:55:29" (3/3) ... [2022-04-15 07:55:29,110 INFO L111 eAbstractionObserver]: Analyzing ICFG dijkstra-u_valuebound100.c [2022-04-15 07:55:29,113 INFO L202 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-15 07:55:29,114 INFO L161 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-15 07:55:29,161 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-15 07:55:29,164 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-15 07:55:29,164 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-15 07:55:29,177 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-15 07:55:29,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-15 07:55:29,181 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:55:29,182 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:55:29,182 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:55:29,185 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:55:29,185 INFO L85 PathProgramCache]: Analyzing trace with hash 223850557, now seen corresponding path program 1 times [2022-04-15 07:55:29,189 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:55:29,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [94079346] [2022-04-15 07:55:29,196 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:55:29,196 INFO L85 PathProgramCache]: Analyzing trace with hash 223850557, now seen corresponding path program 2 times [2022-04-15 07:55:29,198 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:55:29,198 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1988019832] [2022-04-15 07:55:29,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:55:29,199 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:55:29,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:29,323 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 07:55:29,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:29,351 INFO L290 TraceCheckUtils]: 0: Hoare triple {54#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {41#true} is VALID [2022-04-15 07:55:29,352 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 07:55:29,352 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-15 07:55:29,352 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 07:55:29,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:29,361 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 07:55:29,361 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 07:55:29,361 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 07:55:29,362 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-15 07:55:29,362 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-15 07:55:29,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:29,384 INFO L290 TraceCheckUtils]: 0: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 07:55:29,385 INFO L290 TraceCheckUtils]: 1: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 07:55:29,385 INFO L290 TraceCheckUtils]: 2: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 07:55:29,385 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-15 07:55:29,386 INFO L272 TraceCheckUtils]: 0: Hoare triple {41#true} call ULTIMATE.init(); {54#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 07:55:29,386 INFO L290 TraceCheckUtils]: 1: Hoare triple {54#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {41#true} is VALID [2022-04-15 07:55:29,386 INFO L290 TraceCheckUtils]: 2: Hoare triple {41#true} assume true; {41#true} is VALID [2022-04-15 07:55:29,386 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {41#true} {41#true} #103#return; {41#true} is VALID [2022-04-15 07:55:29,386 INFO L272 TraceCheckUtils]: 4: Hoare triple {41#true} call #t~ret5 := main(); {41#true} is VALID [2022-04-15 07:55:29,387 INFO L290 TraceCheckUtils]: 5: Hoare triple {41#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {41#true} is VALID [2022-04-15 07:55:29,387 INFO L272 TraceCheckUtils]: 6: Hoare triple {41#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 100 then 1 else 0)); {41#true} is VALID [2022-04-15 07:55:29,387 INFO L290 TraceCheckUtils]: 7: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 07:55:29,388 INFO L290 TraceCheckUtils]: 8: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 07:55:29,388 INFO L290 TraceCheckUtils]: 9: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 07:55:29,389 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {42#false} {41#true} #81#return; {42#false} is VALID [2022-04-15 07:55:29,389 INFO L272 TraceCheckUtils]: 11: Hoare triple {42#false} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {41#true} is VALID [2022-04-15 07:55:29,389 INFO L290 TraceCheckUtils]: 12: Hoare triple {41#true} ~cond := #in~cond; {41#true} is VALID [2022-04-15 07:55:29,389 INFO L290 TraceCheckUtils]: 13: Hoare triple {41#true} assume 0 == ~cond;assume false; {42#false} is VALID [2022-04-15 07:55:29,389 INFO L290 TraceCheckUtils]: 14: Hoare triple {42#false} assume true; {42#false} is VALID [2022-04-15 07:55:29,390 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {42#false} {42#false} #83#return; {42#false} is VALID [2022-04-15 07:55:29,390 INFO L290 TraceCheckUtils]: 16: Hoare triple {42#false} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {42#false} is VALID [2022-04-15 07:55:29,390 INFO L290 TraceCheckUtils]: 17: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-15 07:55:29,390 INFO L290 TraceCheckUtils]: 18: Hoare triple {42#false} assume false; {42#false} is VALID [2022-04-15 07:55:29,390 INFO L272 TraceCheckUtils]: 19: Hoare triple {42#false} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 + 16 * ~n~0 * ~p~0 + 12 * ~h~0 * ~r~0 - 16 * ~p~0 * ~r~0 - ~h~0 - 4 * ~p~0) % 4294967296 then 1 else 0)); {42#false} is VALID [2022-04-15 07:55:29,390 INFO L290 TraceCheckUtils]: 20: Hoare triple {42#false} ~cond := #in~cond; {42#false} is VALID [2022-04-15 07:55:29,390 INFO L290 TraceCheckUtils]: 21: Hoare triple {42#false} assume 0 == ~cond; {42#false} is VALID [2022-04-15 07:55:29,391 INFO L290 TraceCheckUtils]: 22: Hoare triple {42#false} assume !false; {42#false} is VALID [2022-04-15 07:55:29,391 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-15 07:55:29,391 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:55:29,391 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1988019832] [2022-04-15 07:55:29,392 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1988019832] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:55:29,392 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:55:29,392 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 07:55:29,393 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:55:29,394 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [94079346] [2022-04-15 07:55:29,394 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [94079346] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:55:29,394 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:55:29,394 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-15 07:55:29,394 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [363423516] [2022-04-15 07:55:29,394 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:55:29,397 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-15 07:55:29,398 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:55:29,400 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:55:29,431 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 20 edges. 20 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:55:29,432 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-15 07:55:29,432 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:55:29,448 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-15 07:55:29,449 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 07:55:29,452 INFO L87 Difference]: Start difference. First operand has 38 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:55:31,587 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-15 07:55:31,824 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:55:31,824 INFO L93 Difference]: Finished difference Result 69 states and 113 transitions. [2022-04-15 07:55:31,824 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-15 07:55:31,824 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-15 07:55:31,825 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:55:31,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:55:31,831 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-15 07:55:31,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:55:31,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 113 transitions. [2022-04-15 07:55:31,836 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 3 states and 113 transitions. [2022-04-15 07:55:31,942 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 113 edges. 113 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:55:31,948 INFO L225 Difference]: With dead ends: 69 [2022-04-15 07:55:31,948 INFO L226 Difference]: Without dead ends: 33 [2022-04-15 07:55:31,950 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-15 07:55:31,952 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 13 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2022-04-15 07:55:31,952 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 42 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 11 Invalid, 1 Unknown, 0 Unchecked, 2.1s Time] [2022-04-15 07:55:31,961 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-15 07:55:31,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-15 07:55:31,971 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:55:31,972 INFO L82 GeneralOperation]: Start isEquivalent. First operand 33 states. Second operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 07:55:31,972 INFO L74 IsIncluded]: Start isIncluded. First operand 33 states. Second operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 07:55:31,972 INFO L87 Difference]: Start difference. First operand 33 states. Second operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 07:55:31,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:55:31,976 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-15 07:55:31,976 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-15 07:55:31,976 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:55:31,976 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:55:31,977 INFO L74 IsIncluded]: Start isIncluded. First operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 33 states. [2022-04-15 07:55:31,977 INFO L87 Difference]: Start difference. First operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand 33 states. [2022-04-15 07:55:31,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:55:31,979 INFO L93 Difference]: Finished difference Result 33 states and 44 transitions. [2022-04-15 07:55:31,980 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-15 07:55:31,980 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:55:31,980 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:55:31,980 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:55:31,980 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:55:31,981 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-15 07:55:31,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2022-04-15 07:55:31,983 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 23 [2022-04-15 07:55:31,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:55:31,984 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2022-04-15 07:55:32,001 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-15 07:55:32,002 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 33 states and 44 transitions. [2022-04-15 07:55:32,060 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 44 edges. 44 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:55:32,060 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2022-04-15 07:55:32,062 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-15 07:55:32,062 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:55:32,063 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:55:32,063 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-15 07:55:32,063 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:55:32,064 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:55:32,065 INFO L85 PathProgramCache]: Analyzing trace with hash -563604624, now seen corresponding path program 1 times [2022-04-15 07:55:32,065 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:55:32,065 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1564304960] [2022-04-15 07:55:32,067 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:55:32,067 INFO L85 PathProgramCache]: Analyzing trace with hash -563604624, now seen corresponding path program 2 times [2022-04-15 07:55:32,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:55:32,069 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1992165602] [2022-04-15 07:55:32,069 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:55:32,070 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:55:32,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:32,260 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 07:55:32,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:32,272 INFO L290 TraceCheckUtils]: 0: Hoare triple {344#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {327#true} is VALID [2022-04-15 07:55:32,272 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 07:55:32,272 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {327#true} {327#true} #103#return; {327#true} is VALID [2022-04-15 07:55:32,273 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 07:55:32,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:32,282 INFO L290 TraceCheckUtils]: 0: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 07:55:32,283 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 07:55:32,283 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 07:55:32,283 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #81#return; {327#true} is VALID [2022-04-15 07:55:32,283 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-15 07:55:32,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:55:32,287 INFO L290 TraceCheckUtils]: 0: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 07:55:32,287 INFO L290 TraceCheckUtils]: 1: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 07:55:32,288 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 07:55:32,288 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #83#return; {327#true} is VALID [2022-04-15 07:55:32,288 INFO L272 TraceCheckUtils]: 0: Hoare triple {327#true} call ULTIMATE.init(); {344#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 07:55:32,289 INFO L290 TraceCheckUtils]: 1: Hoare triple {344#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {327#true} is VALID [2022-04-15 07:55:32,289 INFO L290 TraceCheckUtils]: 2: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 07:55:32,289 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {327#true} {327#true} #103#return; {327#true} is VALID [2022-04-15 07:55:32,289 INFO L272 TraceCheckUtils]: 4: Hoare triple {327#true} call #t~ret5 := main(); {327#true} is VALID [2022-04-15 07:55:32,289 INFO L290 TraceCheckUtils]: 5: Hoare triple {327#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {327#true} is VALID [2022-04-15 07:55:32,290 INFO L272 TraceCheckUtils]: 6: Hoare triple {327#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 100 then 1 else 0)); {327#true} is VALID [2022-04-15 07:55:32,290 INFO L290 TraceCheckUtils]: 7: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 07:55:32,290 INFO L290 TraceCheckUtils]: 8: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 07:55:32,290 INFO L290 TraceCheckUtils]: 9: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 07:55:32,290 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {327#true} {327#true} #81#return; {327#true} is VALID [2022-04-15 07:55:32,291 INFO L272 TraceCheckUtils]: 11: Hoare triple {327#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {327#true} is VALID [2022-04-15 07:55:32,291 INFO L290 TraceCheckUtils]: 12: Hoare triple {327#true} ~cond := #in~cond; {327#true} is VALID [2022-04-15 07:55:32,291 INFO L290 TraceCheckUtils]: 13: Hoare triple {327#true} assume !(0 == ~cond); {327#true} is VALID [2022-04-15 07:55:32,291 INFO L290 TraceCheckUtils]: 14: Hoare triple {327#true} assume true; {327#true} is VALID [2022-04-15 07:55:32,291 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {327#true} {327#true} #83#return; {327#true} is VALID [2022-04-15 07:55:32,292 INFO L290 TraceCheckUtils]: 16: Hoare triple {327#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-15 07:55:32,293 INFO L290 TraceCheckUtils]: 17: Hoare triple {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !false; {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} is VALID [2022-04-15 07:55:32,294 INFO L290 TraceCheckUtils]: 18: Hoare triple {340#(and (= main_~p~0 0) (= main_~n~0 main_~r~0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-15 07:55:32,294 INFO L290 TraceCheckUtils]: 19: Hoare triple {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} assume !false; {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} is VALID [2022-04-15 07:55:32,300 INFO L272 TraceCheckUtils]: 20: Hoare triple {341#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0) (= (+ (- 1) main_~q~0) 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {342#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 07:55:32,300 INFO L290 TraceCheckUtils]: 21: Hoare triple {342#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {343#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 07:55:32,301 INFO L290 TraceCheckUtils]: 22: Hoare triple {343#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {328#false} is VALID [2022-04-15 07:55:32,301 INFO L290 TraceCheckUtils]: 23: Hoare triple {328#false} assume !false; {328#false} is VALID [2022-04-15 07:55:32,301 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-15 07:55:32,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:55:32,301 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1992165602] [2022-04-15 07:55:32,301 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1992165602] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:55:32,302 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:55:32,302 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 07:55:32,302 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:55:32,302 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1564304960] [2022-04-15 07:55:32,302 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1564304960] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:55:32,302 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:55:32,302 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 07:55:32,302 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1559817778] [2022-04-15 07:55:32,302 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:55:32,303 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2022-04-15 07:55:32,303 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:55:32,304 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:55:32,328 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 21 edges. 21 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:55:32,328 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-15 07:55:32,329 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:55:32,329 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-15 07:55:32,329 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-15 07:55:32,329 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:55:42,805 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.32s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-15 07:55:44,807 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-15 07:55:50,947 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 07:56:03,182 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 07:56:05,226 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:05,226 INFO L93 Difference]: Finished difference Result 68 states and 98 transitions. [2022-04-15 07:56:05,226 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 07:56:05,226 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2022-04-15 07:56:05,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:56:05,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:05,233 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 98 transitions. [2022-04-15 07:56:05,233 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:05,235 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 98 transitions. [2022-04-15 07:56:05,235 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 98 transitions. [2022-04-15 07:56:05,437 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 98 edges. 98 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:05,439 INFO L225 Difference]: With dead ends: 68 [2022-04-15 07:56:05,439 INFO L226 Difference]: Without dead ends: 48 [2022-04-15 07:56:05,439 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-15 07:56:05,440 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 34 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 203 mSolverCounterSat, 50 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 203 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.6s IncrementalHoareTripleChecker+Time [2022-04-15 07:56:05,440 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 56 Invalid, 257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 203 Invalid, 4 Unknown, 0 Unchecked, 13.6s Time] [2022-04-15 07:56:05,441 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-15 07:56:05,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2022-04-15 07:56:05,462 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:56:05,463 INFO L82 GeneralOperation]: Start isEquivalent. First operand 48 states. Second operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 07:56:05,465 INFO L74 IsIncluded]: Start isIncluded. First operand 48 states. Second operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 07:56:05,466 INFO L87 Difference]: Start difference. First operand 48 states. Second operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 07:56:05,468 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:05,468 INFO L93 Difference]: Finished difference Result 48 states and 65 transitions. [2022-04-15 07:56:05,468 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 65 transitions. [2022-04-15 07:56:05,469 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:05,469 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:05,469 INFO L74 IsIncluded]: Start isIncluded. First operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 48 states. [2022-04-15 07:56:05,470 INFO L87 Difference]: Start difference. First operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) Second operand 48 states. [2022-04-15 07:56:05,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:05,472 INFO L93 Difference]: Finished difference Result 48 states and 65 transitions. [2022-04-15 07:56:05,472 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 65 transitions. [2022-04-15 07:56:05,473 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:05,473 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:05,473 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:56:05,473 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:56:05,473 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 20 states have call successors, (20), 5 states have call predecessors, (20), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-15 07:56:05,475 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 65 transitions. [2022-04-15 07:56:05,475 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 65 transitions. Word has length 24 [2022-04-15 07:56:05,476 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:56:05,476 INFO L478 AbstractCegarLoop]: Abstraction has 48 states and 65 transitions. [2022-04-15 07:56:05,476 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:05,476 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 48 states and 65 transitions. [2022-04-15 07:56:05,693 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 65 edges. 65 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:05,693 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 65 transitions. [2022-04-15 07:56:05,694 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2022-04-15 07:56:05,694 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:56:05,694 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:56:05,694 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-15 07:56:05,694 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:56:05,695 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:56:05,695 INFO L85 PathProgramCache]: Analyzing trace with hash -5094773, now seen corresponding path program 1 times [2022-04-15 07:56:05,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:56:05,695 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1189322519] [2022-04-15 07:56:05,695 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:56:05,695 INFO L85 PathProgramCache]: Analyzing trace with hash -5094773, now seen corresponding path program 2 times [2022-04-15 07:56:05,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:56:05,696 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1824403329] [2022-04-15 07:56:05,696 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:56:05,696 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:56:05,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:56:05,840 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-15 07:56:05,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:56:05,846 INFO L290 TraceCheckUtils]: 0: Hoare triple {702#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {685#true} is VALID [2022-04-15 07:56:05,846 INFO L290 TraceCheckUtils]: 1: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-15 07:56:05,846 INFO L284 TraceCheckUtils]: 2: Hoare quadruple {685#true} {685#true} #103#return; {685#true} is VALID [2022-04-15 07:56:05,846 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-15 07:56:05,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:56:05,849 INFO L290 TraceCheckUtils]: 0: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-15 07:56:05,849 INFO L290 TraceCheckUtils]: 1: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-15 07:56:05,849 INFO L290 TraceCheckUtils]: 2: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-15 07:56:05,849 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {685#true} {685#true} #81#return; {685#true} is VALID [2022-04-15 07:56:05,849 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2022-04-15 07:56:05,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:56:05,852 INFO L290 TraceCheckUtils]: 0: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-15 07:56:05,852 INFO L290 TraceCheckUtils]: 1: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-15 07:56:05,853 INFO L290 TraceCheckUtils]: 2: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-15 07:56:05,853 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {685#true} {685#true} #83#return; {685#true} is VALID [2022-04-15 07:56:05,853 INFO L272 TraceCheckUtils]: 0: Hoare triple {685#true} call ULTIMATE.init(); {702#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} is VALID [2022-04-15 07:56:05,853 INFO L290 TraceCheckUtils]: 1: Hoare triple {702#(and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|))} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {685#true} is VALID [2022-04-15 07:56:05,854 INFO L290 TraceCheckUtils]: 2: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-15 07:56:05,854 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {685#true} {685#true} #103#return; {685#true} is VALID [2022-04-15 07:56:05,854 INFO L272 TraceCheckUtils]: 4: Hoare triple {685#true} call #t~ret5 := main(); {685#true} is VALID [2022-04-15 07:56:05,854 INFO L290 TraceCheckUtils]: 5: Hoare triple {685#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {685#true} is VALID [2022-04-15 07:56:05,854 INFO L272 TraceCheckUtils]: 6: Hoare triple {685#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 100 then 1 else 0)); {685#true} is VALID [2022-04-15 07:56:05,855 INFO L290 TraceCheckUtils]: 7: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-15 07:56:05,855 INFO L290 TraceCheckUtils]: 8: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-15 07:56:05,855 INFO L290 TraceCheckUtils]: 9: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-15 07:56:05,855 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {685#true} {685#true} #81#return; {685#true} is VALID [2022-04-15 07:56:05,855 INFO L272 TraceCheckUtils]: 11: Hoare triple {685#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {685#true} is VALID [2022-04-15 07:56:05,855 INFO L290 TraceCheckUtils]: 12: Hoare triple {685#true} ~cond := #in~cond; {685#true} is VALID [2022-04-15 07:56:05,855 INFO L290 TraceCheckUtils]: 13: Hoare triple {685#true} assume !(0 == ~cond); {685#true} is VALID [2022-04-15 07:56:05,856 INFO L290 TraceCheckUtils]: 14: Hoare triple {685#true} assume true; {685#true} is VALID [2022-04-15 07:56:05,856 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {685#true} {685#true} #83#return; {685#true} is VALID [2022-04-15 07:56:05,856 INFO L290 TraceCheckUtils]: 16: Hoare triple {685#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 07:56:05,857 INFO L290 TraceCheckUtils]: 17: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 07:56:05,857 INFO L290 TraceCheckUtils]: 18: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 07:56:05,857 INFO L290 TraceCheckUtils]: 19: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !false; {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} is VALID [2022-04-15 07:56:05,858 INFO L290 TraceCheckUtils]: 20: Hoare triple {698#(and (= main_~p~0 0) (= main_~n~0 main_~r~0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-15 07:56:05,859 INFO L290 TraceCheckUtils]: 21: Hoare triple {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} assume !false; {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} is VALID [2022-04-15 07:56:05,860 INFO L272 TraceCheckUtils]: 22: Hoare triple {699#(and (<= (+ (* (div (+ (* main_~p~0 2) main_~q~0) 4294967296) 4294967296) main_~r~0 1) (+ main_~q~0 (* (div main_~r~0 4294967296) 4294967296))) (= main_~p~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {700#(not (= |__VERIFIER_assert_#in~cond| 0))} is VALID [2022-04-15 07:56:05,860 INFO L290 TraceCheckUtils]: 23: Hoare triple {700#(not (= |__VERIFIER_assert_#in~cond| 0))} ~cond := #in~cond; {701#(not (= __VERIFIER_assert_~cond 0))} is VALID [2022-04-15 07:56:05,860 INFO L290 TraceCheckUtils]: 24: Hoare triple {701#(not (= __VERIFIER_assert_~cond 0))} assume 0 == ~cond; {686#false} is VALID [2022-04-15 07:56:05,861 INFO L290 TraceCheckUtils]: 25: Hoare triple {686#false} assume !false; {686#false} is VALID [2022-04-15 07:56:05,861 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-04-15 07:56:05,861 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:56:05,861 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1824403329] [2022-04-15 07:56:05,861 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1824403329] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:56:05,861 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:56:05,861 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 07:56:05,862 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:56:05,862 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1189322519] [2022-04-15 07:56:05,862 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1189322519] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:56:05,862 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:56:05,862 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2022-04-15 07:56:05,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [290132844] [2022-04-15 07:56:05,862 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:56:05,863 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 26 [2022-04-15 07:56:05,863 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:56:05,863 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:05,879 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 22 edges. 22 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:05,879 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-15 07:56:05,879 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:56:05,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-15 07:56:05,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2022-04-15 07:56:05,880 INFO L87 Difference]: Start difference. First operand 48 states and 65 transitions. Second operand has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:15,318 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 07:56:17,412 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-15 07:56:28,044 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-15 07:56:30,598 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:30,598 INFO L93 Difference]: Finished difference Result 76 states and 111 transitions. [2022-04-15 07:56:30,598 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-15 07:56:30,598 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 26 [2022-04-15 07:56:30,599 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:56:30,599 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:30,601 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-15 07:56:30,601 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:30,603 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 90 transitions. [2022-04-15 07:56:30,603 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 8 states and 90 transitions. [2022-04-15 07:56:30,903 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 90 edges. 90 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:30,906 INFO L225 Difference]: With dead ends: 76 [2022-04-15 07:56:30,906 INFO L226 Difference]: Without dead ends: 72 [2022-04-15 07:56:30,906 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-04-15 07:56:30,907 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 38 mSDsluCounter, 23 mSDsCounter, 0 mSdLazyCounter, 229 mSolverCounterSat, 76 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 52 SdHoareTripleChecker+Invalid, 308 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 76 IncrementalHoareTripleChecker+Valid, 229 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.6s IncrementalHoareTripleChecker+Time [2022-04-15 07:56:30,907 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [48 Valid, 52 Invalid, 308 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [76 Valid, 229 Invalid, 3 Unknown, 0 Unchecked, 11.6s Time] [2022-04-15 07:56:30,907 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-04-15 07:56:30,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 69. [2022-04-15 07:56:30,935 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:56:30,936 INFO L82 GeneralOperation]: Start isEquivalent. First operand 72 states. Second operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-15 07:56:30,936 INFO L74 IsIncluded]: Start isIncluded. First operand 72 states. Second operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-15 07:56:30,936 INFO L87 Difference]: Start difference. First operand 72 states. Second operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-15 07:56:30,940 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:30,940 INFO L93 Difference]: Finished difference Result 72 states and 105 transitions. [2022-04-15 07:56:30,940 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 105 transitions. [2022-04-15 07:56:30,941 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:30,941 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:30,941 INFO L74 IsIncluded]: Start isIncluded. First operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) Second operand 72 states. [2022-04-15 07:56:30,942 INFO L87 Difference]: Start difference. First operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) Second operand 72 states. [2022-04-15 07:56:30,945 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:30,945 INFO L93 Difference]: Finished difference Result 72 states and 105 transitions. [2022-04-15 07:56:30,945 INFO L276 IsEmpty]: Start isEmpty. Operand 72 states and 105 transitions. [2022-04-15 07:56:30,946 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:30,946 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:30,946 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:56:30,946 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:56:30,947 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 31 states have (on average 1.2580645161290323) internal successors, (39), 33 states have internal predecessors, (39), 32 states have call successors, (32), 6 states have call predecessors, (32), 5 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2022-04-15 07:56:30,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 100 transitions. [2022-04-15 07:56:30,956 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 100 transitions. Word has length 26 [2022-04-15 07:56:30,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:56:30,956 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 100 transitions. [2022-04-15 07:56:30,956 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.0) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-15 07:56:30,956 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 69 states and 100 transitions. [2022-04-15 07:56:31,479 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 100 edges. 100 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:31,479 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 100 transitions. [2022-04-15 07:56:31,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-15 07:56:31,480 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:56:31,480 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:56:31,480 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-15 07:56:31,480 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:56:31,481 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:56:31,481 INFO L85 PathProgramCache]: Analyzing trace with hash -2000886032, now seen corresponding path program 1 times [2022-04-15 07:56:31,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:56:31,481 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1449352894] [2022-04-15 07:56:31,481 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:56:31,481 INFO L85 PathProgramCache]: Analyzing trace with hash -2000886032, now seen corresponding path program 2 times [2022-04-15 07:56:31,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:56:31,482 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [897447589] [2022-04-15 07:56:31,482 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:56:31,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:56:31,492 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:56:31,492 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1467933473] [2022-04-15 07:56:31,492 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 07:56:31,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:56:31,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:56:31,493 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 07:56:31,498 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-15 07:56:31,554 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 07:56:31,554 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 07:56:31,556 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-15 07:56:31,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:56:31,570 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:56:31,796 INFO L272 TraceCheckUtils]: 0: Hoare triple {1149#true} call ULTIMATE.init(); {1149#true} is VALID [2022-04-15 07:56:31,796 INFO L290 TraceCheckUtils]: 1: Hoare triple {1149#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {1149#true} is VALID [2022-04-15 07:56:31,796 INFO L290 TraceCheckUtils]: 2: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-15 07:56:31,797 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1149#true} {1149#true} #103#return; {1149#true} is VALID [2022-04-15 07:56:31,797 INFO L272 TraceCheckUtils]: 4: Hoare triple {1149#true} call #t~ret5 := main(); {1149#true} is VALID [2022-04-15 07:56:31,797 INFO L290 TraceCheckUtils]: 5: Hoare triple {1149#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1149#true} is VALID [2022-04-15 07:56:31,797 INFO L272 TraceCheckUtils]: 6: Hoare triple {1149#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 100 then 1 else 0)); {1149#true} is VALID [2022-04-15 07:56:31,797 INFO L290 TraceCheckUtils]: 7: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-15 07:56:31,798 INFO L290 TraceCheckUtils]: 8: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-15 07:56:31,798 INFO L290 TraceCheckUtils]: 9: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-15 07:56:31,799 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1149#true} {1149#true} #81#return; {1149#true} is VALID [2022-04-15 07:56:31,801 INFO L272 TraceCheckUtils]: 11: Hoare triple {1149#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1149#true} is VALID [2022-04-15 07:56:31,801 INFO L290 TraceCheckUtils]: 12: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-15 07:56:31,802 INFO L290 TraceCheckUtils]: 13: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-15 07:56:31,811 INFO L290 TraceCheckUtils]: 14: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-15 07:56:31,811 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1149#true} {1149#true} #83#return; {1149#true} is VALID [2022-04-15 07:56:31,815 INFO L290 TraceCheckUtils]: 16: Hoare triple {1149#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 07:56:31,816 INFO L290 TraceCheckUtils]: 17: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 07:56:31,816 INFO L290 TraceCheckUtils]: 18: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 07:56:31,817 INFO L290 TraceCheckUtils]: 19: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} assume !false; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 07:56:31,817 INFO L272 TraceCheckUtils]: 20: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1149#true} is VALID [2022-04-15 07:56:31,817 INFO L290 TraceCheckUtils]: 21: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-15 07:56:31,817 INFO L290 TraceCheckUtils]: 22: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-15 07:56:31,817 INFO L290 TraceCheckUtils]: 23: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-15 07:56:31,818 INFO L284 TraceCheckUtils]: 24: Hoare quadruple {1149#true} {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #85#return; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 07:56:31,818 INFO L272 TraceCheckUtils]: 25: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {1149#true} is VALID [2022-04-15 07:56:31,818 INFO L290 TraceCheckUtils]: 26: Hoare triple {1149#true} ~cond := #in~cond; {1149#true} is VALID [2022-04-15 07:56:31,818 INFO L290 TraceCheckUtils]: 27: Hoare triple {1149#true} assume !(0 == ~cond); {1149#true} is VALID [2022-04-15 07:56:31,818 INFO L290 TraceCheckUtils]: 28: Hoare triple {1149#true} assume true; {1149#true} is VALID [2022-04-15 07:56:31,819 INFO L284 TraceCheckUtils]: 29: Hoare quadruple {1149#true} {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} #87#return; {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} is VALID [2022-04-15 07:56:31,819 INFO L272 TraceCheckUtils]: 30: Hoare triple {1202#(and (= main_~p~0 0) (= main_~h~0 0) (= main_~q~0 1))} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {1245#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 07:56:31,820 INFO L290 TraceCheckUtils]: 31: Hoare triple {1245#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1249#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 07:56:31,820 INFO L290 TraceCheckUtils]: 32: Hoare triple {1249#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1150#false} is VALID [2022-04-15 07:56:31,820 INFO L290 TraceCheckUtils]: 33: Hoare triple {1150#false} assume !false; {1150#false} is VALID [2022-04-15 07:56:31,820 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-04-15 07:56:31,820 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:56:31,821 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:56:31,821 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [897447589] [2022-04-15 07:56:31,821 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:56:31,821 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1467933473] [2022-04-15 07:56:31,821 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1467933473] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:56:31,821 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:56:31,821 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:56:31,822 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:56:31,822 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1449352894] [2022-04-15 07:56:31,822 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1449352894] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:56:31,822 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:56:31,822 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:56:31,822 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1746271973] [2022-04-15 07:56:31,822 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:56:31,822 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-04-15 07:56:31,823 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:56:31,823 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:31,844 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 28 edges. 28 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:31,844 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 07:56:31,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:56:31,845 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 07:56:31,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 07:56:31,846 INFO L87 Difference]: Start difference. First operand 69 states and 100 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:34,115 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 07:56:40,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:40,294 INFO L93 Difference]: Finished difference Result 80 states and 109 transitions. [2022-04-15 07:56:40,295 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 07:56:40,295 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-04-15 07:56:40,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:56:40,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:40,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 07:56:40,297 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:40,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 67 transitions. [2022-04-15 07:56:40,298 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 67 transitions. [2022-04-15 07:56:40,354 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 67 edges. 67 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:40,356 INFO L225 Difference]: With dead ends: 80 [2022-04-15 07:56:40,356 INFO L226 Difference]: Without dead ends: 57 [2022-04-15 07:56:40,356 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 07:56:40,357 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 6 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 2 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2022-04-15 07:56:40,357 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 144 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 54 Invalid, 1 Unknown, 0 Unchecked, 2.5s Time] [2022-04-15 07:56:40,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states. [2022-04-15 07:56:40,386 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 57. [2022-04-15 07:56:40,386 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:56:40,386 INFO L82 GeneralOperation]: Start isEquivalent. First operand 57 states. Second operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-15 07:56:40,387 INFO L74 IsIncluded]: Start isIncluded. First operand 57 states. Second operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-15 07:56:40,387 INFO L87 Difference]: Start difference. First operand 57 states. Second operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-15 07:56:40,389 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:40,390 INFO L93 Difference]: Finished difference Result 57 states and 82 transitions. [2022-04-15 07:56:40,390 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 82 transitions. [2022-04-15 07:56:40,390 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:40,390 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:40,391 INFO L74 IsIncluded]: Start isIncluded. First operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand 57 states. [2022-04-15 07:56:40,391 INFO L87 Difference]: Start difference. First operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) Second operand 57 states. [2022-04-15 07:56:40,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:40,393 INFO L93 Difference]: Finished difference Result 57 states and 82 transitions. [2022-04-15 07:56:40,393 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 82 transitions. [2022-04-15 07:56:40,394 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:40,394 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:40,394 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:56:40,394 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:56:40,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 26 states have call successors, (26), 5 states have call predecessors, (26), 4 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-04-15 07:56:40,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 82 transitions. [2022-04-15 07:56:40,397 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 82 transitions. Word has length 34 [2022-04-15 07:56:40,397 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:56:40,397 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 82 transitions. [2022-04-15 07:56:40,397 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:40,397 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 57 states and 82 transitions. [2022-04-15 07:56:40,683 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 82 edges. 82 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:40,683 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 82 transitions. [2022-04-15 07:56:40,684 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-15 07:56:40,684 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:56:40,684 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:56:40,694 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-15 07:56:40,890 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:56:40,891 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:56:40,891 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:56:40,891 INFO L85 PathProgramCache]: Analyzing trace with hash -965267381, now seen corresponding path program 1 times [2022-04-15 07:56:40,891 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:56:40,891 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [205338853] [2022-04-15 07:56:40,891 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:56:40,891 INFO L85 PathProgramCache]: Analyzing trace with hash -965267381, now seen corresponding path program 2 times [2022-04-15 07:56:40,892 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:56:40,892 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1118745518] [2022-04-15 07:56:40,892 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:56:40,892 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:56:40,903 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:56:40,903 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1634444174] [2022-04-15 07:56:40,903 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 07:56:40,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:56:40,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:56:40,904 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 07:56:40,905 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-15 07:56:40,966 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-15 07:56:40,966 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-15 07:56:40,967 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-15 07:56:40,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-15 07:56:40,980 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-15 07:56:41,089 INFO L272 TraceCheckUtils]: 0: Hoare triple {1645#true} call ULTIMATE.init(); {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L290 TraceCheckUtils]: 1: Hoare triple {1645#true} #NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(13, 2);call #Ultimate.allocInit(12, 3); {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L290 TraceCheckUtils]: 2: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L284 TraceCheckUtils]: 3: Hoare quadruple {1645#true} {1645#true} #103#return; {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L272 TraceCheckUtils]: 4: Hoare triple {1645#true} call #t~ret5 := main(); {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L290 TraceCheckUtils]: 5: Hoare triple {1645#true} havoc ~n~0;havoc ~p~0;havoc ~q~0;havoc ~r~0;havoc ~h~0;~n~0 := #t~nondet4;havoc #t~nondet4; {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L272 TraceCheckUtils]: 6: Hoare triple {1645#true} call assume_abort_if_not((if ~n~0 % 4294967296 >= 0 && ~n~0 % 4294967296 <= 100 then 1 else 0)); {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L290 TraceCheckUtils]: 7: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-15 07:56:41,090 INFO L290 TraceCheckUtils]: 8: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L290 TraceCheckUtils]: 9: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L284 TraceCheckUtils]: 10: Hoare quadruple {1645#true} {1645#true} #81#return; {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L272 TraceCheckUtils]: 11: Hoare triple {1645#true} call assume_abort_if_not((if ~n~0 % 4294967296 < 1073741823 then 1 else 0)); {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L290 TraceCheckUtils]: 12: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L290 TraceCheckUtils]: 13: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L290 TraceCheckUtils]: 14: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L284 TraceCheckUtils]: 15: Hoare quadruple {1645#true} {1645#true} #83#return; {1645#true} is VALID [2022-04-15 07:56:41,091 INFO L290 TraceCheckUtils]: 16: Hoare triple {1645#true} ~p~0 := 0;~q~0 := 1;~r~0 := ~n~0;~h~0 := 0; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,092 INFO L290 TraceCheckUtils]: 17: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,092 INFO L290 TraceCheckUtils]: 18: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !!(~q~0 % 4294967296 <= ~n~0 % 4294967296);~q~0 := 4 * ~q~0; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,092 INFO L290 TraceCheckUtils]: 19: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,093 INFO L290 TraceCheckUtils]: 20: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !(~q~0 % 4294967296 <= ~n~0 % 4294967296); {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,093 INFO L290 TraceCheckUtils]: 21: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} assume !false; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,093 INFO L272 TraceCheckUtils]: 22: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if ~r~0 % 4294967296 < (2 * ~p~0 + ~q~0) % 4294967296 then 1 else 0)); {1645#true} is VALID [2022-04-15 07:56:41,093 INFO L290 TraceCheckUtils]: 23: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-15 07:56:41,094 INFO L290 TraceCheckUtils]: 24: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-15 07:56:41,094 INFO L290 TraceCheckUtils]: 25: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-15 07:56:41,097 INFO L284 TraceCheckUtils]: 26: Hoare quadruple {1645#true} {1698#(and (= main_~p~0 0) (= main_~h~0 0))} #85#return; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,097 INFO L272 TraceCheckUtils]: 27: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if (~p~0 * ~p~0 + ~r~0 * ~q~0) % 4294967296 == ~n~0 * ~q~0 % 4294967296 then 1 else 0)); {1645#true} is VALID [2022-04-15 07:56:41,097 INFO L290 TraceCheckUtils]: 28: Hoare triple {1645#true} ~cond := #in~cond; {1645#true} is VALID [2022-04-15 07:56:41,097 INFO L290 TraceCheckUtils]: 29: Hoare triple {1645#true} assume !(0 == ~cond); {1645#true} is VALID [2022-04-15 07:56:41,097 INFO L290 TraceCheckUtils]: 30: Hoare triple {1645#true} assume true; {1645#true} is VALID [2022-04-15 07:56:41,098 INFO L284 TraceCheckUtils]: 31: Hoare quadruple {1645#true} {1698#(and (= main_~p~0 0) (= main_~h~0 0))} #87#return; {1698#(and (= main_~p~0 0) (= main_~h~0 0))} is VALID [2022-04-15 07:56:41,099 INFO L272 TraceCheckUtils]: 32: Hoare triple {1698#(and (= main_~p~0 0) (= main_~h~0 0))} call __VERIFIER_assert((if 0 == (~h~0 * ~h~0 * ~h~0 - 12 * ~h~0 * ~n~0 * ~q~0 + 16 * ~n~0 * ~p~0 * ~q~0 - ~h~0 * ~q~0 * ~q~0 - 4 * ~p~0 * ~q~0 * ~q~0 + 12 * ~h~0 * ~q~0 * ~r~0 - 16 * ~p~0 * ~q~0 * ~r~0) % 4294967296 then 1 else 0)); {1747#(<= 1 |__VERIFIER_assert_#in~cond|)} is VALID [2022-04-15 07:56:41,100 INFO L290 TraceCheckUtils]: 33: Hoare triple {1747#(<= 1 |__VERIFIER_assert_#in~cond|)} ~cond := #in~cond; {1751#(<= 1 __VERIFIER_assert_~cond)} is VALID [2022-04-15 07:56:41,100 INFO L290 TraceCheckUtils]: 34: Hoare triple {1751#(<= 1 __VERIFIER_assert_~cond)} assume 0 == ~cond; {1646#false} is VALID [2022-04-15 07:56:41,100 INFO L290 TraceCheckUtils]: 35: Hoare triple {1646#false} assume !false; {1646#false} is VALID [2022-04-15 07:56:41,100 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-04-15 07:56:41,100 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-15 07:56:41,100 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-15 07:56:41,101 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1118745518] [2022-04-15 07:56:41,101 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-15 07:56:41,101 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1634444174] [2022-04-15 07:56:41,101 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1634444174] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:56:41,102 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:56:41,102 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:56:41,103 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-15 07:56:41,103 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [205338853] [2022-04-15 07:56:41,103 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [205338853] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-15 07:56:41,103 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-15 07:56:41,103 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-15 07:56:41,103 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1074349814] [2022-04-15 07:56:41,103 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-15 07:56:41,104 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-15 07:56:41,104 INFO L84 Accepts]: Finished accepts. word is accepted. [2022-04-15 07:56:41,104 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:41,125 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 29 edges. 29 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:41,125 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-15 07:56:41,125 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-15 07:56:41,126 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-15 07:56:41,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-15 07:56:41,126 INFO L87 Difference]: Start difference. First operand 57 states and 82 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:48,735 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-15 07:56:50,743 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:50,743 INFO L93 Difference]: Finished difference Result 70 states and 95 transitions. [2022-04-15 07:56:50,743 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-15 07:56:50,743 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-04-15 07:56:50,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-15 07:56:50,743 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:50,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 69 transitions. [2022-04-15 07:56:50,756 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:50,757 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 69 transitions. [2022-04-15 07:56:50,757 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 5 states and 69 transitions. [2022-04-15 07:56:50,827 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 69 edges. 69 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:50,828 INFO L225 Difference]: With dead ends: 70 [2022-04-15 07:56:50,828 INFO L226 Difference]: Without dead ends: 67 [2022-04-15 07:56:50,829 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-15 07:56:50,830 INFO L913 BasicCegarLoop]: 49 mSDtfsCounter, 6 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 3 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2022-04-15 07:56:50,830 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 151 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 50 Invalid, 1 Unknown, 0 Unchecked, 2.6s Time] [2022-04-15 07:56:50,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-04-15 07:56:50,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2022-04-15 07:56:50,854 INFO L214 AbstractMinimizeNwa]: Start testing correctness of minimizeSevpa [2022-04-15 07:56:50,854 INFO L82 GeneralOperation]: Start isEquivalent. First operand 67 states. Second operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-15 07:56:50,855 INFO L74 IsIncluded]: Start isIncluded. First operand 67 states. Second operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-15 07:56:50,855 INFO L87 Difference]: Start difference. First operand 67 states. Second operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-15 07:56:50,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:50,857 INFO L93 Difference]: Finished difference Result 67 states and 91 transitions. [2022-04-15 07:56:50,857 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2022-04-15 07:56:50,858 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:50,858 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:50,858 INFO L74 IsIncluded]: Start isIncluded. First operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand 67 states. [2022-04-15 07:56:50,858 INFO L87 Difference]: Start difference. First operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand 67 states. [2022-04-15 07:56:50,860 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-15 07:56:50,861 INFO L93 Difference]: Finished difference Result 67 states and 91 transitions. [2022-04-15 07:56:50,861 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2022-04-15 07:56:50,861 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-15 07:56:50,861 INFO L83 IsIncluded]: Finished isIncluded. Language is included [2022-04-15 07:56:50,861 INFO L88 GeneralOperation]: Finished isEquivalent. [2022-04-15 07:56:50,861 INFO L221 AbstractMinimizeNwa]: Finished testing correctness of minimizeSevpa [2022-04-15 07:56:50,861 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 28 states have call successors, (28), 7 states have call predecessors, (28), 6 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-15 07:56:50,863 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 91 transitions. [2022-04-15 07:56:50,863 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 91 transitions. Word has length 36 [2022-04-15 07:56:50,863 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-15 07:56:50,864 INFO L478 AbstractCegarLoop]: Abstraction has 67 states and 91 transitions. [2022-04-15 07:56:50,864 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-15 07:56:50,864 INFO L86 InductivityCheck]: Starting inductivity check of a Floyd-Hoare automaton with 67 states and 91 transitions. [2022-04-15 07:56:51,195 INFO L122 InductivityCheck]: Floyd-Hoare automaton has 91 edges. 91 inductive. 0 not inductive. 0 times theorem prover too weak to decide inductivity. [2022-04-15 07:56:51,196 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 91 transitions. [2022-04-15 07:56:51,198 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2022-04-15 07:56:51,198 INFO L491 BasicCegarLoop]: Found error trace [2022-04-15 07:56:51,198 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-15 07:56:51,204 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-15 07:56:51,401 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:56:51,402 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-15 07:56:51,402 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-15 07:56:51,402 INFO L85 PathProgramCache]: Analyzing trace with hash 1670386034, now seen corresponding path program 1 times [2022-04-15 07:56:51,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-15 07:56:51,402 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1413713870] [2022-04-15 07:56:51,403 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-15 07:56:51,403 INFO L85 PathProgramCache]: Analyzing trace with hash 1670386034, now seen corresponding path program 2 times [2022-04-15 07:56:51,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-15 07:56:51,403 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [522590067] [2022-04-15 07:56:51,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-15 07:56:51,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-15 07:56:51,424 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-15 07:56:51,424 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [608909676] [2022-04-15 07:56:51,424 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-15 07:56:51,429 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-15 07:56:51,430 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-15 07:56:51,430 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-15 07:56:51,431 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process