./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/unreach-call.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound20.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 20f9ce6814caacb533e5bf2143ac3e067387f11238548a0b9b41e2de8e2cc436 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-11 02:08:20,971 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-11 02:08:21,036 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-10-11 02:08:21,043 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-11 02:08:21,044 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-11 02:08:21,074 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-11 02:08:21,075 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-11 02:08:21,076 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-11 02:08:21,077 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-11 02:08:21,077 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-11 02:08:21,078 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-10-11 02:08:21,078 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-10-11 02:08:21,078 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-11 02:08:21,079 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-11 02:08:21,079 INFO L153 SettingsManager]: * Use SBE=true [2024-10-11 02:08:21,079 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-11 02:08:21,080 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-10-11 02:08:21,080 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-11 02:08:21,080 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-11 02:08:21,080 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-11 02:08:21,081 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-11 02:08:21,084 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-10-11 02:08:21,084 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-10-11 02:08:21,085 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-10-11 02:08:21,085 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-11 02:08:21,085 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-11 02:08:21,085 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-11 02:08:21,085 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-11 02:08:21,086 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-11 02:08:21,086 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-11 02:08:21,086 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-10-11 02:08:21,086 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-10-11 02:08:21,086 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:08:21,087 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-11 02:08:21,087 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-10-11 02:08:21,087 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-10-11 02:08:21,087 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-11 02:08:21,087 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-10-11 02:08:21,087 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-10-11 02:08:21,088 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-10-11 02:08:21,088 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-10-11 02:08:21,090 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-10-11 02:08:21,090 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-clean/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-clean/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 ! call(reach_error())) ) 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 -> 20f9ce6814caacb533e5bf2143ac3e067387f11238548a0b9b41e2de8e2cc436 [2024-10-11 02:08:21,317 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-11 02:08:21,339 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-11 02:08:21,342 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-11 02:08:21,343 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-11 02:08:21,343 INFO L274 PluginConnector]: CDTParser initialized [2024-10-11 02:08:21,344 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound20.c [2024-10-11 02:08:22,773 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-11 02:08:22,934 INFO L384 CDTParser]: Found 1 translation units. [2024-10-11 02:08:22,935 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound20.c [2024-10-11 02:08:22,941 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/198c75166/be835791bfdc46eaac098f8e7f29e2da/FLAG2711cc6d1 [2024-10-11 02:08:22,953 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/198c75166/be835791bfdc46eaac098f8e7f29e2da [2024-10-11 02:08:22,958 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-11 02:08:22,959 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-11 02:08:22,960 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-11 02:08:22,960 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-11 02:08:22,966 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-11 02:08:22,967 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:08:22" (1/1) ... [2024-10-11 02:08:22,968 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@14f64611 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:22, skipping insertion in model container [2024-10-11 02:08:22,968 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.10 02:08:22" (1/1) ... [2024-10-11 02:08:22,987 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-11 02:08:23,162 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound20.c[489,502] [2024-10-11 02:08:23,183 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:08:23,191 INFO L200 MainTranslator]: Completed pre-run [2024-10-11 02:08:23,201 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound20.c[489,502] [2024-10-11 02:08:23,208 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-11 02:08:23,221 INFO L204 MainTranslator]: Completed translation [2024-10-11 02:08:23,221 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23 WrapperNode [2024-10-11 02:08:23,222 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-11 02:08:23,223 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-11 02:08:23,223 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-11 02:08:23,223 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-11 02:08:23,230 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,238 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,260 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 57 [2024-10-11 02:08:23,262 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-11 02:08:23,262 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-11 02:08:23,263 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-11 02:08:23,263 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-11 02:08:23,273 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,273 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,275 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,284 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-10-11 02:08:23,285 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,285 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,287 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,292 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,293 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,294 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,296 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-11 02:08:23,299 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-11 02:08:23,299 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-11 02:08:23,299 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-11 02:08:23,300 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (1/1) ... [2024-10-11 02:08:23,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-10-11 02:08:23,319 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:23,340 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-10-11 02:08:23,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-10-11 02:08:23,392 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-11 02:08:23,392 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-10-11 02:08:23,392 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-10-11 02:08:23,393 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-11 02:08:23,393 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-11 02:08:23,393 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-11 02:08:23,393 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-10-11 02:08:23,395 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-10-11 02:08:23,460 INFO L238 CfgBuilder]: Building ICFG [2024-10-11 02:08:23,465 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-11 02:08:23,636 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-10-11 02:08:23,636 INFO L287 CfgBuilder]: Performing block encoding [2024-10-11 02:08:23,667 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-11 02:08:23,668 INFO L314 CfgBuilder]: Removed 1 assume(true) statements. [2024-10-11 02:08:23,668 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:08:23 BoogieIcfgContainer [2024-10-11 02:08:23,668 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-11 02:08:23,671 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-10-11 02:08:23,671 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-10-11 02:08:23,674 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-10-11 02:08:23,674 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.10 02:08:22" (1/3) ... [2024-10-11 02:08:23,675 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@770e30cd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:08:23, skipping insertion in model container [2024-10-11 02:08:23,675 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.10 02:08:23" (2/3) ... [2024-10-11 02:08:23,675 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@770e30cd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.10 02:08:23, skipping insertion in model container [2024-10-11 02:08:23,675 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:08:23" (3/3) ... [2024-10-11 02:08:23,676 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound20.c [2024-10-11 02:08:23,690 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-10-11 02:08:23,690 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-10-11 02:08:23,742 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-10-11 02:08:23,747 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;@4950ccc4, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-10-11 02:08:23,747 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-10-11 02:08:23,750 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 14 states have (on average 1.5) internal successors, (21), 15 states have internal predecessors, (21), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-10-11 02:08:23,756 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-10-11 02:08:23,756 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:23,757 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:23,757 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:23,761 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:23,761 INFO L85 PathProgramCache]: Analyzing trace with hash 1514925992, now seen corresponding path program 1 times [2024-10-11 02:08:23,767 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:23,768 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1442717893] [2024-10-11 02:08:23,768 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:23,768 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:23,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:08:23,896 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1869503620] [2024-10-11 02:08:23,898 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:23,898 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:23,898 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:23,901 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:23,902 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-10-11 02:08:23,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:23,994 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-11 02:08:24,000 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:24,111 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 02:08:24,111 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:08:24,112 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:24,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1442717893] [2024-10-11 02:08:24,112 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:08:24,112 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1869503620] [2024-10-11 02:08:24,113 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1869503620] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:08:24,113 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:08:24,113 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:08:24,117 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [528589176] [2024-10-11 02:08:24,117 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:08:24,121 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:08:24,122 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:24,141 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:08:24,141 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:08:24,143 INFO L87 Difference]: Start difference. First operand has 29 states, 14 states have (on average 1.5) internal successors, (21), 15 states have internal predecessors, (21), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-11 02:08:24,236 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:24,237 INFO L93 Difference]: Finished difference Result 71 states and 127 transitions. [2024-10-11 02:08:24,238 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:08:24,240 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2024-10-11 02:08:24,240 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:24,248 INFO L225 Difference]: With dead ends: 71 [2024-10-11 02:08:24,249 INFO L226 Difference]: Without dead ends: 41 [2024-10-11 02:08:24,253 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 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-10-11 02:08:24,256 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 5 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:24,259 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 118 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:08:24,275 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-10-11 02:08:24,293 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 40. [2024-10-11 02:08:24,294 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 19 states have (on average 1.263157894736842) internal successors, (24), 21 states have internal predecessors, (24), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 15 states have call predecessors, (16), 16 states have call successors, (16) [2024-10-11 02:08:24,297 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 57 transitions. [2024-10-11 02:08:24,299 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 57 transitions. Word has length 28 [2024-10-11 02:08:24,299 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:24,300 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 57 transitions. [2024-10-11 02:08:24,300 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-10-11 02:08:24,300 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 57 transitions. [2024-10-11 02:08:24,301 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-10-11 02:08:24,302 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:24,302 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:24,314 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-10-11 02:08:24,502 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-10-11 02:08:24,503 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:24,504 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:24,504 INFO L85 PathProgramCache]: Analyzing trace with hash 1720779372, now seen corresponding path program 1 times [2024-10-11 02:08:24,504 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:24,504 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1079568464] [2024-10-11 02:08:24,504 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:24,504 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:24,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:08:24,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [845911009] [2024-10-11 02:08:24,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:24,533 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:24,533 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:24,535 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:24,537 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-10-11 02:08:24,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:24,586 INFO L255 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-10-11 02:08:24,588 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:24,670 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-10-11 02:08:24,674 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:08:24,674 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:24,674 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1079568464] [2024-10-11 02:08:24,675 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:08:24,675 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [845911009] [2024-10-11 02:08:24,675 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [845911009] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:08:24,675 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:08:24,675 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:08:24,675 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2088129639] [2024-10-11 02:08:24,675 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:08:24,676 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:08:24,676 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:24,677 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:08:24,677 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:08:24,677 INFO L87 Difference]: Start difference. First operand 40 states and 57 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-11 02:08:24,776 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:24,779 INFO L93 Difference]: Finished difference Result 65 states and 97 transitions. [2024-10-11 02:08:24,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:08:24,780 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2024-10-11 02:08:24,780 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:24,783 INFO L225 Difference]: With dead ends: 65 [2024-10-11 02:08:24,783 INFO L226 Difference]: Without dead ends: 63 [2024-10-11 02:08:24,784 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-10-11 02:08:24,785 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 116 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:24,786 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 116 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:08:24,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-10-11 02:08:24,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 56. [2024-10-11 02:08:24,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 28 states have (on average 1.3214285714285714) internal successors, (37), 30 states have internal predecessors, (37), 23 states have call successors, (23), 4 states have call predecessors, (23), 4 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2024-10-11 02:08:24,800 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 82 transitions. [2024-10-11 02:08:24,801 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 82 transitions. Word has length 33 [2024-10-11 02:08:24,801 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:24,801 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 82 transitions. [2024-10-11 02:08:24,802 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-10-11 02:08:24,802 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 82 transitions. [2024-10-11 02:08:24,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-10-11 02:08:24,803 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:24,803 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:24,819 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-10-11 02:08:25,007 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,3 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:25,008 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:25,008 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:25,008 INFO L85 PathProgramCache]: Analyzing trace with hash 1127883240, now seen corresponding path program 1 times [2024-10-11 02:08:25,009 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:25,009 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2109530134] [2024-10-11 02:08:25,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:25,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:25,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:08:25,036 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [762700359] [2024-10-11 02:08:25,036 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:25,036 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:25,036 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:25,038 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:25,039 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-10-11 02:08:25,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,087 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-11 02:08:25,089 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:25,175 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-11 02:08:25,179 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:08:25,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:25,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2109530134] [2024-10-11 02:08:25,179 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:08:25,180 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [762700359] [2024-10-11 02:08:25,180 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [762700359] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:08:25,180 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:08:25,180 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:08:25,180 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [742563656] [2024-10-11 02:08:25,180 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:08:25,181 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:08:25,181 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:25,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:08:25,185 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:08:25,185 INFO L87 Difference]: Start difference. First operand 56 states and 82 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-11 02:08:25,251 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:25,252 INFO L93 Difference]: Finished difference Result 63 states and 88 transitions. [2024-10-11 02:08:25,252 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:08:25,252 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2024-10-11 02:08:25,253 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:25,254 INFO L225 Difference]: With dead ends: 63 [2024-10-11 02:08:25,254 INFO L226 Difference]: Without dead ends: 59 [2024-10-11 02:08:25,255 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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-10-11 02:08:25,256 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:25,257 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 115 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:08:25,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2024-10-11 02:08:25,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 59. [2024-10-11 02:08:25,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 33 states have internal predecessors, (40), 22 states have call successors, (22), 5 states have call predecessors, (22), 5 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-10-11 02:08:25,273 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 82 transitions. [2024-10-11 02:08:25,275 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 82 transitions. Word has length 38 [2024-10-11 02:08:25,275 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:25,275 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 82 transitions. [2024-10-11 02:08:25,276 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-10-11 02:08:25,276 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 82 transitions. [2024-10-11 02:08:25,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-10-11 02:08:25,277 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:25,277 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:25,293 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-10-11 02:08:25,481 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:25,482 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:25,482 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:25,483 INFO L85 PathProgramCache]: Analyzing trace with hash -1622474211, now seen corresponding path program 1 times [2024-10-11 02:08:25,483 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:25,483 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1733663749] [2024-10-11 02:08:25,483 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:25,483 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:25,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,708 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:08:25,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,716 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-11 02:08:25,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-11 02:08:25,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,723 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-11 02:08:25,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,726 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-11 02:08:25,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,729 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-11 02:08:25,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,733 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-11 02:08:25,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,736 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-10-11 02:08:25,736 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:25,737 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1733663749] [2024-10-11 02:08:25,737 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1733663749] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:08:25,737 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:08:25,737 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:08:25,737 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1602048908] [2024-10-11 02:08:25,737 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:08:25,738 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:08:25,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:25,738 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:08:25,739 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:08:25,739 INFO L87 Difference]: Start difference. First operand 59 states and 82 transitions. Second operand has 5 states, 4 states have (on average 3.5) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2024-10-11 02:08:25,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:25,794 INFO L93 Difference]: Finished difference Result 65 states and 87 transitions. [2024-10-11 02:08:25,794 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:08:25,794 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 44 [2024-10-11 02:08:25,795 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:25,795 INFO L225 Difference]: With dead ends: 65 [2024-10-11 02:08:25,796 INFO L226 Difference]: Without dead ends: 63 [2024-10-11 02:08:25,796 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 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-10-11 02:08:25,797 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 3 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:25,797 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 125 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:08:25,798 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-10-11 02:08:25,810 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2024-10-11 02:08:25,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 34 states have (on average 1.2647058823529411) internal successors, (43), 36 states have internal predecessors, (43), 22 states have call successors, (22), 6 states have call predecessors, (22), 6 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-10-11 02:08:25,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 85 transitions. [2024-10-11 02:08:25,812 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 85 transitions. Word has length 44 [2024-10-11 02:08:25,812 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:25,812 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 85 transitions. [2024-10-11 02:08:25,812 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2024-10-11 02:08:25,812 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 85 transitions. [2024-10-11 02:08:25,814 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-10-11 02:08:25,815 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:25,815 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:25,815 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-10-11 02:08:25,816 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:25,817 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:25,817 INFO L85 PathProgramCache]: Analyzing trace with hash 302551960, now seen corresponding path program 1 times [2024-10-11 02:08:25,817 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:25,817 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [509541036] [2024-10-11 02:08:25,817 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:25,817 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:25,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:08:25,862 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [614537846] [2024-10-11 02:08:25,862 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:25,862 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:25,863 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:25,866 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:25,871 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-10-11 02:08:25,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:25,928 INFO L255 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-11 02:08:25,930 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:26,072 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2024-10-11 02:08:26,073 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:08:26,074 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:26,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [509541036] [2024-10-11 02:08:26,074 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:08:26,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [614537846] [2024-10-11 02:08:26,074 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [614537846] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:08:26,075 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-11 02:08:26,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-11 02:08:26,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [56781825] [2024-10-11 02:08:26,079 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:08:26,079 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:08:26,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:26,080 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:08:26,080 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-10-11 02:08:26,080 INFO L87 Difference]: Start difference. First operand 63 states and 85 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-11 02:08:26,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:26,142 INFO L93 Difference]: Finished difference Result 79 states and 103 transitions. [2024-10-11 02:08:26,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:08:26,143 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 46 [2024-10-11 02:08:26,143 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:26,144 INFO L225 Difference]: With dead ends: 79 [2024-10-11 02:08:26,146 INFO L226 Difference]: Without dead ends: 77 [2024-10-11 02:08:26,147 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 42 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-10-11 02:08:26,147 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 4 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:26,148 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 114 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-10-11 02:08:26,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2024-10-11 02:08:26,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 74. [2024-10-11 02:08:26,165 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 40 states have (on average 1.225) internal successors, (49), 43 states have internal predecessors, (49), 25 states have call successors, (25), 8 states have call predecessors, (25), 8 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-10-11 02:08:26,166 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 97 transitions. [2024-10-11 02:08:26,167 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 97 transitions. Word has length 46 [2024-10-11 02:08:26,167 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:26,167 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 97 transitions. [2024-10-11 02:08:26,168 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-11 02:08:26,168 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 97 transitions. [2024-10-11 02:08:26,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-10-11 02:08:26,169 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:26,169 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:26,188 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-10-11 02:08:26,370 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:26,370 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:26,371 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:26,371 INFO L85 PathProgramCache]: Analyzing trace with hash -399804329, now seen corresponding path program 1 times [2024-10-11 02:08:26,371 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:26,371 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [932146127] [2024-10-11 02:08:26,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:26,371 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:26,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,634 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:08:26,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,638 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-11 02:08:26,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,640 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-11 02:08:26,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,642 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-11 02:08:26,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,645 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-11 02:08:26,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,649 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-11 02:08:26,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,682 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-11 02:08:26,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,703 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 40 [2024-10-11 02:08:26,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,709 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-11 02:08:26,709 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:26,709 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [932146127] [2024-10-11 02:08:26,709 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [932146127] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:08:26,709 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1992935712] [2024-10-11 02:08:26,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:26,709 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:26,710 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:26,712 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:26,714 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-10-11 02:08:26,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:26,766 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-11 02:08:26,767 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:26,877 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-10-11 02:08:26,878 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-10-11 02:08:26,878 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1992935712] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-11 02:08:26,878 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:08:26,878 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2024-10-11 02:08:26,878 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347514076] [2024-10-11 02:08:26,879 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:08:26,879 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-10-11 02:08:26,880 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:26,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-11 02:08:26,881 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-10-11 02:08:26,882 INFO L87 Difference]: Start difference. First operand 74 states and 97 transitions. Second operand has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-11 02:08:26,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:27,000 INFO L93 Difference]: Finished difference Result 87 states and 109 transitions. [2024-10-11 02:08:27,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-11 02:08:27,000 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 49 [2024-10-11 02:08:27,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:27,002 INFO L225 Difference]: With dead ends: 87 [2024-10-11 02:08:27,002 INFO L226 Difference]: Without dead ends: 83 [2024-10-11 02:08:27,002 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2024-10-11 02:08:27,003 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:27,003 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 139 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:08:27,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2024-10-11 02:08:27,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 82. [2024-10-11 02:08:27,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 46 states have (on average 1.173913043478261) internal successors, (54), 49 states have internal predecessors, (54), 25 states have call successors, (25), 10 states have call predecessors, (25), 10 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-10-11 02:08:27,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 102 transitions. [2024-10-11 02:08:27,023 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 102 transitions. Word has length 49 [2024-10-11 02:08:27,023 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:27,024 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 102 transitions. [2024-10-11 02:08:27,024 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.8) internal successors, (14), 5 states have internal predecessors, (14), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-10-11 02:08:27,024 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 102 transitions. [2024-10-11 02:08:27,025 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-10-11 02:08:27,026 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:27,026 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:27,044 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-10-11 02:08:27,230 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:27,231 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:27,231 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:27,231 INFO L85 PathProgramCache]: Analyzing trace with hash -1174147334, now seen corresponding path program 1 times [2024-10-11 02:08:27,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:27,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [313042497] [2024-10-11 02:08:27,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:27,232 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:27,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:08:27,253 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1179431951] [2024-10-11 02:08:27,253 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:27,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:27,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:27,258 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:27,259 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-10-11 02:08:27,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:27,311 INFO L255 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-10-11 02:08:27,314 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:27,507 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-11 02:08:27,507 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:08:27,701 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-10-11 02:08:27,702 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:27,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [313042497] [2024-10-11 02:08:27,702 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:08:27,702 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1179431951] [2024-10-11 02:08:27,702 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1179431951] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:08:27,703 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-10-11 02:08:27,703 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2024-10-11 02:08:27,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1449894332] [2024-10-11 02:08:27,703 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-10-11 02:08:27,704 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-10-11 02:08:27,704 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:27,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-10-11 02:08:27,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2024-10-11 02:08:27,705 INFO L87 Difference]: Start difference. First operand 82 states and 102 transitions. Second operand has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 12 states have internal predecessors, (28), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-10-11 02:08:28,293 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:28,293 INFO L93 Difference]: Finished difference Result 106 states and 139 transitions. [2024-10-11 02:08:28,293 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-11 02:08:28,293 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 12 states have internal predecessors, (28), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) Word has length 51 [2024-10-11 02:08:28,294 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:28,295 INFO L225 Difference]: With dead ends: 106 [2024-10-11 02:08:28,295 INFO L226 Difference]: Without dead ends: 91 [2024-10-11 02:08:28,295 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=54, Invalid=186, Unknown=0, NotChecked=0, Total=240 [2024-10-11 02:08:28,296 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 16 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 145 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 189 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 145 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:28,296 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 169 Invalid, 189 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 145 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-10-11 02:08:28,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-10-11 02:08:28,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 74. [2024-10-11 02:08:28,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 43 states have (on average 1.1627906976744187) internal successors, (50), 45 states have internal predecessors, (50), 21 states have call successors, (21), 9 states have call predecessors, (21), 9 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2024-10-11 02:08:28,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 90 transitions. [2024-10-11 02:08:28,326 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 90 transitions. Word has length 51 [2024-10-11 02:08:28,326 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:28,326 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 90 transitions. [2024-10-11 02:08:28,328 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.1538461538461537) internal successors, (28), 12 states have internal predecessors, (28), 6 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 6 states have call successors, (12) [2024-10-11 02:08:28,328 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 90 transitions. [2024-10-11 02:08:28,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-10-11 02:08:28,330 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:28,331 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:28,348 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-10-11 02:08:28,531 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-10-11 02:08:28,531 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:28,532 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:28,532 INFO L85 PathProgramCache]: Analyzing trace with hash 649788874, now seen corresponding path program 1 times [2024-10-11 02:08:28,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:28,532 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1185825798] [2024-10-11 02:08:28,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:28,532 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:28,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-10-11 02:08:28,558 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1452075939] [2024-10-11 02:08:28,558 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:28,558 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:28,559 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:28,560 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:28,562 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-10-11 02:08:28,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:28,620 INFO L255 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-10-11 02:08:28,622 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:28,794 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-10-11 02:08:28,794 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:08:28,895 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2024-10-11 02:08:28,896 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:28,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1185825798] [2024-10-11 02:08:28,896 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-10-11 02:08:28,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1452075939] [2024-10-11 02:08:28,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1452075939] provided 1 perfect and 1 imperfect interpolant sequences [2024-10-11 02:08:28,896 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-10-11 02:08:28,897 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2024-10-11 02:08:28,897 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1606036619] [2024-10-11 02:08:28,897 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-11 02:08:28,897 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-10-11 02:08:28,897 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:28,898 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-10-11 02:08:28,898 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-10-11 02:08:28,898 INFO L87 Difference]: Start difference. First operand 74 states and 90 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-11 02:08:29,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:29,019 INFO L93 Difference]: Finished difference Result 80 states and 95 transitions. [2024-10-11 02:08:29,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-10-11 02:08:29,019 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 64 [2024-10-11 02:08:29,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:29,020 INFO L225 Difference]: With dead ends: 80 [2024-10-11 02:08:29,020 INFO L226 Difference]: Without dead ends: 75 [2024-10-11 02:08:29,021 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 118 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-10-11 02:08:29,021 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 4 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:29,022 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 102 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:08:29,022 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2024-10-11 02:08:29,037 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 73. [2024-10-11 02:08:29,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 45 states have (on average 1.1333333333333333) internal successors, (51), 45 states have internal predecessors, (51), 18 states have call successors, (18), 10 states have call predecessors, (18), 9 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2024-10-11 02:08:29,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 86 transitions. [2024-10-11 02:08:29,040 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 86 transitions. Word has length 64 [2024-10-11 02:08:29,040 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:29,041 INFO L471 AbstractCegarLoop]: Abstraction has 73 states and 86 transitions. [2024-10-11 02:08:29,041 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), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-10-11 02:08:29,041 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 86 transitions. [2024-10-11 02:08:29,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-10-11 02:08:29,042 INFO L207 NwaCegarLoop]: Found error trace [2024-10-11 02:08:29,042 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:29,061 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-10-11 02:08:29,242 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:29,243 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-10-11 02:08:29,243 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-11 02:08:29,243 INFO L85 PathProgramCache]: Analyzing trace with hash 1853851877, now seen corresponding path program 1 times [2024-10-11 02:08:29,243 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-11 02:08:29,243 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1055136674] [2024-10-11 02:08:29,243 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:29,243 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-11 02:08:29,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,441 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-10-11 02:08:29,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,444 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-10-11 02:08:29,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,445 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-10-11 02:08:29,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,449 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-10-11 02:08:29,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,451 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-10-11 02:08:29,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,453 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-10-11 02:08:29,454 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,455 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-11 02:08:29,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,457 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-10-11 02:08:29,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,462 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-10-11 02:08:29,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,493 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-10-11 02:08:29,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,503 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 58 [2024-10-11 02:08:29,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,507 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-10-11 02:08:29,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-11 02:08:29,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1055136674] [2024-10-11 02:08:29,508 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1055136674] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-11 02:08:29,508 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [691665070] [2024-10-11 02:08:29,508 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-11 02:08:29,508 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:29,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-11 02:08:29,510 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-11 02:08:29,512 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-10-11 02:08:29,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-11 02:08:29,562 INFO L255 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-10-11 02:08:29,564 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-11 02:08:29,611 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-10-11 02:08:29,612 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-11 02:08:29,705 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-10-11 02:08:29,705 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [691665070] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-11 02:08:29,705 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-11 02:08:29,705 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 11 [2024-10-11 02:08:29,706 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1297903004] [2024-10-11 02:08:29,706 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-11 02:08:29,706 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-10-11 02:08:29,706 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-11 02:08:29,707 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-11 02:08:29,707 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-10-11 02:08:29,707 INFO L87 Difference]: Start difference. First operand 73 states and 86 transitions. Second operand has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-11 02:08:29,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-11 02:08:29,840 INFO L93 Difference]: Finished difference Result 80 states and 94 transitions. [2024-10-11 02:08:29,840 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-10-11 02:08:29,840 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 67 [2024-10-11 02:08:29,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-10-11 02:08:29,841 INFO L225 Difference]: With dead ends: 80 [2024-10-11 02:08:29,841 INFO L226 Difference]: Without dead ends: 0 [2024-10-11 02:08:29,842 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 151 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-10-11 02:08:29,842 INFO L432 NwaCegarLoop]: 22 mSDtfsCounter, 8 mSDsluCounter, 114 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-10-11 02:08:29,843 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 136 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-10-11 02:08:29,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-10-11 02:08:29,843 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-10-11 02:08:29,844 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-11 02:08:29,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-10-11 02:08:29,844 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 67 [2024-10-11 02:08:29,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-10-11 02:08:29,844 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-11 02:08:29,844 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.4) internal successors, (24), 8 states have internal predecessors, (24), 4 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-10-11 02:08:29,845 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-10-11 02:08:29,845 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-10-11 02:08:29,847 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-10-11 02:08:29,864 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-10-11 02:08:30,051 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,9 /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-11 02:08:30,055 INFO L407 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-11 02:08:30,056 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-10-11 02:08:35,505 INFO L165 ceAbstractionStarter]: Computing trace abstraction results [2024-10-11 02:08:35,524 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 11.10 02:08:35 BoogieIcfgContainer [2024-10-11 02:08:35,524 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-10-11 02:08:35,525 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-11 02:08:35,525 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-11 02:08:35,525 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-11 02:08:35,525 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.10 02:08:23" (3/4) ... [2024-10-11 02:08:35,527 INFO L139 WitnessPrinter]: Generating witness for correct program [2024-10-11 02:08:35,531 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-10-11 02:08:35,531 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-10-11 02:08:35,534 INFO L904 BoogieBacktranslator]: Reduced CFG by removing 15 nodes and edges [2024-10-11 02:08:35,534 INFO L904 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2024-10-11 02:08:35,535 INFO L904 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-10-11 02:08:35,535 INFO L904 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-10-11 02:08:35,625 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-10-11 02:08:35,626 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/witness.yml [2024-10-11 02:08:35,626 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-11 02:08:35,626 INFO L158 Benchmark]: Toolchain (without parser) took 12667.08ms. Allocated memory was 115.3MB in the beginning and 172.0MB in the end (delta: 56.6MB). Free memory was 46.9MB in the beginning and 100.6MB in the end (delta: -53.7MB). Peak memory consumption was 4.7MB. Max. memory is 16.1GB. [2024-10-11 02:08:35,627 INFO L158 Benchmark]: CDTParser took 0.57ms. Allocated memory is still 115.3MB. Free memory was 73.8MB in the beginning and 73.6MB in the end (delta: 241.2kB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-11 02:08:35,627 INFO L158 Benchmark]: CACSL2BoogieTranslator took 261.62ms. Allocated memory was 115.3MB in the beginning and 142.6MB in the end (delta: 27.3MB). Free memory was 46.7MB in the beginning and 110.1MB in the end (delta: -63.4MB). Peak memory consumption was 14.3MB. Max. memory is 16.1GB. [2024-10-11 02:08:35,627 INFO L158 Benchmark]: Boogie Procedure Inliner took 39.18ms. Allocated memory is still 142.6MB. Free memory was 110.1MB in the beginning and 108.0MB in the end (delta: 2.0MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-11 02:08:35,628 INFO L158 Benchmark]: Boogie Preprocessor took 33.29ms. Allocated memory is still 142.6MB. Free memory was 108.0MB in the beginning and 106.8MB in the end (delta: 1.2MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-11 02:08:35,628 INFO L158 Benchmark]: RCFGBuilder took 369.81ms. Allocated memory is still 142.6MB. Free memory was 105.9MB in the beginning and 93.4MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-10-11 02:08:35,628 INFO L158 Benchmark]: TraceAbstraction took 11853.36ms. Allocated memory was 142.6MB in the beginning and 172.0MB in the end (delta: 29.4MB). Free memory was 93.1MB in the beginning and 105.8MB in the end (delta: -12.7MB). Peak memory consumption was 80.9MB. Max. memory is 16.1GB. [2024-10-11 02:08:35,628 INFO L158 Benchmark]: Witness Printer took 101.38ms. Allocated memory is still 172.0MB. Free memory was 105.8MB in the beginning and 100.6MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-10-11 02:08:35,630 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.57ms. Allocated memory is still 115.3MB. Free memory was 73.8MB in the beginning and 73.6MB in the end (delta: 241.2kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 261.62ms. Allocated memory was 115.3MB in the beginning and 142.6MB in the end (delta: 27.3MB). Free memory was 46.7MB in the beginning and 110.1MB in the end (delta: -63.4MB). Peak memory consumption was 14.3MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 39.18ms. Allocated memory is still 142.6MB. Free memory was 110.1MB in the beginning and 108.0MB in the end (delta: 2.0MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 33.29ms. Allocated memory is still 142.6MB. Free memory was 108.0MB in the beginning and 106.8MB in the end (delta: 1.2MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 369.81ms. Allocated memory is still 142.6MB. Free memory was 105.9MB in the beginning and 93.4MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * TraceAbstraction took 11853.36ms. Allocated memory was 142.6MB in the beginning and 172.0MB in the end (delta: 29.4MB). Free memory was 93.1MB in the beginning and 105.8MB in the end (delta: -12.7MB). Peak memory consumption was 80.9MB. Max. memory is 16.1GB. * Witness Printer took 101.38ms. Allocated memory is still 172.0MB. Free memory was 105.8MB in the beginning and 100.6MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 6.3s, OverallIterations: 9, TraceHistogramMax: 8, PathProgramHistogramMax: 1, EmptinessCheckTime: 0.0s, AutomataDifference: 1.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 83 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 58 mSDsluCounter, 1134 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 863 mSDsCounter, 62 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 488 IncrementalHoareTripleChecker+Invalid, 550 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 62 mSolverCounterUnsat, 271 mSDtfsCounter, 488 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 634 GetRequests, 567 SyntacticMatches, 4 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 0.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=82occurred in iteration=6, InterpolantAutomatonStates: 53, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 31 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 2.2s InterpolantComputationTime, 796 NumberOfCodeBlocks, 796 NumberOfCodeBlocksAsserted, 17 NumberOfCheckSat, 704 ConstructedInterpolants, 0 QuantifiedInterpolants, 1916 SizeOfPredicates, 14 NumberOfNonLiveVariables, 956 ConjunctsInSsa, 110 ConjunctsInUnsatCore, 14 InterpolantComputations, 7 PerfectInterpolantSequences, 933/991 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 35]: Loop Invariant Derived loop invariant: (((((__int128) p * s) == (((__int128) q * r) + 1)) && (((((__int128) r * y) + b) + ((__int128) p * x)) == ((a + ((__int128) s * y)) + ((__int128) q * x)))) && ((((__int128) r * y) + ((__int128) p * x)) == a)) - ProcedureContractResult [Line: 10]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= cond) Ensures: (1 <= cond) RESULT: Ultimate proved your program to be correct! [2024-10-11 02:08:35,652 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE