./Ultimate.py --spec ../sv-benchmarks/c/properties/no-overflow.prp --file ../sv-benchmarks/c/recursive/MultCommutative-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for overflows Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive/MultCommutative-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! overflow) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ce29b37e076ab683230ebf17073db3b7759ea39570dd2ef64322b6d43bb636cd --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-10 19:37:26,828 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-10 19:37:26,909 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Overflow-32bit-Automizer_Default.epf [2024-11-10 19:37:26,915 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-10 19:37:26,915 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-10 19:37:26,942 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-10 19:37:26,943 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-10 19:37:26,943 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-10 19:37:26,944 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-10 19:37:26,945 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-10 19:37:26,945 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-10 19:37:26,945 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-10 19:37:26,946 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-10 19:37:26,948 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-10 19:37:26,948 INFO L153 SettingsManager]: * Use SBE=true [2024-11-10 19:37:26,949 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-10 19:37:26,949 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-10 19:37:26,949 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-10 19:37:26,950 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-10 19:37:26,950 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-10 19:37:26,950 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-10 19:37:26,954 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-10 19:37:26,954 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-10 19:37:26,955 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-10 19:37:26,955 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-10 19:37:26,955 INFO L153 SettingsManager]: * Check absence of signed integer overflows=ASSERTandASSUME [2024-11-10 19:37:26,955 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-10 19:37:26,955 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-10 19:37:26,955 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-10 19:37:26,956 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-10 19:37:26,956 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-10 19:37:26,956 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-10 19:37:26,956 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-10 19:37:26,956 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-10 19:37:26,957 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-10 19:37:26,957 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-10 19:37:26,958 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-10 19:37:26,958 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-10 19:37:26,958 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-10 19:37:26,959 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-10 19:37:26,959 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-10 19:37:26,960 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-10 19:37:26,961 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-10 19:37:26,961 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-10 19:37:26,961 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! overflow) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> ce29b37e076ab683230ebf17073db3b7759ea39570dd2ef64322b6d43bb636cd [2024-11-10 19:37:27,223 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-10 19:37:27,249 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-10 19:37:27,253 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-10 19:37:27,255 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-10 19:37:27,255 INFO L274 PluginConnector]: CDTParser initialized [2024-11-10 19:37:27,256 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/MultCommutative-2.c [2024-11-10 19:37:28,838 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-10 19:37:29,023 INFO L384 CDTParser]: Found 1 translation units. [2024-11-10 19:37:29,023 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/MultCommutative-2.c [2024-11-10 19:37:29,030 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/657e9e34b/e5319e6f7ac041beb6182f623b4e11fb/FLAG7eb9ab3ad [2024-11-10 19:37:29,044 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/657e9e34b/e5319e6f7ac041beb6182f623b4e11fb [2024-11-10 19:37:29,046 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-10 19:37:29,048 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-10 19:37:29,049 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-10 19:37:29,049 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-10 19:37:29,054 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-10 19:37:29,055 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,056 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@37f6762e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29, skipping insertion in model container [2024-11-10 19:37:29,056 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,079 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-10 19:37:29,278 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 19:37:29,290 INFO L200 MainTranslator]: Completed pre-run [2024-11-10 19:37:29,305 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 19:37:29,319 INFO L204 MainTranslator]: Completed translation [2024-11-10 19:37:29,319 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29 WrapperNode [2024-11-10 19:37:29,320 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-10 19:37:29,321 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-10 19:37:29,321 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-10 19:37:29,321 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-10 19:37:29,328 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,335 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,350 INFO L138 Inliner]: procedures = 13, calls = 12, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 38 [2024-11-10 19:37:29,350 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-10 19:37:29,351 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-10 19:37:29,351 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-10 19:37:29,351 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-10 19:37:29,359 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,359 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,360 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,376 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-10 19:37:29,376 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,376 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,379 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,379 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,380 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,381 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,382 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-10 19:37:29,383 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-10 19:37:29,383 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-10 19:37:29,384 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-10 19:37:29,384 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (1/1) ... [2024-11-10 19:37:29,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-10 19:37:29,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:29,448 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-10 19:37:29,452 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-10 19:37:29,514 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-10 19:37:29,514 INFO L130 BoogieDeclarations]: Found specification of procedure mult [2024-11-10 19:37:29,514 INFO L138 BoogieDeclarations]: Found implementation of procedure mult [2024-11-10 19:37:29,514 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-10 19:37:29,514 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-10 19:37:29,515 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-10 19:37:29,577 INFO L256 CfgBuilder]: Building ICFG [2024-11-10 19:37:29,579 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-10 19:37:29,674 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L24: havoc #t~ret5; [2024-11-10 19:37:29,674 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L19: havoc #t~ret4; [2024-11-10 19:37:29,736 INFO L? ?]: Removed 22 outVars from TransFormulas that were not future-live. [2024-11-10 19:37:29,736 INFO L307 CfgBuilder]: Performing block encoding [2024-11-10 19:37:29,759 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-10 19:37:29,760 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-10 19:37:29,760 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 07:37:29 BoogieIcfgContainer [2024-11-10 19:37:29,760 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-10 19:37:29,762 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-10 19:37:29,763 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-10 19:37:29,767 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-10 19:37:29,768 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 10.11 07:37:29" (1/3) ... [2024-11-10 19:37:29,769 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@165bf862 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.11 07:37:29, skipping insertion in model container [2024-11-10 19:37:29,769 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 07:37:29" (2/3) ... [2024-11-10 19:37:29,771 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@165bf862 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.11 07:37:29, skipping insertion in model container [2024-11-10 19:37:29,771 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 07:37:29" (3/3) ... [2024-11-10 19:37:29,772 INFO L112 eAbstractionObserver]: Analyzing ICFG MultCommutative-2.c [2024-11-10 19:37:29,790 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-10 19:37:29,790 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 6 error locations. [2024-11-10 19:37:29,854 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-10 19:37:29,862 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@3ae7e951, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-10 19:37:29,862 INFO L334 AbstractCegarLoop]: Starting to check reachability of 6 error locations. [2024-11-10 19:37:29,868 INFO L276 IsEmpty]: Start isEmpty. Operand has 36 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 30 states have internal predecessors, (35), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-10 19:37:29,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-10 19:37:29,876 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:29,877 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:29,878 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting multErr5ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:29,884 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:29,885 INFO L85 PathProgramCache]: Analyzing trace with hash -1687091907, now seen corresponding path program 1 times [2024-11-10 19:37:29,898 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:29,899 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [462495057] [2024-11-10 19:37:29,899 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:29,899 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:30,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:30,129 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:30,130 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:30,130 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [462495057] [2024-11-10 19:37:30,133 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [462495057] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 19:37:30,133 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 19:37:30,133 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-10 19:37:30,135 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1421776534] [2024-11-10 19:37:30,136 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 19:37:30,140 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-10 19:37:30,141 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:30,167 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-10 19:37:30,168 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-10 19:37:30,171 INFO L87 Difference]: Start difference. First operand has 36 states, 24 states have (on average 1.4583333333333333) internal successors, (35), 30 states have internal predecessors, (35), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,232 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:30,233 INFO L93 Difference]: Finished difference Result 41 states and 50 transitions. [2024-11-10 19:37:30,234 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-10 19:37:30,236 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-10 19:37:30,236 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:30,242 INFO L225 Difference]: With dead ends: 41 [2024-11-10 19:37:30,242 INFO L226 Difference]: Without dead ends: 30 [2024-11-10 19:37:30,245 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-10 19:37:30,250 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 4 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 71 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:30,252 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 71 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-10 19:37:30,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-11-10 19:37:30,289 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 28. [2024-11-10 19:37:30,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 23 states have internal predecessors, (25), 4 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-10 19:37:30,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 32 transitions. [2024-11-10 19:37:30,292 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 32 transitions. Word has length 8 [2024-11-10 19:37:30,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:30,293 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 32 transitions. [2024-11-10 19:37:30,293 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 3.5) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,293 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 32 transitions. [2024-11-10 19:37:30,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-10 19:37:30,294 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:30,294 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:30,294 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-10 19:37:30,294 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting multErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:30,295 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:30,295 INFO L85 PathProgramCache]: Analyzing trace with hash -760241578, now seen corresponding path program 1 times [2024-11-10 19:37:30,295 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:30,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [996403285] [2024-11-10 19:37:30,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:30,295 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:30,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:30,407 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:30,407 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:30,408 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [996403285] [2024-11-10 19:37:30,408 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [996403285] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 19:37:30,408 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 19:37:30,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-10 19:37:30,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1492570254] [2024-11-10 19:37:30,408 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 19:37:30,409 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-10 19:37:30,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:30,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-10 19:37:30,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-10 19:37:30,410 INFO L87 Difference]: Start difference. First operand 28 states and 32 transitions. Second operand has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:30,516 INFO L93 Difference]: Finished difference Result 69 states and 83 transitions. [2024-11-10 19:37:30,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 19:37:30,517 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-10 19:37:30,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:30,519 INFO L225 Difference]: With dead ends: 69 [2024-11-10 19:37:30,520 INFO L226 Difference]: Without dead ends: 46 [2024-11-10 19:37:30,521 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-10 19:37:30,522 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 36 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:30,523 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 82 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:30,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-10 19:37:30,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 39. [2024-11-10 19:37:30,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 28 states have (on average 1.3571428571428572) internal successors, (38), 32 states have internal predecessors, (38), 5 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-10 19:37:30,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 47 transitions. [2024-11-10 19:37:30,539 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 47 transitions. Word has length 9 [2024-11-10 19:37:30,539 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:30,540 INFO L471 AbstractCegarLoop]: Abstraction has 39 states and 47 transitions. [2024-11-10 19:37:30,540 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,540 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 47 transitions. [2024-11-10 19:37:30,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-10 19:37:30,541 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:30,541 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:30,541 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-10 19:37:30,541 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:30,542 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:30,542 INFO L85 PathProgramCache]: Analyzing trace with hash -2092628652, now seen corresponding path program 1 times [2024-11-10 19:37:30,542 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:30,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2089908211] [2024-11-10 19:37:30,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:30,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:30,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:30,630 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:30,631 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:30,631 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2089908211] [2024-11-10 19:37:30,631 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2089908211] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 19:37:30,631 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 19:37:30,631 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-10 19:37:30,631 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1452416944] [2024-11-10 19:37:30,632 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 19:37:30,632 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-10 19:37:30,632 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:30,633 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-10 19:37:30,633 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-10 19:37:30,633 INFO L87 Difference]: Start difference. First operand 39 states and 47 transitions. Second operand has 5 states, 3 states have (on average 3.0) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,750 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:30,751 INFO L93 Difference]: Finished difference Result 65 states and 79 transitions. [2024-11-10 19:37:30,751 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 19:37:30,751 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 3 states have (on average 3.0) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-10 19:37:30,752 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:30,753 INFO L225 Difference]: With dead ends: 65 [2024-11-10 19:37:30,753 INFO L226 Difference]: Without dead ends: 64 [2024-11-10 19:37:30,754 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-10 19:37:30,755 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 34 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:30,755 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 85 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:30,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-10 19:37:30,769 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 55. [2024-11-10 19:37:30,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 41 states have (on average 1.3414634146341464) internal successors, (55), 45 states have internal predecessors, (55), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-10 19:37:30,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2024-11-10 19:37:30,773 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 10 [2024-11-10 19:37:30,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:30,774 INFO L471 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2024-11-10 19:37:30,774 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 3 states have (on average 3.0) internal successors, (9), 4 states have internal predecessors, (9), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,774 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2024-11-10 19:37:30,775 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-10 19:37:30,775 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:30,775 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:30,775 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-10 19:37:30,775 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting multErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:30,776 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:30,776 INFO L85 PathProgramCache]: Analyzing trace with hash -666151560, now seen corresponding path program 1 times [2024-11-10 19:37:30,776 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:30,777 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1753578169] [2024-11-10 19:37:30,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:30,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:30,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:30,853 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:30,854 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:30,854 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1753578169] [2024-11-10 19:37:30,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1753578169] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 19:37:30,855 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 19:37:30,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-10 19:37:30,855 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2125173297] [2024-11-10 19:37:30,855 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 19:37:30,856 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-10 19:37:30,856 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:30,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-10 19:37:30,857 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-10 19:37:30,858 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:30,974 INFO L93 Difference]: Finished difference Result 87 states and 109 transitions. [2024-11-10 19:37:30,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 19:37:30,975 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 15 [2024-11-10 19:37:30,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:30,977 INFO L225 Difference]: With dead ends: 87 [2024-11-10 19:37:30,977 INFO L226 Difference]: Without dead ends: 86 [2024-11-10 19:37:30,977 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2024-11-10 19:37:30,979 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 28 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:30,979 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 87 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:30,980 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-10 19:37:30,994 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 71. [2024-11-10 19:37:30,995 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 54 states have (on average 1.3333333333333333) internal successors, (72), 58 states have internal predecessors, (72), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-10 19:37:30,997 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 89 transitions. [2024-11-10 19:37:30,998 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 89 transitions. Word has length 15 [2024-11-10 19:37:30,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:30,998 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 89 transitions. [2024-11-10 19:37:30,998 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:30,999 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 89 transitions. [2024-11-10 19:37:30,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-10 19:37:30,999 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:30,999 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:31,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-10 19:37:31,000 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting multErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:31,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:31,000 INFO L85 PathProgramCache]: Analyzing trace with hash -2098056161, now seen corresponding path program 1 times [2024-11-10 19:37:31,001 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:31,001 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2107088632] [2024-11-10 19:37:31,001 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:31,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:31,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:31,074 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:31,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:31,089 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:31,093 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:31,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2107088632] [2024-11-10 19:37:31,094 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2107088632] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 19:37:31,094 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 19:37:31,094 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-10 19:37:31,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1254394738] [2024-11-10 19:37:31,094 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 19:37:31,095 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-10 19:37:31,095 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:31,096 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-10 19:37:31,096 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-10 19:37:31,096 INFO L87 Difference]: Start difference. First operand 71 states and 89 transitions. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-10 19:37:31,186 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:31,186 INFO L93 Difference]: Finished difference Result 132 states and 165 transitions. [2024-11-10 19:37:31,187 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 19:37:31,187 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2024-11-10 19:37:31,188 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:31,190 INFO L225 Difference]: With dead ends: 132 [2024-11-10 19:37:31,191 INFO L226 Difference]: Without dead ends: 91 [2024-11-10 19:37:31,193 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-10 19:37:31,194 INFO L432 NwaCegarLoop]: 41 mSDtfsCounter, 24 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 43 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 43 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:31,198 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 116 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 43 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:31,199 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-11-10 19:37:31,210 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 80. [2024-11-10 19:37:31,211 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 62 states have (on average 1.3225806451612903) internal successors, (82), 65 states have internal predecessors, (82), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-10 19:37:31,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 101 transitions. [2024-11-10 19:37:31,212 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 101 transitions. Word has length 16 [2024-11-10 19:37:31,212 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:31,212 INFO L471 AbstractCegarLoop]: Abstraction has 80 states and 101 transitions. [2024-11-10 19:37:31,213 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-10 19:37:31,213 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 101 transitions. [2024-11-10 19:37:31,213 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2024-11-10 19:37:31,213 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:31,214 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:31,214 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-10 19:37:31,214 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:31,214 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:31,215 INFO L85 PathProgramCache]: Analyzing trace with hash -615207765, now seen corresponding path program 1 times [2024-11-10 19:37:31,215 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:31,215 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1172376664] [2024-11-10 19:37:31,215 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:31,215 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:31,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:31,311 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:31,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:31,327 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:31,327 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:31,327 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1172376664] [2024-11-10 19:37:31,327 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1172376664] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 19:37:31,328 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 19:37:31,328 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-10 19:37:31,328 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [394758611] [2024-11-10 19:37:31,328 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 19:37:31,333 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-10 19:37:31,333 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:31,333 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-10 19:37:31,334 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-10 19:37:31,334 INFO L87 Difference]: Start difference. First operand 80 states and 101 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-10 19:37:31,446 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:31,447 INFO L93 Difference]: Finished difference Result 107 states and 137 transitions. [2024-11-10 19:37:31,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 19:37:31,451 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 17 [2024-11-10 19:37:31,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:31,452 INFO L225 Difference]: With dead ends: 107 [2024-11-10 19:37:31,452 INFO L226 Difference]: Without dead ends: 106 [2024-11-10 19:37:31,453 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-10 19:37:31,454 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 28 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:31,457 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [29 Valid, 127 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:31,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 106 states. [2024-11-10 19:37:31,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 106 to 96. [2024-11-10 19:37:31,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 75 states have (on average 1.3066666666666666) internal successors, (98), 78 states have internal predecessors, (98), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-10 19:37:31,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 121 transitions. [2024-11-10 19:37:31,471 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 121 transitions. Word has length 17 [2024-11-10 19:37:31,471 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:31,472 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 121 transitions. [2024-11-10 19:37:31,472 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-10 19:37:31,472 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 121 transitions. [2024-11-10 19:37:31,472 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-10 19:37:31,472 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:31,473 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:31,473 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-10 19:37:31,473 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:31,473 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:31,473 INFO L85 PathProgramCache]: Analyzing trace with hash 1745139464, now seen corresponding path program 1 times [2024-11-10 19:37:31,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:31,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [489892421] [2024-11-10 19:37:31,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:31,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:31,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:31,578 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-10 19:37:31,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:31,623 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:31,623 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:31,623 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [489892421] [2024-11-10 19:37:31,623 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [489892421] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:31,623 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2039650032] [2024-11-10 19:37:31,623 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:31,624 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:31,624 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:31,627 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) [2024-11-10 19:37:31,629 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-10 19:37:31,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:31,672 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-10 19:37:31,677 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:31,771 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:31,773 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:31,842 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:31,842 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2039650032] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:31,842 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:31,842 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 5] total 8 [2024-11-10 19:37:31,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1257642758] [2024-11-10 19:37:31,843 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:31,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-10 19:37:31,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:31,844 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-10 19:37:31,844 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-11-10 19:37:31,844 INFO L87 Difference]: Start difference. First operand 96 states and 121 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-10 19:37:32,007 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:32,007 INFO L93 Difference]: Finished difference Result 168 states and 222 transitions. [2024-11-10 19:37:32,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-10 19:37:32,009 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-11-10 19:37:32,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:32,013 INFO L225 Difference]: With dead ends: 168 [2024-11-10 19:37:32,013 INFO L226 Difference]: Without dead ends: 167 [2024-11-10 19:37:32,013 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 33 SyntacticMatches, 3 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=110, Unknown=0, NotChecked=0, Total=156 [2024-11-10 19:37:32,014 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 41 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 76 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 86 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 76 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:32,015 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 140 Invalid, 86 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:32,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2024-11-10 19:37:32,039 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 128. [2024-11-10 19:37:32,040 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 101 states have (on average 1.297029702970297) internal successors, (131), 104 states have internal predecessors, (131), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-10 19:37:32,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 162 transitions. [2024-11-10 19:37:32,043 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 162 transitions. Word has length 18 [2024-11-10 19:37:32,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:32,043 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 162 transitions. [2024-11-10 19:37:32,044 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 8 states have internal predecessors, (21), 2 states have call successors, (2), 2 states have call predecessors, (2), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-10 19:37:32,044 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 162 transitions. [2024-11-10 19:37:32,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-10 19:37:32,045 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:32,045 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:32,061 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-10 19:37:32,249 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:32,250 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting multErr4ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:32,250 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:32,251 INFO L85 PathProgramCache]: Analyzing trace with hash 2017569494, now seen corresponding path program 1 times [2024-11-10 19:37:32,251 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:32,251 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1391578782] [2024-11-10 19:37:32,251 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:32,251 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:32,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:32,305 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-10 19:37:32,306 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:32,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1391578782] [2024-11-10 19:37:32,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1391578782] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 19:37:32,306 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 19:37:32,306 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 19:37:32,306 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [676523664] [2024-11-10 19:37:32,306 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 19:37:32,307 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-10 19:37:32,307 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:32,307 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-10 19:37:32,307 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-10 19:37:32,308 INFO L87 Difference]: Start difference. First operand 128 states and 162 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:32,370 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:32,371 INFO L93 Difference]: Finished difference Result 173 states and 216 transitions. [2024-11-10 19:37:32,371 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-10 19:37:32,371 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), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 20 [2024-11-10 19:37:32,372 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:32,372 INFO L225 Difference]: With dead ends: 173 [2024-11-10 19:37:32,372 INFO L226 Difference]: Without dead ends: 62 [2024-11-10 19:37:32,373 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 3 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2024-11-10 19:37:32,374 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 27 mSDsluCounter, 28 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 57 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:32,374 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 57 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-10 19:37:32,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-11-10 19:37:32,390 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 54. [2024-11-10 19:37:32,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 43 states have (on average 1.186046511627907) internal successors, (51), 44 states have internal predecessors, (51), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-10 19:37:32,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 62 transitions. [2024-11-10 19:37:32,391 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 62 transitions. Word has length 20 [2024-11-10 19:37:32,391 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:32,392 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 62 transitions. [2024-11-10 19:37:32,392 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-10 19:37:32,392 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 62 transitions. [2024-11-10 19:37:32,396 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-10 19:37:32,397 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:32,398 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:32,398 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-10 19:37:32,398 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:32,399 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:32,399 INFO L85 PathProgramCache]: Analyzing trace with hash -1735251492, now seen corresponding path program 1 times [2024-11-10 19:37:32,399 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:32,399 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [176737901] [2024-11-10 19:37:32,399 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:32,399 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:32,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:32,490 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-10 19:37:32,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:32,518 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:32,519 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:32,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [176737901] [2024-11-10 19:37:32,519 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [176737901] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:32,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1906057024] [2024-11-10 19:37:32,519 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:32,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:32,519 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:32,522 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) [2024-11-10 19:37:32,523 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-10 19:37:32,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:32,565 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 19:37:32,567 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:32,636 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:32,636 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:32,720 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-10 19:37:32,720 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1906057024] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:32,720 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:32,720 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 12 [2024-11-10 19:37:32,720 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [482445931] [2024-11-10 19:37:32,720 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:32,721 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-10 19:37:32,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:32,721 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-10 19:37:32,722 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2024-11-10 19:37:32,722 INFO L87 Difference]: Start difference. First operand 54 states and 62 transitions. Second operand has 13 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 11 states have internal predecessors, (31), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 19:37:32,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:32,855 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2024-11-10 19:37:32,856 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-10 19:37:32,856 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 11 states have internal predecessors, (31), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 19 [2024-11-10 19:37:32,857 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:32,857 INFO L225 Difference]: With dead ends: 70 [2024-11-10 19:37:32,857 INFO L226 Difference]: Without dead ends: 69 [2024-11-10 19:37:32,858 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=68, Invalid=204, Unknown=0, NotChecked=0, Total=272 [2024-11-10 19:37:32,859 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 26 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:32,859 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 138 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:32,860 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2024-11-10 19:37:32,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 62. [2024-11-10 19:37:32,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 50 states have (on average 1.16) internal successors, (58), 50 states have internal predecessors, (58), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (7), 7 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-10 19:37:32,899 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 71 transitions. [2024-11-10 19:37:32,899 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 71 transitions. Word has length 19 [2024-11-10 19:37:32,900 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:32,900 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 71 transitions. [2024-11-10 19:37:32,900 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 11 states have internal predecessors, (31), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 19:37:32,900 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 71 transitions. [2024-11-10 19:37:32,901 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-10 19:37:32,902 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:32,902 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:32,920 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-10 19:37:33,102 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-10 19:37:33,103 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:33,104 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:33,104 INFO L85 PathProgramCache]: Analyzing trace with hash 1220482911, now seen corresponding path program 1 times [2024-11-10 19:37:33,104 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:33,104 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [946662321] [2024-11-10 19:37:33,104 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:33,105 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:33,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,171 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:33,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,179 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-10 19:37:33,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,202 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-10 19:37:33,203 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:33,203 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [946662321] [2024-11-10 19:37:33,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [946662321] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:33,203 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [32610040] [2024-11-10 19:37:33,203 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:33,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:33,203 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:33,207 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) [2024-11-10 19:37:33,209 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-10 19:37:33,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,250 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-10 19:37:33,252 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:33,290 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-10 19:37:33,291 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:33,343 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-10 19:37:33,344 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [32610040] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:33,344 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:33,344 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5, 5] total 8 [2024-11-10 19:37:33,344 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2041659653] [2024-11-10 19:37:33,344 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:33,345 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-10 19:37:33,345 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:33,345 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-10 19:37:33,345 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-11-10 19:37:33,345 INFO L87 Difference]: Start difference. First operand 62 states and 71 transitions. Second operand has 9 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 19:37:33,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:33,433 INFO L93 Difference]: Finished difference Result 74 states and 86 transitions. [2024-11-10 19:37:33,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-10 19:37:33,434 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 25 [2024-11-10 19:37:33,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:33,436 INFO L225 Difference]: With dead ends: 74 [2024-11-10 19:37:33,436 INFO L226 Difference]: Without dead ends: 73 [2024-11-10 19:37:33,437 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 49 SyntacticMatches, 3 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=46, Invalid=110, Unknown=0, NotChecked=0, Total=156 [2024-11-10 19:37:33,437 INFO L432 NwaCegarLoop]: 26 mSDtfsCounter, 31 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:33,438 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 123 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-10 19:37:33,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-10 19:37:33,450 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 61. [2024-11-10 19:37:33,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 50 states have (on average 1.12) internal successors, (56), 49 states have internal predecessors, (56), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (7), 7 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-10 19:37:33,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 69 transitions. [2024-11-10 19:37:33,451 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 69 transitions. Word has length 25 [2024-11-10 19:37:33,451 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:33,451 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 69 transitions. [2024-11-10 19:37:33,452 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.75) internal successors, (22), 8 states have internal predecessors, (22), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 19:37:33,452 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 69 transitions. [2024-11-10 19:37:33,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-10 19:37:33,457 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:33,457 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:33,475 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-10 19:37:33,657 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:33,658 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:33,658 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:33,658 INFO L85 PathProgramCache]: Analyzing trace with hash -819735451, now seen corresponding path program 1 times [2024-11-10 19:37:33,658 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:33,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [936095204] [2024-11-10 19:37:33,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:33,659 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:33,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,727 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:33,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,771 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-10 19:37:33,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,796 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 1 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 19:37:33,800 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:33,800 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [936095204] [2024-11-10 19:37:33,800 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [936095204] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:33,801 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [429929498] [2024-11-10 19:37:33,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:33,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:33,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:33,803 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:33,805 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-10 19:37:33,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:33,853 INFO L255 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 19:37:33,854 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:33,910 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 1 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 19:37:33,910 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:34,011 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 1 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 19:37:34,012 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [429929498] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:34,012 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:34,012 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 7] total 12 [2024-11-10 19:37:34,013 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1425906648] [2024-11-10 19:37:34,013 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:34,014 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-10 19:37:34,014 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:34,014 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-10 19:37:34,014 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2024-11-10 19:37:34,015 INFO L87 Difference]: Start difference. First operand 61 states and 69 transitions. Second operand has 13 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 19:37:34,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:34,201 INFO L93 Difference]: Finished difference Result 98 states and 111 transitions. [2024-11-10 19:37:34,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-10 19:37:34,202 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 26 [2024-11-10 19:37:34,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:34,203 INFO L225 Difference]: With dead ends: 98 [2024-11-10 19:37:34,203 INFO L226 Difference]: Without dead ends: 63 [2024-11-10 19:37:34,204 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 48 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=91, Invalid=289, Unknown=0, NotChecked=0, Total=380 [2024-11-10 19:37:34,204 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 47 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 163 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:34,204 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 96 Invalid, 171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 163 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:34,205 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-10 19:37:34,217 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 61. [2024-11-10 19:37:34,217 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 50 states have (on average 1.1) internal successors, (55), 49 states have internal predecessors, (55), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (7), 7 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-10 19:37:34,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 68 transitions. [2024-11-10 19:37:34,218 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 68 transitions. Word has length 26 [2024-11-10 19:37:34,218 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:34,218 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 68 transitions. [2024-11-10 19:37:34,219 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 12 states have internal predecessors, (35), 3 states have call successors, (3), 2 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-10 19:37:34,219 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 68 transitions. [2024-11-10 19:37:34,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-10 19:37:34,219 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:34,220 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:34,238 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-10 19:37:34,420 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:34,420 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:34,421 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:34,421 INFO L85 PathProgramCache]: Analyzing trace with hash 1929759210, now seen corresponding path program 1 times [2024-11-10 19:37:34,421 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:34,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1600278134] [2024-11-10 19:37:34,422 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:34,422 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:34,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:34,507 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-10 19:37:34,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:34,581 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:34,583 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:34,600 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 19:37:34,600 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:34,600 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1600278134] [2024-11-10 19:37:34,602 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1600278134] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:34,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1107377643] [2024-11-10 19:37:34,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:34,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:34,603 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:34,605 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:34,607 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-10 19:37:34,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:34,650 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-10 19:37:34,652 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:34,765 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 19:37:34,766 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:35,038 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-10 19:37:35,039 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1107377643] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:35,039 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:35,039 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 19 [2024-11-10 19:37:35,039 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2085646571] [2024-11-10 19:37:35,039 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:35,039 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-10 19:37:35,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:35,040 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-10 19:37:35,040 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=317, Unknown=0, NotChecked=0, Total=380 [2024-11-10 19:37:35,041 INFO L87 Difference]: Start difference. First operand 61 states and 68 transitions. Second operand has 20 states, 19 states have (on average 3.0526315789473686) internal successors, (58), 18 states have internal predecessors, (58), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 19:37:35,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:35,361 INFO L93 Difference]: Finished difference Result 99 states and 112 transitions. [2024-11-10 19:37:35,361 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-10 19:37:35,362 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 3.0526315789473686) internal successors, (58), 18 states have internal predecessors, (58), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 31 [2024-11-10 19:37:35,362 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:35,363 INFO L225 Difference]: With dead ends: 99 [2024-11-10 19:37:35,363 INFO L226 Difference]: Without dead ends: 98 [2024-11-10 19:37:35,364 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 54 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 143 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=172, Invalid=758, Unknown=0, NotChecked=0, Total=930 [2024-11-10 19:37:35,364 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 67 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 182 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 182 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:35,365 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 139 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 182 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-10 19:37:35,365 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2024-11-10 19:37:35,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 73. [2024-11-10 19:37:35,376 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 60 states have (on average 1.0833333333333333) internal successors, (65), 59 states have internal predecessors, (65), 6 states have call successors, (6), 4 states have call predecessors, (6), 6 states have return successors, (11), 9 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-10 19:37:35,377 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 82 transitions. [2024-11-10 19:37:35,377 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 82 transitions. Word has length 31 [2024-11-10 19:37:35,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:35,378 INFO L471 AbstractCegarLoop]: Abstraction has 73 states and 82 transitions. [2024-11-10 19:37:35,378 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 3.0526315789473686) internal successors, (58), 18 states have internal predecessors, (58), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 19:37:35,378 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 82 transitions. [2024-11-10 19:37:35,379 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-10 19:37:35,379 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:35,379 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:35,397 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-10 19:37:35,580 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-10 19:37:35,581 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:35,581 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:35,582 INFO L85 PathProgramCache]: Analyzing trace with hash -2000553961, now seen corresponding path program 1 times [2024-11-10 19:37:35,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:35,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2143068109] [2024-11-10 19:37:35,582 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:35,582 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:35,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:35,648 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:35,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:35,681 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:35,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:35,697 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-10 19:37:35,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:35,717 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 23 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-10 19:37:35,717 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:35,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2143068109] [2024-11-10 19:37:35,718 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2143068109] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:35,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1637215547] [2024-11-10 19:37:35,718 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:35,718 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:35,718 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:35,720 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:35,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-10 19:37:35,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:35,770 INFO L255 TraceCheckSpWp]: Trace formula consists of 110 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 19:37:35,772 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:35,869 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 16 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-10 19:37:35,869 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:35,986 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 16 proven. 3 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-10 19:37:35,987 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1637215547] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:35,987 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:35,987 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6, 6] total 18 [2024-11-10 19:37:35,987 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [982569074] [2024-11-10 19:37:35,987 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:35,988 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-10 19:37:35,988 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:35,988 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-10 19:37:35,989 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=288, Unknown=0, NotChecked=0, Total=342 [2024-11-10 19:37:35,989 INFO L87 Difference]: Start difference. First operand 73 states and 82 transitions. Second operand has 19 states, 18 states have (on average 3.3333333333333335) internal successors, (60), 16 states have internal predecessors, (60), 8 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-10 19:37:36,386 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:36,386 INFO L93 Difference]: Finished difference Result 127 states and 142 transitions. [2024-11-10 19:37:36,387 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-10 19:37:36,387 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 3.3333333333333335) internal successors, (60), 16 states have internal predecessors, (60), 8 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) Word has length 38 [2024-11-10 19:37:36,387 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:36,388 INFO L225 Difference]: With dead ends: 127 [2024-11-10 19:37:36,388 INFO L226 Difference]: Without dead ends: 120 [2024-11-10 19:37:36,389 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 72 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=220, Invalid=970, Unknown=0, NotChecked=0, Total=1190 [2024-11-10 19:37:36,390 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 100 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 103 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 294 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:36,390 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [103 Valid, 130 Invalid, 294 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-10 19:37:36,391 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 120 states. [2024-11-10 19:37:36,397 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 120 to 78. [2024-11-10 19:37:36,398 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 64 states have (on average 1.078125) internal successors, (69), 63 states have internal predecessors, (69), 6 states have call successors, (6), 4 states have call predecessors, (6), 7 states have return successors, (12), 10 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-10 19:37:36,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 87 transitions. [2024-11-10 19:37:36,398 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 87 transitions. Word has length 38 [2024-11-10 19:37:36,399 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:36,399 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 87 transitions. [2024-11-10 19:37:36,399 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 3.3333333333333335) internal successors, (60), 16 states have internal predecessors, (60), 8 states have call successors, (11), 4 states have call predecessors, (11), 5 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-10 19:37:36,399 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 87 transitions. [2024-11-10 19:37:36,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-10 19:37:36,401 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:36,401 INFO L215 NwaCegarLoop]: trace histogram [7, 7, 6, 6, 6, 6, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:36,417 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-10 19:37:36,601 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:36,602 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:36,603 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:36,603 INFO L85 PathProgramCache]: Analyzing trace with hash 1888077642, now seen corresponding path program 2 times [2024-11-10 19:37:36,603 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:36,603 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [851200984] [2024-11-10 19:37:36,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:36,604 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:36,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:36,780 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-10 19:37:36,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:36,901 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:36,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:37,006 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:37,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:37,064 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:37,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:37,084 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 0 proven. 102 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-10 19:37:37,084 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:37,084 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [851200984] [2024-11-10 19:37:37,084 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [851200984] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:37,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2092457236] [2024-11-10 19:37:37,085 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-10 19:37:37,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:37,085 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:37,087 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:37,088 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-10 19:37:37,147 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-10 19:37:37,147 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 19:37:37,148 INFO L255 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-10 19:37:37,150 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:37,354 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 0 proven. 102 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-10 19:37:37,354 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:38,215 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 10 proven. 102 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-10 19:37:38,216 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2092457236] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:38,216 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:38,216 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 14] total 30 [2024-11-10 19:37:38,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1066741558] [2024-11-10 19:37:38,217 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:38,217 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-10 19:37:38,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:38,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-10 19:37:38,219 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=794, Unknown=0, NotChecked=0, Total=930 [2024-11-10 19:37:38,219 INFO L87 Difference]: Start difference. First operand 78 states and 87 transitions. Second operand has 31 states, 30 states have (on average 3.033333333333333) internal successors, (91), 29 states have internal predecessors, (91), 8 states have call successors, (10), 3 states have call predecessors, (10), 7 states have return successors, (12), 12 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-10 19:37:38,846 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:38,847 INFO L93 Difference]: Finished difference Result 162 states and 185 transitions. [2024-11-10 19:37:38,847 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-10 19:37:38,847 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 30 states have (on average 3.033333333333333) internal successors, (91), 29 states have internal predecessors, (91), 8 states have call successors, (10), 3 states have call predecessors, (10), 7 states have return successors, (12), 12 states have call predecessors, (12), 6 states have call successors, (12) Word has length 67 [2024-11-10 19:37:38,847 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:38,848 INFO L225 Difference]: With dead ends: 162 [2024-11-10 19:37:38,849 INFO L226 Difference]: Without dead ends: 161 [2024-11-10 19:37:38,851 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 127 SyntacticMatches, 1 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 592 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=417, Invalid=2235, Unknown=0, NotChecked=0, Total=2652 [2024-11-10 19:37:38,851 INFO L432 NwaCegarLoop]: 17 mSDtfsCounter, 124 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 460 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 133 SdHoareTripleChecker+Valid, 224 SdHoareTripleChecker+Invalid, 505 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 460 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:38,852 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [133 Valid, 224 Invalid, 505 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 460 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-10 19:37:38,852 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2024-11-10 19:37:38,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 102. [2024-11-10 19:37:38,864 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 84 states have (on average 1.0595238095238095) internal successors, (89), 83 states have internal predecessors, (89), 6 states have call successors, (6), 4 states have call predecessors, (6), 11 states have return successors, (20), 14 states have call predecessors, (20), 5 states have call successors, (20) [2024-11-10 19:37:38,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 115 transitions. [2024-11-10 19:37:38,865 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 115 transitions. Word has length 67 [2024-11-10 19:37:38,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:38,866 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 115 transitions. [2024-11-10 19:37:38,866 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 30 states have (on average 3.033333333333333) internal successors, (91), 29 states have internal predecessors, (91), 8 states have call successors, (10), 3 states have call predecessors, (10), 7 states have return successors, (12), 12 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-10 19:37:38,866 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 115 transitions. [2024-11-10 19:37:38,869 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-11-10 19:37:38,869 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:38,870 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:38,888 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-10 19:37:39,070 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:39,071 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:39,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:39,071 INFO L85 PathProgramCache]: Analyzing trace with hash -64809051, now seen corresponding path program 2 times [2024-11-10 19:37:39,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:39,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1548272379] [2024-11-10 19:37:39,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:39,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:39,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:39,153 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:39,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:39,159 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:39,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:39,161 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-10 19:37:39,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:39,222 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:39,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:39,240 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 31 proven. 16 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-10 19:37:39,240 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:39,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1548272379] [2024-11-10 19:37:39,240 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1548272379] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:39,240 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [728590597] [2024-11-10 19:37:39,241 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-10 19:37:39,241 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:39,241 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:39,242 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:39,244 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-10 19:37:39,312 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-10 19:37:39,312 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 19:37:39,313 INFO L255 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 19:37:39,314 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:39,474 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 2 proven. 51 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-10 19:37:39,475 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:39,854 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 2 proven. 53 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-10 19:37:39,856 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [728590597] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:39,857 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:39,857 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 12, 13] total 28 [2024-11-10 19:37:39,857 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1229627805] [2024-11-10 19:37:39,857 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:39,858 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-11-10 19:37:39,858 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:39,858 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-10 19:37:39,859 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=714, Unknown=0, NotChecked=0, Total=812 [2024-11-10 19:37:39,859 INFO L87 Difference]: Start difference. First operand 102 states and 115 transitions. Second operand has 29 states, 28 states have (on average 3.5357142857142856) internal successors, (99), 26 states have internal predecessors, (99), 12 states have call successors, (14), 4 states have call predecessors, (14), 7 states have return successors, (12), 12 states have call predecessors, (12), 10 states have call successors, (12) [2024-11-10 19:37:40,491 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:40,491 INFO L93 Difference]: Finished difference Result 176 states and 196 transitions. [2024-11-10 19:37:40,491 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-11-10 19:37:40,492 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 28 states have (on average 3.5357142857142856) internal successors, (99), 26 states have internal predecessors, (99), 12 states have call successors, (14), 4 states have call predecessors, (14), 7 states have return successors, (12), 12 states have call predecessors, (12), 10 states have call successors, (12) Word has length 50 [2024-11-10 19:37:40,492 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:40,494 INFO L225 Difference]: With dead ends: 176 [2024-11-10 19:37:40,494 INFO L226 Difference]: Without dead ends: 163 [2024-11-10 19:37:40,495 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 88 SyntacticMatches, 2 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 571 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=509, Invalid=2353, Unknown=0, NotChecked=0, Total=2862 [2024-11-10 19:37:40,495 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 139 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 452 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 506 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 452 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:40,495 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 145 Invalid, 506 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 452 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-10 19:37:40,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2024-11-10 19:37:40,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 114. [2024-11-10 19:37:40,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 94 states have (on average 1.053191489361702) internal successors, (99), 93 states have internal predecessors, (99), 6 states have call successors, (6), 4 states have call predecessors, (6), 13 states have return successors, (22), 16 states have call predecessors, (22), 5 states have call successors, (22) [2024-11-10 19:37:40,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 127 transitions. [2024-11-10 19:37:40,510 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 127 transitions. Word has length 50 [2024-11-10 19:37:40,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:40,511 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 127 transitions. [2024-11-10 19:37:40,511 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 28 states have (on average 3.5357142857142856) internal successors, (99), 26 states have internal predecessors, (99), 12 states have call successors, (14), 4 states have call predecessors, (14), 7 states have return successors, (12), 12 states have call predecessors, (12), 10 states have call successors, (12) [2024-11-10 19:37:40,511 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 127 transitions. [2024-11-10 19:37:40,512 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-11-10 19:37:40,512 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:40,512 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 7, 7, 7, 7, 6, 5, 5, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:40,531 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-10 19:37:40,712 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-10 19:37:40,713 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:40,713 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:40,713 INFO L85 PathProgramCache]: Analyzing trace with hash 1163662213, now seen corresponding path program 3 times [2024-11-10 19:37:40,713 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:40,713 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [159841244] [2024-11-10 19:37:40,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:40,714 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:40,741 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:40,915 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:40,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:40,949 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:40,951 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:40,969 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-11-10 19:37:40,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:41,079 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:41,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:41,153 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:41,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:41,203 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:41,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:41,222 INFO L134 CoverageAnalysis]: Checked inductivity of 237 backedges. 6 proven. 181 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-10 19:37:41,222 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:41,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [159841244] [2024-11-10 19:37:41,222 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [159841244] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:41,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1814414306] [2024-11-10 19:37:41,223 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-10 19:37:41,223 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:41,223 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:41,225 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:41,226 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-10 19:37:41,305 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2024-11-10 19:37:41,306 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 19:37:41,307 INFO L255 TraceCheckSpWp]: Trace formula consists of 198 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-10 19:37:41,309 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:41,544 INFO L134 CoverageAnalysis]: Checked inductivity of 237 backedges. 79 proven. 102 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2024-11-10 19:37:41,544 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:42,399 INFO L134 CoverageAnalysis]: Checked inductivity of 237 backedges. 89 proven. 102 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2024-11-10 19:37:42,399 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1814414306] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:42,399 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:42,399 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13, 14] total 36 [2024-11-10 19:37:42,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [879611076] [2024-11-10 19:37:42,399 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:42,400 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 37 states [2024-11-10 19:37:42,400 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:42,401 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2024-11-10 19:37:42,403 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=156, Invalid=1176, Unknown=0, NotChecked=0, Total=1332 [2024-11-10 19:37:42,403 INFO L87 Difference]: Start difference. First operand 114 states and 127 transitions. Second operand has 37 states, 36 states have (on average 3.3333333333333335) internal successors, (120), 34 states have internal predecessors, (120), 12 states have call successors, (18), 4 states have call predecessors, (18), 10 states have return successors, (17), 17 states have call predecessors, (17), 11 states have call successors, (17) [2024-11-10 19:37:43,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:43,685 INFO L93 Difference]: Finished difference Result 247 states and 276 transitions. [2024-11-10 19:37:43,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2024-11-10 19:37:43,685 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 36 states have (on average 3.3333333333333335) internal successors, (120), 34 states have internal predecessors, (120), 12 states have call successors, (18), 4 states have call predecessors, (18), 10 states have return successors, (17), 17 states have call predecessors, (17), 11 states have call successors, (17) Word has length 86 [2024-11-10 19:37:43,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:43,686 INFO L225 Difference]: With dead ends: 247 [2024-11-10 19:37:43,686 INFO L226 Difference]: Without dead ends: 222 [2024-11-10 19:37:43,688 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 166 SyntacticMatches, 1 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1552 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=901, Invalid=5579, Unknown=0, NotChecked=0, Total=6480 [2024-11-10 19:37:43,688 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 295 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 907 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 295 SdHoareTripleChecker+Valid, 219 SdHoareTripleChecker+Invalid, 981 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 907 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:43,689 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [295 Valid, 219 Invalid, 981 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 907 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-10 19:37:43,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2024-11-10 19:37:43,701 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 138. [2024-11-10 19:37:43,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 114 states have (on average 1.043859649122807) internal successors, (119), 113 states have internal predecessors, (119), 6 states have call successors, (6), 4 states have call predecessors, (6), 17 states have return successors, (26), 20 states have call predecessors, (26), 5 states have call successors, (26) [2024-11-10 19:37:43,702 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 151 transitions. [2024-11-10 19:37:43,703 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 151 transitions. Word has length 86 [2024-11-10 19:37:43,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:43,703 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 151 transitions. [2024-11-10 19:37:43,703 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 37 states, 36 states have (on average 3.3333333333333335) internal successors, (120), 34 states have internal predecessors, (120), 12 states have call successors, (18), 4 states have call predecessors, (18), 10 states have return successors, (17), 17 states have call predecessors, (17), 11 states have call successors, (17) [2024-11-10 19:37:43,703 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 151 transitions. [2024-11-10 19:37:43,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-10 19:37:43,704 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:43,704 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:43,721 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-10 19:37:43,908 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-10 19:37:43,909 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:43,909 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:43,909 INFO L85 PathProgramCache]: Analyzing trace with hash -917301570, now seen corresponding path program 3 times [2024-11-10 19:37:43,909 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:43,909 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1192169626] [2024-11-10 19:37:43,909 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:43,910 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:43,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:44,131 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-10 19:37:44,141 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:44,441 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:44,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:44,622 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:44,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:44,817 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:44,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:44,928 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:44,933 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:45,012 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:45,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:45,091 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:45,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:45,147 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:45,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:45,170 INFO L134 CoverageAnalysis]: Checked inductivity of 353 backedges. 0 proven. 220 refuted. 0 times theorem prover too weak. 133 trivial. 0 not checked. [2024-11-10 19:37:45,170 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:45,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1192169626] [2024-11-10 19:37:45,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1192169626] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:45,171 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1730117716] [2024-11-10 19:37:45,171 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-10 19:37:45,171 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:45,171 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:45,173 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:45,175 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-10 19:37:45,254 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2024-11-10 19:37:45,254 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 19:37:45,257 INFO L255 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-10 19:37:45,261 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:45,630 INFO L134 CoverageAnalysis]: Checked inductivity of 353 backedges. 0 proven. 220 refuted. 0 times theorem prover too weak. 133 trivial. 0 not checked. [2024-11-10 19:37:45,630 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:49,689 INFO L134 CoverageAnalysis]: Checked inductivity of 353 backedges. 30 proven. 220 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2024-11-10 19:37:49,690 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1730117716] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:49,690 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:49,690 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 22] total 50 [2024-11-10 19:37:49,690 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [604418737] [2024-11-10 19:37:49,690 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:49,691 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2024-11-10 19:37:49,691 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:49,692 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2024-11-10 19:37:49,695 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=322, Invalid=2228, Unknown=0, NotChecked=0, Total=2550 [2024-11-10 19:37:49,696 INFO L87 Difference]: Start difference. First operand 138 states and 151 transitions. Second operand has 51 states, 50 states have (on average 2.94) internal successors, (147), 49 states have internal predecessors, (147), 8 states have call successors, (8), 3 states have call predecessors, (8), 15 states have return successors, (24), 24 states have call predecessors, (24), 6 states have call successors, (24) [2024-11-10 19:37:50,961 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:50,961 INFO L93 Difference]: Finished difference Result 275 states and 311 transitions. [2024-11-10 19:37:50,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2024-11-10 19:37:50,962 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 50 states have (on average 2.94) internal successors, (147), 49 states have internal predecessors, (147), 8 states have call successors, (8), 3 states have call predecessors, (8), 15 states have return successors, (24), 24 states have call predecessors, (24), 6 states have call successors, (24) Word has length 103 [2024-11-10 19:37:50,962 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:50,964 INFO L225 Difference]: With dead ends: 275 [2024-11-10 19:37:50,964 INFO L226 Difference]: Without dead ends: 274 [2024-11-10 19:37:50,966 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 281 GetRequests, 191 SyntacticMatches, 1 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2207 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1067, Invalid=7123, Unknown=0, NotChecked=0, Total=8190 [2024-11-10 19:37:50,967 INFO L432 NwaCegarLoop]: 21 mSDtfsCounter, 382 mSDsluCounter, 309 mSDsCounter, 0 mSdLazyCounter, 1091 mSolverCounterSat, 125 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 399 SdHoareTripleChecker+Valid, 330 SdHoareTripleChecker+Invalid, 1216 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 125 IncrementalHoareTripleChecker+Valid, 1091 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:50,968 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [399 Valid, 330 Invalid, 1216 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [125 Valid, 1091 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-10 19:37:50,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 274 states. [2024-11-10 19:37:50,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 274 to 186. [2024-11-10 19:37:50,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 154 states have (on average 1.0324675324675325) internal successors, (159), 153 states have internal predecessors, (159), 6 states have call successors, (6), 4 states have call predecessors, (6), 25 states have return successors, (42), 28 states have call predecessors, (42), 5 states have call successors, (42) [2024-11-10 19:37:50,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 207 transitions. [2024-11-10 19:37:50,989 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 207 transitions. Word has length 103 [2024-11-10 19:37:50,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:50,990 INFO L471 AbstractCegarLoop]: Abstraction has 186 states and 207 transitions. [2024-11-10 19:37:50,990 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 51 states, 50 states have (on average 2.94) internal successors, (147), 49 states have internal predecessors, (147), 8 states have call successors, (8), 3 states have call predecessors, (8), 15 states have return successors, (24), 24 states have call predecessors, (24), 6 states have call successors, (24) [2024-11-10 19:37:50,990 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 207 transitions. [2024-11-10 19:37:50,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2024-11-10 19:37:50,992 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:50,992 INFO L215 NwaCegarLoop]: trace histogram [11, 11, 10, 9, 9, 9, 9, 9, 9, 9, 8, 8, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:51,010 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-10 19:37:51,193 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-10 19:37:51,193 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:51,193 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:51,194 INFO L85 PathProgramCache]: Analyzing trace with hash 2006786425, now seen corresponding path program 4 times [2024-11-10 19:37:51,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:51,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [47837085] [2024-11-10 19:37:51,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:51,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:51,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:51,474 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:37:51,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:51,502 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:51,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:51,518 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-10 19:37:51,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:51,726 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:51,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:51,894 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:51,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:52,029 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:52,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:52,145 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:52,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:52,237 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:52,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:52,313 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:52,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:52,372 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:37:52,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:37:52,409 INFO L134 CoverageAnalysis]: Checked inductivity of 499 backedges. 2 proven. 345 refuted. 0 times theorem prover too weak. 152 trivial. 0 not checked. [2024-11-10 19:37:52,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:37:52,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [47837085] [2024-11-10 19:37:52,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [47837085] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:37:52,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [665261922] [2024-11-10 19:37:52,409 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-10 19:37:52,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:37:52,410 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:37:52,412 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:37:52,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-10 19:37:52,540 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-10 19:37:52,541 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 19:37:52,542 INFO L255 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-11-10 19:37:52,544 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:37:52,918 INFO L134 CoverageAnalysis]: Checked inductivity of 499 backedges. 2 proven. 345 refuted. 0 times theorem prover too weak. 152 trivial. 0 not checked. [2024-11-10 19:37:52,918 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:37:57,158 INFO L134 CoverageAnalysis]: Checked inductivity of 499 backedges. 32 proven. 347 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2024-11-10 19:37:57,158 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [665261922] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:37:57,158 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:37:57,158 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24, 26] total 57 [2024-11-10 19:37:57,159 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [842093734] [2024-11-10 19:37:57,159 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:37:57,159 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 58 states [2024-11-10 19:37:57,159 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:37:57,160 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 58 interpolants. [2024-11-10 19:37:57,161 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=348, Invalid=2958, Unknown=0, NotChecked=0, Total=3306 [2024-11-10 19:37:57,162 INFO L87 Difference]: Start difference. First operand 186 states and 207 transitions. Second operand has 58 states, 57 states have (on average 3.1228070175438596) internal successors, (178), 56 states have internal predecessors, (178), 12 states have call successors, (12), 3 states have call predecessors, (12), 18 states have return successors, (29), 28 states have call predecessors, (29), 10 states have call successors, (29) [2024-11-10 19:37:59,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:37:59,576 INFO L93 Difference]: Finished difference Result 376 states and 415 transitions. [2024-11-10 19:37:59,576 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2024-11-10 19:37:59,577 INFO L78 Accepts]: Start accepts. Automaton has has 58 states, 57 states have (on average 3.1228070175438596) internal successors, (178), 56 states have internal predecessors, (178), 12 states have call successors, (12), 3 states have call predecessors, (12), 18 states have return successors, (29), 28 states have call predecessors, (29), 10 states have call successors, (29) Word has length 122 [2024-11-10 19:37:59,577 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:37:59,579 INFO L225 Difference]: With dead ends: 376 [2024-11-10 19:37:59,579 INFO L226 Difference]: Without dead ends: 348 [2024-11-10 19:37:59,584 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 362 GetRequests, 229 SyntacticMatches, 2 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5154 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=1959, Invalid=15597, Unknown=0, NotChecked=0, Total=17556 [2024-11-10 19:37:59,585 INFO L432 NwaCegarLoop]: 25 mSDtfsCounter, 658 mSDsluCounter, 439 mSDsCounter, 0 mSdLazyCounter, 2301 mSolverCounterSat, 190 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 658 SdHoareTripleChecker+Valid, 464 SdHoareTripleChecker+Invalid, 2491 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 190 IncrementalHoareTripleChecker+Valid, 2301 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-10 19:37:59,585 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [658 Valid, 464 Invalid, 2491 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [190 Valid, 2301 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-10 19:37:59,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 348 states. [2024-11-10 19:37:59,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 348 to 307. [2024-11-10 19:37:59,615 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 307 states, 254 states have (on average 1.0275590551181102) internal successors, (261), 253 states have internal predecessors, (261), 9 states have call successors, (9), 6 states have call predecessors, (9), 43 states have return successors, (61), 47 states have call predecessors, (61), 7 states have call successors, (61) [2024-11-10 19:37:59,617 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 307 states to 307 states and 331 transitions. [2024-11-10 19:37:59,617 INFO L78 Accepts]: Start accepts. Automaton has 307 states and 331 transitions. Word has length 122 [2024-11-10 19:37:59,617 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:37:59,618 INFO L471 AbstractCegarLoop]: Abstraction has 307 states and 331 transitions. [2024-11-10 19:37:59,618 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 58 states, 57 states have (on average 3.1228070175438596) internal successors, (178), 56 states have internal predecessors, (178), 12 states have call successors, (12), 3 states have call predecessors, (12), 18 states have return successors, (29), 28 states have call predecessors, (29), 10 states have call successors, (29) [2024-11-10 19:37:59,618 INFO L276 IsEmpty]: Start isEmpty. Operand 307 states and 331 transitions. [2024-11-10 19:37:59,620 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2024-11-10 19:37:59,620 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:37:59,620 INFO L215 NwaCegarLoop]: trace histogram [13, 13, 12, 11, 11, 11, 11, 11, 11, 11, 10, 10, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:37:59,639 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-10 19:37:59,820 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2024-11-10 19:37:59,821 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:37:59,821 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:37:59,821 INFO L85 PathProgramCache]: Analyzing trace with hash -1757013063, now seen corresponding path program 5 times [2024-11-10 19:37:59,821 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:37:59,821 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [342557179] [2024-11-10 19:37:59,822 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:37:59,822 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:37:59,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,081 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 19:38:00,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,088 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:00,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,091 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:00,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,093 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 41 [2024-11-10 19:38:00,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,347 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:00,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,561 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:00,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,704 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:00,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,832 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:00,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:00,931 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:00,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:01,028 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:01,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:01,114 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:01,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:01,178 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:01,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:01,206 INFO L134 CoverageAnalysis]: Checked inductivity of 741 backedges. 235 proven. 275 refuted. 0 times theorem prover too weak. 231 trivial. 0 not checked. [2024-11-10 19:38:01,206 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:38:01,206 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [342557179] [2024-11-10 19:38:01,207 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [342557179] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:38:01,207 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [697247935] [2024-11-10 19:38:01,207 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-10 19:38:01,207 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:38:01,207 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:38:01,209 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:38:01,211 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-10 19:38:01,412 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 15 check-sat command(s) [2024-11-10 19:38:01,413 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 19:38:01,418 INFO L255 TraceCheckSpWp]: Trace formula consists of 317 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-11-10 19:38:01,423 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:38:02,039 INFO L134 CoverageAnalysis]: Checked inductivity of 741 backedges. 3 proven. 523 refuted. 0 times theorem prover too weak. 215 trivial. 0 not checked. [2024-11-10 19:38:02,039 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 19:38:07,724 INFO L134 CoverageAnalysis]: Checked inductivity of 741 backedges. 3 proven. 567 refuted. 0 times theorem prover too weak. 171 trivial. 0 not checked. [2024-11-10 19:38:07,725 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [697247935] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 19:38:07,725 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 19:38:07,725 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 27, 30] total 66 [2024-11-10 19:38:07,725 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [930424634] [2024-11-10 19:38:07,725 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 19:38:07,726 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 67 states [2024-11-10 19:38:07,726 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 19:38:07,728 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 67 interpolants. [2024-11-10 19:38:07,729 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=428, Invalid=3994, Unknown=0, NotChecked=0, Total=4422 [2024-11-10 19:38:07,729 INFO L87 Difference]: Start difference. First operand 307 states and 331 transitions. Second operand has 67 states, 66 states have (on average 3.212121212121212) internal successors, (212), 64 states have internal predecessors, (212), 14 states have call successors, (16), 4 states have call predecessors, (16), 22 states have return successors, (35), 34 states have call predecessors, (35), 12 states have call successors, (35) [2024-11-10 19:38:11,984 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 19:38:11,984 INFO L93 Difference]: Finished difference Result 597 states and 660 transitions. [2024-11-10 19:38:11,985 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 125 states. [2024-11-10 19:38:11,985 INFO L78 Accepts]: Start accepts. Automaton has has 67 states, 66 states have (on average 3.212121212121212) internal successors, (212), 64 states have internal predecessors, (212), 14 states have call successors, (16), 4 states have call predecessors, (16), 22 states have return successors, (35), 34 states have call predecessors, (35), 12 states have call successors, (35) Word has length 146 [2024-11-10 19:38:11,985 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-10 19:38:11,988 INFO L225 Difference]: With dead ends: 597 [2024-11-10 19:38:11,988 INFO L226 Difference]: Without dead ends: 542 [2024-11-10 19:38:11,993 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 456 GetRequests, 271 SyntacticMatches, 3 SemanticMatches, 182 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10583 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=3563, Invalid=30109, Unknown=0, NotChecked=0, Total=33672 [2024-11-10 19:38:11,993 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 648 mSDsluCounter, 751 mSDsCounter, 0 mSdLazyCounter, 3377 mSolverCounterSat, 189 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 648 SdHoareTripleChecker+Valid, 783 SdHoareTripleChecker+Invalid, 3566 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 189 IncrementalHoareTripleChecker+Valid, 3377 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-11-10 19:38:11,994 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [648 Valid, 783 Invalid, 3566 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [189 Valid, 3377 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-11-10 19:38:11,995 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 542 states. [2024-11-10 19:38:12,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 542 to 246. [2024-11-10 19:38:12,018 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 246 states, 204 states have (on average 1.0245098039215685) internal successors, (209), 203 states have internal predecessors, (209), 6 states have call successors, (6), 4 states have call predecessors, (6), 35 states have return successors, (52), 38 states have call predecessors, (52), 5 states have call successors, (52) [2024-11-10 19:38:12,019 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 246 states to 246 states and 267 transitions. [2024-11-10 19:38:12,020 INFO L78 Accepts]: Start accepts. Automaton has 246 states and 267 transitions. Word has length 146 [2024-11-10 19:38:12,020 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-10 19:38:12,020 INFO L471 AbstractCegarLoop]: Abstraction has 246 states and 267 transitions. [2024-11-10 19:38:12,021 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 67 states, 66 states have (on average 3.212121212121212) internal successors, (212), 64 states have internal predecessors, (212), 14 states have call successors, (16), 4 states have call predecessors, (16), 22 states have return successors, (35), 34 states have call predecessors, (35), 12 states have call successors, (35) [2024-11-10 19:38:12,021 INFO L276 IsEmpty]: Start isEmpty. Operand 246 states and 267 transitions. [2024-11-10 19:38:12,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 200 [2024-11-10 19:38:12,023 INFO L207 NwaCegarLoop]: Found error trace [2024-11-10 19:38:12,023 INFO L215 NwaCegarLoop]: trace histogram [17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 19:38:12,041 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-10 19:38:12,224 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:38:12,224 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW === [multErr0ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr1ASSERT_VIOLATIONINTEGER_OVERFLOW, multErr2ASSERT_VIOLATIONINTEGER_OVERFLOW (and 3 more)] === [2024-11-10 19:38:12,224 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 19:38:12,225 INFO L85 PathProgramCache]: Analyzing trace with hash 1316833582, now seen corresponding path program 4 times [2024-11-10 19:38:12,225 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 19:38:12,225 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [237347739] [2024-11-10 19:38:12,225 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 19:38:12,225 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 19:38:12,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:12,672 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-10 19:38:12,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:13,392 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:13,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:13,911 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:13,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:14,402 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:14,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:14,873 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:14,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:15,193 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:15,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:15,483 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:15,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:15,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:15,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:15,912 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:15,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,098 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:16,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,236 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:16,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,355 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:16,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,454 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:16,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,545 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:16,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,615 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:16,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-11-10 19:38:16,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 19:38:16,716 INFO L134 CoverageAnalysis]: Checked inductivity of 1473 backedges. 0 proven. 828 refuted. 0 times theorem prover too weak. 645 trivial. 0 not checked. [2024-11-10 19:38:16,716 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 19:38:16,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [237347739] [2024-11-10 19:38:16,716 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [237347739] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 19:38:16,717 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [200784657] [2024-11-10 19:38:16,717 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-10 19:38:16,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 19:38:16,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 19:38:16,719 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-10 19:38:16,721 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-10 19:38:16,949 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-10 19:38:16,949 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 19:38:16,951 INFO L255 TraceCheckSpWp]: Trace formula consists of 410 conjuncts, 66 conjuncts are in the unsatisfiable core [2024-11-10 19:38:16,954 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 19:38:17,698 INFO L134 CoverageAnalysis]: Checked inductivity of 1473 backedges. 0 proven. 828 refuted. 0 times theorem prover too weak. 645 trivial. 0 not checked. [2024-11-10 19:38:17,699 INFO L311 TraceCheckSpWp]: Computing backward predicates...