./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench/egcd2-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 023d838f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench/egcd2-ll.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-09 22:25:58,269 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 22:25:58,342 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-09 22:25:58,348 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 22:25:58,349 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 22:25:58,370 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 22:25:58,370 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 22:25:58,371 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 22:25:58,371 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 22:25:58,373 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 22:25:58,373 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 22:25:58,373 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 22:25:58,374 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 22:25:58,374 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 22:25:58,375 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 22:25:58,375 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 22:25:58,376 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 22:25:58,376 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 22:25:58,376 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 22:25:58,376 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 22:25:58,376 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 22:25:58,377 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 22:25:58,379 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 22:25:58,379 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 22:25:58,379 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 22:25:58,379 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 22:25:58,379 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 22:25:58,380 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 22:25:58,380 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-09 22:25:58,380 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 22:25:58,380 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 22:25:58,380 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 22:25:58,380 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:25:58,381 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 22:25:58,381 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 22:25:58,381 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 22:25:58,381 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 22:25:58,381 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 22:25:58,381 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 22:25:58,381 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 22:25:58,382 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 22:25:58,383 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 22:25:58,383 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! 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 -> ed6536c9cb0e4b2be9a327fc4a25c6bfba6e98b1dfb78e314dd25bca8cbdb087 [2024-11-09 22:25:58,580 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 22:25:58,604 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 22:25:58,606 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 22:25:58,607 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 22:25:58,607 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 22:25:58,608 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench/egcd2-ll.c [2024-11-09 22:25:59,868 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 22:26:00,024 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 22:26:00,024 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench/egcd2-ll.c [2024-11-09 22:26:00,031 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a4da68591/fcf4379f105a47b39468697bef13f9d1/FLAGbeadd0e95 [2024-11-09 22:26:00,433 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a4da68591/fcf4379f105a47b39468697bef13f9d1 [2024-11-09 22:26:00,435 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 22:26:00,436 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 22:26:00,441 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 22:26:00,442 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 22:26:00,447 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 22:26:00,448 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,449 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1e74ab8a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00, skipping insertion in model container [2024-11-09 22:26:00,449 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,465 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 22:26:00,619 WARN L250 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/egcd2-ll.c[490,503] [2024-11-09 22:26:00,637 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:26:00,645 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 22:26:00,654 WARN L250 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/egcd2-ll.c[490,503] [2024-11-09 22:26:00,662 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 22:26:00,676 INFO L204 MainTranslator]: Completed translation [2024-11-09 22:26:00,677 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00 WrapperNode [2024-11-09 22:26:00,677 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 22:26:00,678 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 22:26:00,678 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 22:26:00,678 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 22:26:00,683 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,689 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,703 INFO L138 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 75 [2024-11-09 22:26:00,704 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 22:26:00,704 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 22:26:00,704 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 22:26:00,704 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 22:26:00,712 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,713 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,714 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,726 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-09 22:26:00,726 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,726 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,729 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,729 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,730 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,731 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,732 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 22:26:00,733 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-09 22:26:00,733 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-09 22:26:00,733 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-09 22:26:00,734 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (1/1) ... [2024-11-09 22:26:00,738 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 22:26:00,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:00,764 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-09 22:26:00,766 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-09 22:26:00,802 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 22:26:00,802 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-09 22:26:00,803 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-09 22:26:00,803 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-09 22:26:00,804 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 22:26:00,804 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 22:26:00,804 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 22:26:00,804 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 22:26:00,862 INFO L256 CfgBuilder]: Building ICFG [2024-11-09 22:26:00,865 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 22:26:01,014 INFO L? ?]: Removed 11 outVars from TransFormulas that were not future-live. [2024-11-09 22:26:01,014 INFO L307 CfgBuilder]: Performing block encoding [2024-11-09 22:26:01,032 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 22:26:01,033 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 22:26:01,034 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:26:01 BoogieIcfgContainer [2024-11-09 22:26:01,034 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-09 22:26:01,035 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 22:26:01,036 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 22:26:01,038 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 22:26:01,039 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 10:26:00" (1/3) ... [2024-11-09 22:26:01,039 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@17039f9c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:26:01, skipping insertion in model container [2024-11-09 22:26:01,039 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 10:26:00" (2/3) ... [2024-11-09 22:26:01,040 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@17039f9c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 10:26:01, skipping insertion in model container [2024-11-09 22:26:01,040 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 09.11 10:26:01" (3/3) ... [2024-11-09 22:26:01,041 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd2-ll.c [2024-11-09 22:26:01,055 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 22:26:01,056 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 22:26:01,112 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 22:26:01,118 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;@100cfc1d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 22:26:01,119 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 22:26:01,122 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 23 states have internal predecessors, (30), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-09 22:26:01,129 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-09 22:26:01,130 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:01,131 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:26:01,131 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:01,136 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:01,137 INFO L85 PathProgramCache]: Analyzing trace with hash 1003311343, now seen corresponding path program 1 times [2024-11-09 22:26:01,146 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:01,146 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1556109151] [2024-11-09 22:26:01,147 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:01,147 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:01,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,336 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:26:01,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,346 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:26:01,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,355 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:26:01,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:26:01,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,375 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-09 22:26:01,376 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:01,376 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1556109151] [2024-11-09 22:26:01,377 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1556109151] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:26:01,377 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:26:01,377 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 22:26:01,379 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1817015154] [2024-11-09 22:26:01,380 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:26:01,383 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 22:26:01,384 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:01,406 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 22:26:01,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:26:01,410 INFO L87 Difference]: Start difference. First operand has 35 states, 21 states have (on average 1.4285714285714286) internal successors, (30), 23 states have internal predecessors, (30), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 22:26:01,430 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:01,431 INFO L93 Difference]: Finished difference Result 67 states and 106 transitions. [2024-11-09 22:26:01,433 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 22:26:01,434 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-11-09 22:26:01,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:01,440 INFO L225 Difference]: With dead ends: 67 [2024-11-09 22:26:01,441 INFO L226 Difference]: Without dead ends: 31 [2024-11-09 22:26:01,445 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 22:26:01,448 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:01,450 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:26:01,465 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-11-09 22:26:01,483 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-11-09 22:26:01,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-09 22:26:01,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 40 transitions. [2024-11-09 22:26:01,488 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 40 transitions. Word has length 29 [2024-11-09 22:26:01,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:01,489 INFO L471 AbstractCegarLoop]: Abstraction has 31 states and 40 transitions. [2024-11-09 22:26:01,489 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 22:26:01,489 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 40 transitions. [2024-11-09 22:26:01,492 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-09 22:26:01,492 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:01,492 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:26:01,493 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 22:26:01,493 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:01,494 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:01,495 INFO L85 PathProgramCache]: Analyzing trace with hash 771037684, now seen corresponding path program 1 times [2024-11-09 22:26:01,495 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:01,495 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2131624779] [2024-11-09 22:26:01,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:01,496 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:01,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,695 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:26:01,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,699 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:26:01,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,740 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:26:01,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,755 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:26:01,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,769 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-09 22:26:01,769 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:01,769 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2131624779] [2024-11-09 22:26:01,770 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2131624779] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:26:01,770 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [732722886] [2024-11-09 22:26:01,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:01,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:01,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:01,776 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:01,782 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 22:26:01,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:01,852 INFO L255 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 22:26:01,858 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:02,000 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-09 22:26:02,001 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:26:02,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [732722886] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:26:02,001 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:26:02,001 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2024-11-09 22:26:02,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1338318799] [2024-11-09 22:26:02,002 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:26:02,002 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-09 22:26:02,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:02,005 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-09 22:26:02,006 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2024-11-09 22:26:02,006 INFO L87 Difference]: Start difference. First operand 31 states and 40 transitions. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 22:26:02,134 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:02,134 INFO L93 Difference]: Finished difference Result 51 states and 66 transitions. [2024-11-09 22:26:02,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-09 22:26:02,136 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 31 [2024-11-09 22:26:02,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:02,137 INFO L225 Difference]: With dead ends: 51 [2024-11-09 22:26:02,137 INFO L226 Difference]: Without dead ends: 48 [2024-11-09 22:26:02,137 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2024-11-09 22:26:02,138 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 8 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:02,138 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 141 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:26:02,139 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-09 22:26:02,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 46. [2024-11-09 22:26:02,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-09 22:26:02,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 61 transitions. [2024-11-09 22:26:02,154 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 61 transitions. Word has length 31 [2024-11-09 22:26:02,154 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:02,154 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 61 transitions. [2024-11-09 22:26:02,154 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 3 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-09 22:26:02,154 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 61 transitions. [2024-11-09 22:26:02,155 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-09 22:26:02,155 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:02,155 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:26:02,169 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-11-09 22:26:02,356 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:02,356 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:02,357 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:02,357 INFO L85 PathProgramCache]: Analyzing trace with hash -1107911909, now seen corresponding path program 1 times [2024-11-09 22:26:02,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:02,357 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1860806382] [2024-11-09 22:26:02,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:02,357 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:02,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:02,388 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1450129900] [2024-11-09 22:26:02,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:02,388 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:02,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:02,393 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:02,394 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 22:26:02,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:02,436 INFO L255 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 22:26:02,438 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:02,491 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-09 22:26:02,495 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:26:02,495 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:02,495 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1860806382] [2024-11-09 22:26:02,496 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:26:02,496 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1450129900] [2024-11-09 22:26:02,496 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1450129900] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:26:02,497 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:26:02,497 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:26:02,497 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [389496795] [2024-11-09 22:26:02,497 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:26:02,498 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:26:02,498 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:02,498 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:26:02,499 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:26:02,499 INFO L87 Difference]: Start difference. First operand 46 states and 61 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, (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-11-09 22:26:02,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:02,543 INFO L93 Difference]: Finished difference Result 68 states and 92 transitions. [2024-11-09 22:26:02,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:26:02,544 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, (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 33 [2024-11-09 22:26:02,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:02,547 INFO L225 Difference]: With dead ends: 68 [2024-11-09 22:26:02,547 INFO L226 Difference]: Without dead ends: 65 [2024-11-09 22:26:02,547 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-11-09 22:26:02,548 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 4 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:02,548 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 135 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:26:02,549 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-11-09 22:26:02,565 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 56. [2024-11-09 22:26:02,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 34 states have (on average 1.1470588235294117) internal successors, (39), 38 states have internal predecessors, (39), 17 states have call successors, (17), 4 states have call predecessors, (17), 4 states have return successors, (16), 13 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-09 22:26:02,566 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 72 transitions. [2024-11-09 22:26:02,566 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 72 transitions. Word has length 33 [2024-11-09 22:26:02,566 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:02,566 INFO L471 AbstractCegarLoop]: Abstraction has 56 states and 72 transitions. [2024-11-09 22:26:02,567 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, (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-11-09 22:26:02,567 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 72 transitions. [2024-11-09 22:26:02,569 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-11-09 22:26:02,569 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:02,570 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, 1, 1, 1] [2024-11-09 22:26:02,582 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 22:26:02,773 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-09 22:26:02,775 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:02,775 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:02,775 INFO L85 PathProgramCache]: Analyzing trace with hash -636157296, now seen corresponding path program 1 times [2024-11-09 22:26:02,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:02,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [483254478] [2024-11-09 22:26:02,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:02,776 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:02,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:02,905 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:26:02,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:02,913 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:26:02,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:02,938 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:26:02,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:02,944 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:26:02,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:02,949 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 22:26:02,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:02,952 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-09 22:26:02,953 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:02,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [483254478] [2024-11-09 22:26:02,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [483254478] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:26:02,953 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1395595286] [2024-11-09 22:26:02,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:02,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:02,954 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:02,955 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:02,956 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 22:26:03,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:03,005 INFO L255 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 22:26:03,006 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:03,101 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-09 22:26:03,101 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:26:03,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1395595286] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:26:03,102 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:26:03,102 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 9 [2024-11-09 22:26:03,102 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [889158783] [2024-11-09 22:26:03,102 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:26:03,102 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:26:03,102 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:03,103 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:26:03,103 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:26:03,103 INFO L87 Difference]: Start difference. First operand 56 states and 72 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, (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-11-09 22:26:03,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:03,161 INFO L93 Difference]: Finished difference Result 65 states and 80 transitions. [2024-11-09 22:26:03,163 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:26:03,163 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, (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 36 [2024-11-09 22:26:03,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:03,164 INFO L225 Difference]: With dead ends: 65 [2024-11-09 22:26:03,164 INFO L226 Difference]: Without dead ends: 60 [2024-11-09 22:26:03,164 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2024-11-09 22:26:03,165 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 8 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:03,165 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 138 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:26:03,166 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-09 22:26:03,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-11-09 22:26:03,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 37 states have (on average 1.1081081081081081) internal successors, (41), 40 states have internal predecessors, (41), 16 states have call successors, (16), 5 states have call predecessors, (16), 5 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 22:26:03,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 72 transitions. [2024-11-09 22:26:03,178 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 72 transitions. Word has length 36 [2024-11-09 22:26:03,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:03,178 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 72 transitions. [2024-11-09 22:26:03,181 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, (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-11-09 22:26:03,181 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 72 transitions. [2024-11-09 22:26:03,182 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-09 22:26:03,183 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:03,183 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, 1, 1, 1, 1] [2024-11-09 22:26:03,195 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-09 22:26:03,386 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:03,387 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:03,387 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:03,387 INFO L85 PathProgramCache]: Analyzing trace with hash 1812264393, now seen corresponding path program 1 times [2024-11-09 22:26:03,387 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:03,387 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2053319596] [2024-11-09 22:26:03,387 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:03,388 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:03,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:03,407 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1561222222] [2024-11-09 22:26:03,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:03,408 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:03,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:03,409 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:03,410 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 22:26:03,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:03,466 INFO L255 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 22:26:03,468 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:03,647 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-09 22:26:03,647 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 22:26:03,647 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:03,647 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2053319596] [2024-11-09 22:26:03,648 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:26:03,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1561222222] [2024-11-09 22:26:03,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1561222222] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 22:26:03,648 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 22:26:03,648 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 22:26:03,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1343669117] [2024-11-09 22:26:03,648 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:26:03,649 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:26:03,649 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:03,649 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:26:03,649 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 22:26:03,650 INFO L87 Difference]: Start difference. First operand 59 states and 72 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 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-11-09 22:26:03,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:03,781 INFO L93 Difference]: Finished difference Result 67 states and 79 transitions. [2024-11-09 22:26:03,781 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:26:03,781 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 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 48 [2024-11-09 22:26:03,782 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:03,782 INFO L225 Difference]: With dead ends: 67 [2024-11-09 22:26:03,782 INFO L226 Difference]: Without dead ends: 64 [2024-11-09 22:26:03,782 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 22:26:03,783 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 5 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:03,784 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 126 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:26:03,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2024-11-09 22:26:03,793 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 63. [2024-11-09 22:26:03,793 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 40 states have (on average 1.1) internal successors, (44), 43 states have internal predecessors, (44), 16 states have call successors, (16), 6 states have call predecessors, (16), 6 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-09 22:26:03,794 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 75 transitions. [2024-11-09 22:26:03,794 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 75 transitions. Word has length 48 [2024-11-09 22:26:03,794 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:03,794 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 75 transitions. [2024-11-09 22:26:03,795 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 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-11-09 22:26:03,795 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 75 transitions. [2024-11-09 22:26:03,795 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-09 22:26:03,795 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:03,796 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:26:03,812 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-09 22:26:03,999 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:04,000 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:04,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:04,000 INFO L85 PathProgramCache]: Analyzing trace with hash -419919395, now seen corresponding path program 1 times [2024-11-09 22:26:04,000 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:04,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [290518792] [2024-11-09 22:26:04,000 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:04,000 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:04,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:04,016 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1789215404] [2024-11-09 22:26:04,016 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:04,016 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:04,016 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:04,018 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:04,019 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 22:26:04,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,072 INFO L255 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-09 22:26:04,074 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:04,135 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-09 22:26:04,136 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:26:04,222 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2024-11-09 22:26:04,222 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:04,222 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [290518792] [2024-11-09 22:26:04,223 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:26:04,223 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1789215404] [2024-11-09 22:26:04,223 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1789215404] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-09 22:26:04,223 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:26:04,223 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-09 22:26:04,223 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [154738753] [2024-11-09 22:26:04,223 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 22:26:04,224 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 22:26:04,224 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:04,226 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 22:26:04,227 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-09 22:26:04,227 INFO L87 Difference]: Start difference. First operand 63 states and 75 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-09 22:26:04,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:04,272 INFO L93 Difference]: Finished difference Result 70 states and 81 transitions. [2024-11-09 22:26:04,275 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 22:26:04,276 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 56 [2024-11-09 22:26:04,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:04,277 INFO L225 Difference]: With dead ends: 70 [2024-11-09 22:26:04,277 INFO L226 Difference]: Without dead ends: 67 [2024-11-09 22:26:04,277 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 103 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-09 22:26:04,278 INFO L432 NwaCegarLoop]: 34 mSDtfsCounter, 4 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:04,280 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 121 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 22:26:04,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-09 22:26:04,290 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 57. [2024-11-09 22:26:04,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 36 states have (on average 1.1111111111111112) internal successors, (40), 37 states have internal predecessors, (40), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-09 22:26:04,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 67 transitions. [2024-11-09 22:26:04,293 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 67 transitions. Word has length 56 [2024-11-09 22:26:04,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:04,293 INFO L471 AbstractCegarLoop]: Abstraction has 57 states and 67 transitions. [2024-11-09 22:26:04,294 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-09 22:26:04,294 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 67 transitions. [2024-11-09 22:26:04,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-11-09 22:26:04,295 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:04,295 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:26:04,309 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-09 22:26:04,495 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:04,496 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:04,497 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:04,497 INFO L85 PathProgramCache]: Analyzing trace with hash -1526811961, now seen corresponding path program 1 times [2024-11-09 22:26:04,497 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:04,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1779180265] [2024-11-09 22:26:04,497 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:04,497 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:04,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,614 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 22:26:04,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,635 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-09 22:26:04,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,638 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-09 22:26:04,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,642 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-09 22:26:04,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,644 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-11-09 22:26:04,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,647 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-09 22:26:04,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,650 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-11-09 22:26:04,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,653 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 43 [2024-11-09 22:26:04,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,656 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-09 22:26:04,656 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:04,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1779180265] [2024-11-09 22:26:04,657 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1779180265] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:26:04,657 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1326741506] [2024-11-09 22:26:04,657 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:04,657 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:04,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:04,658 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:04,660 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 22:26:04,703 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:04,706 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-09 22:26:04,708 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:04,734 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-09 22:26:04,734 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:26:04,811 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-09 22:26:04,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1326741506] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:26:04,812 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 22:26:04,812 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 9 [2024-11-09 22:26:04,812 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1786921341] [2024-11-09 22:26:04,812 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 22:26:04,812 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-09 22:26:04,812 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:04,813 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-09 22:26:04,813 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-09 22:26:04,813 INFO L87 Difference]: Start difference. First operand 57 states and 67 transitions. Second operand has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-09 22:26:04,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:04,960 INFO L93 Difference]: Finished difference Result 112 states and 150 transitions. [2024-11-09 22:26:04,962 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 22:26:04,962 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 58 [2024-11-09 22:26:04,962 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:04,963 INFO L225 Difference]: With dead ends: 112 [2024-11-09 22:26:04,963 INFO L226 Difference]: Without dead ends: 103 [2024-11-09 22:26:04,964 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 126 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=114, Unknown=0, NotChecked=0, Total=156 [2024-11-09 22:26:04,964 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 41 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:04,964 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 269 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:26:04,965 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-09 22:26:04,986 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 93. [2024-11-09 22:26:04,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 56 states have (on average 1.1607142857142858) internal successors, (65), 57 states have internal predecessors, (65), 30 states have call successors, (30), 6 states have call predecessors, (30), 6 states have return successors, (29), 29 states have call predecessors, (29), 29 states have call successors, (29) [2024-11-09 22:26:04,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 124 transitions. [2024-11-09 22:26:04,989 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 124 transitions. Word has length 58 [2024-11-09 22:26:04,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:04,990 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 124 transitions. [2024-11-09 22:26:04,991 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-09 22:26:04,991 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 124 transitions. [2024-11-09 22:26:04,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-11-09 22:26:04,992 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:04,992 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 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, 1, 1] [2024-11-09 22:26:05,007 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-09 22:26:05,193 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:05,193 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:05,193 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:05,193 INFO L85 PathProgramCache]: Analyzing trace with hash 580126358, now seen corresponding path program 1 times [2024-11-09 22:26:05,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:05,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1500176513] [2024-11-09 22:26:05,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:05,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:05,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:05,208 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1410536799] [2024-11-09 22:26:05,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:05,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:05,208 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:05,209 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:05,210 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 22:26:05,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:05,257 INFO L255 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-09 22:26:05,259 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:05,501 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 19 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-09 22:26:05,501 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:26:05,610 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-11-09 22:26:05,610 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:05,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1500176513] [2024-11-09 22:26:05,610 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:26:05,610 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1410536799] [2024-11-09 22:26:05,610 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1410536799] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:26:05,611 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:26:05,611 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 6] total 12 [2024-11-09 22:26:05,611 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1144339029] [2024-11-09 22:26:05,611 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:26:05,611 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-09 22:26:05,611 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:05,612 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 22:26:05,612 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2024-11-09 22:26:05,612 INFO L87 Difference]: Start difference. First operand 93 states and 124 transitions. Second operand has 12 states, 11 states have (on average 3.727272727272727) internal successors, (41), 9 states have internal predecessors, (41), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-09 22:26:05,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:05,792 INFO L93 Difference]: Finished difference Result 134 states and 181 transitions. [2024-11-09 22:26:05,792 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 22:26:05,793 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 3.727272727272727) internal successors, (41), 9 states have internal predecessors, (41), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) Word has length 65 [2024-11-09 22:26:05,793 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:05,794 INFO L225 Difference]: With dead ends: 134 [2024-11-09 22:26:05,794 INFO L226 Difference]: Without dead ends: 130 [2024-11-09 22:26:05,794 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 116 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-11-09 22:26:05,795 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 19 mSDsluCounter, 306 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 184 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:05,795 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 348 Invalid, 184 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 22:26:05,795 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2024-11-09 22:26:05,817 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2024-11-09 22:26:05,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 76 states have (on average 1.1710526315789473) internal successors, (89), 78 states have internal predecessors, (89), 43 states have call successors, (43), 7 states have call predecessors, (43), 7 states have return successors, (41), 41 states have call predecessors, (41), 41 states have call successors, (41) [2024-11-09 22:26:05,819 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 173 transitions. [2024-11-09 22:26:05,819 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 173 transitions. Word has length 65 [2024-11-09 22:26:05,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:05,819 INFO L471 AbstractCegarLoop]: Abstraction has 127 states and 173 transitions. [2024-11-09 22:26:05,819 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 3.727272727272727) internal successors, (41), 9 states have internal predecessors, (41), 6 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 7 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-09 22:26:05,819 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 173 transitions. [2024-11-09 22:26:05,820 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-09 22:26:05,820 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:05,820 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 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-11-09 22:26:05,836 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-09 22:26:06,020 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:06,021 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:06,021 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:06,021 INFO L85 PathProgramCache]: Analyzing trace with hash -286503954, now seen corresponding path program 2 times [2024-11-09 22:26:06,021 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:06,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1767207013] [2024-11-09 22:26:06,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:06,022 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:06,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:06,035 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1450715853] [2024-11-09 22:26:06,035 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 22:26:06,036 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:06,036 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:06,038 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:06,040 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-09 22:26:06,094 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 22:26:06,094 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:26:06,095 INFO L255 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-09 22:26:06,097 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:06,446 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 20 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-09 22:26:06,447 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:26:06,576 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 8 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-09 22:26:06,576 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:06,576 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1767207013] [2024-11-09 22:26:06,576 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:26:06,577 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1450715853] [2024-11-09 22:26:06,577 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1450715853] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:26:06,577 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:26:06,577 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 14 [2024-11-09 22:26:06,577 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1950780545] [2024-11-09 22:26:06,577 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:26:06,577 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-09 22:26:06,577 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:06,579 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-09 22:26:06,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2024-11-09 22:26:06,579 INFO L87 Difference]: Start difference. First operand 127 states and 173 transitions. Second operand has 14 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 11 states have internal predecessors, (41), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-09 22:26:07,000 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:07,000 INFO L93 Difference]: Finished difference Result 136 states and 181 transitions. [2024-11-09 22:26:07,000 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-09 22:26:07,001 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 11 states have internal predecessors, (41), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) Word has length 70 [2024-11-09 22:26:07,001 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:07,002 INFO L225 Difference]: With dead ends: 136 [2024-11-09 22:26:07,002 INFO L226 Difference]: Without dead ends: 132 [2024-11-09 22:26:07,003 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 124 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=117, Invalid=389, Unknown=0, NotChecked=0, Total=506 [2024-11-09 22:26:07,003 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 60 mSDsluCounter, 211 mSDsCounter, 0 mSdLazyCounter, 200 mSolverCounterSat, 61 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 244 SdHoareTripleChecker+Invalid, 261 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 61 IncrementalHoareTripleChecker+Valid, 200 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:07,003 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 244 Invalid, 261 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [61 Valid, 200 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 22:26:07,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-09 22:26:07,035 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 129. [2024-11-09 22:26:07,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 79 states have (on average 1.1645569620253164) internal successors, (92), 80 states have internal predecessors, (92), 41 states have call successors, (41), 8 states have call predecessors, (41), 8 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-09 22:26:07,036 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 173 transitions. [2024-11-09 22:26:07,036 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 173 transitions. Word has length 70 [2024-11-09 22:26:07,037 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:07,037 INFO L471 AbstractCegarLoop]: Abstraction has 129 states and 173 transitions. [2024-11-09 22:26:07,037 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.1538461538461537) internal successors, (41), 11 states have internal predecessors, (41), 8 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (20), 9 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-09 22:26:07,038 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 173 transitions. [2024-11-09 22:26:07,040 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-09 22:26:07,040 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:07,040 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:26:07,056 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-09 22:26:07,244 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2024-11-09 22:26:07,244 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:07,245 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:07,245 INFO L85 PathProgramCache]: Analyzing trace with hash 1788591446, now seen corresponding path program 3 times [2024-11-09 22:26:07,245 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:07,245 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1828444820] [2024-11-09 22:26:07,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:07,245 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:07,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:07,259 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1590849231] [2024-11-09 22:26:07,259 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 22:26:07,259 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:07,259 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:07,260 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:07,261 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-09 22:26:07,312 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-09 22:26:07,312 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 22:26:07,313 INFO L255 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 57 conjuncts are in the unsatisfiable core [2024-11-09 22:26:07,317 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:08,197 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 42 proven. 23 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-09 22:26:08,197 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:26:22,229 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:22,229 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1828444820] [2024-11-09 22:26:22,229 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:26:22,229 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1590849231] [2024-11-09 22:26:22,229 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1590849231] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 22:26:22,229 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-09 22:26:22,229 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-11-09 22:26:22,229 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1063693534] [2024-11-09 22:26:22,229 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-09 22:26:22,229 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 22:26:22,230 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:22,230 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 22:26:22,230 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=501, Unknown=0, NotChecked=0, Total=600 [2024-11-09 22:26:22,230 INFO L87 Difference]: Start difference. First operand 129 states and 173 transitions. Second operand has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 12 states have internal predecessors, (31), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-09 22:26:22,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:22,826 INFO L93 Difference]: Finished difference Result 146 states and 187 transitions. [2024-11-09 22:26:22,827 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-09 22:26:22,827 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 12 states have internal predecessors, (31), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) Word has length 75 [2024-11-09 22:26:22,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:22,828 INFO L225 Difference]: With dead ends: 146 [2024-11-09 22:26:22,828 INFO L226 Difference]: Without dead ends: 143 [2024-11-09 22:26:22,828 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 104 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=152, Invalid=660, Unknown=0, NotChecked=0, Total=812 [2024-11-09 22:26:22,829 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 30 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 279 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 298 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 279 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:22,829 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 252 Invalid, 298 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 279 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 22:26:22,829 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-09 22:26:22,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 141. [2024-11-09 22:26:22,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 88 states have (on average 1.1477272727272727) internal successors, (101), 89 states have internal predecessors, (101), 41 states have call successors, (41), 11 states have call predecessors, (41), 11 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-09 22:26:22,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 182 transitions. [2024-11-09 22:26:22,857 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 182 transitions. Word has length 75 [2024-11-09 22:26:22,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:22,858 INFO L471 AbstractCegarLoop]: Abstraction has 141 states and 182 transitions. [2024-11-09 22:26:22,858 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 12 states have internal predecessors, (31), 5 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-09 22:26:22,858 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 182 transitions. [2024-11-09 22:26:22,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-09 22:26:22,861 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:22,861 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 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, 1] [2024-11-09 22:26:22,874 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-09 22:26:23,062 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-09 22:26:23,063 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:23,063 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:23,063 INFO L85 PathProgramCache]: Analyzing trace with hash 1628799557, now seen corresponding path program 1 times [2024-11-09 22:26:23,063 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:23,063 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1099777296] [2024-11-09 22:26:23,063 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:23,063 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:23,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:23,080 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1535560118] [2024-11-09 22:26:23,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:23,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:23,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:23,081 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:23,085 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-09 22:26:23,137 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:23,144 INFO L255 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-09 22:26:23,146 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:23,616 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 19 refuted. 0 times theorem prover too weak. 127 trivial. 0 not checked. [2024-11-09 22:26:23,616 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:26:24,252 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 136 trivial. 0 not checked. [2024-11-09 22:26:24,253 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:26:24,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1099777296] [2024-11-09 22:26:24,253 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:26:24,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1535560118] [2024-11-09 22:26:24,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1535560118] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:26:24,253 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:26:24,253 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 21 [2024-11-09 22:26:24,254 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [946059651] [2024-11-09 22:26:24,254 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:26:24,254 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-09 22:26:24,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:26:24,254 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-09 22:26:24,255 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=356, Unknown=0, NotChecked=0, Total=420 [2024-11-09 22:26:24,255 INFO L87 Difference]: Start difference. First operand 141 states and 182 transitions. Second operand has 21 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 18 states have internal predecessors, (45), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-09 22:26:26,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 22:26:26,724 INFO L93 Difference]: Finished difference Result 260 states and 362 transitions. [2024-11-09 22:26:26,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-09 22:26:26,725 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 18 states have internal predecessors, (45), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 81 [2024-11-09 22:26:26,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 22:26:26,727 INFO L225 Difference]: With dead ends: 260 [2024-11-09 22:26:26,727 INFO L226 Difference]: Without dead ends: 251 [2024-11-09 22:26:26,727 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 141 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 206 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=255, Invalid=1151, Unknown=0, NotChecked=0, Total=1406 [2024-11-09 22:26:26,728 INFO L432 NwaCegarLoop]: 49 mSDtfsCounter, 94 mSDsluCounter, 524 mSDsCounter, 0 mSdLazyCounter, 493 mSolverCounterSat, 106 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 573 SdHoareTripleChecker+Invalid, 599 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 106 IncrementalHoareTripleChecker+Valid, 493 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-09 22:26:26,728 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [98 Valid, 573 Invalid, 599 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [106 Valid, 493 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-09 22:26:26,732 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 251 states. [2024-11-09 22:26:26,794 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 251 to 249. [2024-11-09 22:26:26,795 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 249 states, 146 states have (on average 1.1712328767123288) internal successors, (171), 147 states have internal predecessors, (171), 89 states have call successors, (89), 13 states have call predecessors, (89), 13 states have return successors, (88), 88 states have call predecessors, (88), 88 states have call successors, (88) [2024-11-09 22:26:26,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 249 states to 249 states and 348 transitions. [2024-11-09 22:26:26,797 INFO L78 Accepts]: Start accepts. Automaton has 249 states and 348 transitions. Word has length 81 [2024-11-09 22:26:26,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 22:26:26,798 INFO L471 AbstractCegarLoop]: Abstraction has 249 states and 348 transitions. [2024-11-09 22:26:26,798 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 19 states have (on average 2.3684210526315788) internal successors, (45), 18 states have internal predecessors, (45), 10 states have call successors, (25), 3 states have call predecessors, (25), 2 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2024-11-09 22:26:26,798 INFO L276 IsEmpty]: Start isEmpty. Operand 249 states and 348 transitions. [2024-11-09 22:26:26,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-09 22:26:26,799 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 22:26:26,799 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 22:26:26,812 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-09 22:26:27,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-11-09 22:26:27,000 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 22:26:27,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 22:26:27,000 INFO L85 PathProgramCache]: Analyzing trace with hash 1391073688, now seen corresponding path program 1 times [2024-11-09 22:26:27,000 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 22:26:27,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [539802320] [2024-11-09 22:26:27,000 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:27,000 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 22:26:27,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 22:26:27,021 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1018481806] [2024-11-09 22:26:27,021 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 22:26:27,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 22:26:27,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 22:26:27,023 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 22:26:27,025 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-09 22:26:27,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 22:26:27,082 INFO L255 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 54 conjuncts are in the unsatisfiable core [2024-11-09 22:26:27,084 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 22:26:27,882 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 39 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2024-11-09 22:26:27,882 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 22:26:56,770 WARN L286 SmtUtils]: Spent 5.25s on a formula simplification that was a NOOP. DAG size: 7 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 22:27:02,697 INFO L134 CoverageAnalysis]: Checked inductivity of 288 backedges. 68 proven. 30 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2024-11-09 22:27:02,697 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 22:27:02,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [539802320] [2024-11-09 22:27:02,697 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 22:27:02,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1018481806] [2024-11-09 22:27:02,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1018481806] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 22:27:02,697 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 22:27:02,697 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 25 [2024-11-09 22:27:02,697 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [360842294] [2024-11-09 22:27:02,697 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 22:27:02,698 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-09 22:27:02,698 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 22:27:02,698 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-09 22:27:02,699 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=488, Unknown=0, NotChecked=0, Total=600 [2024-11-09 22:27:02,699 INFO L87 Difference]: Start difference. First operand 249 states and 348 transitions. Second operand has 25 states, 24 states have (on average 2.25) internal successors, (54), 21 states have internal predecessors, (54), 11 states have call successors, (31), 3 states have call predecessors, (31), 3 states have return successors, (30), 12 states have call predecessors, (30), 10 states have call successors, (30) [2024-11-09 22:27:07,798 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:27:15,962 WARN L286 SmtUtils]: Spent 7.69s on a formula simplification. DAG size of input: 61 DAG size of output: 60 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:27:24,918 WARN L286 SmtUtils]: Spent 5.84s on a formula simplification. DAG size of input: 65 DAG size of output: 64 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 22:27:29,125 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:27:33,147 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 22:27:37,159 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []