./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/loops-crafted-1/nested3-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8be7027f 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/loops-crafted-1/nested3-1.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 ed8e064f31e82b4c33cb383334d25637eef982ae8d5b8603579b97c7fdfe808e --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dk.perfect-tracechecks-8be7027-m [2024-11-11 19:51:25,238 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-11 19:51:25,294 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-11 19:51:25,299 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-11 19:51:25,300 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-11 19:51:25,326 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-11 19:51:25,326 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-11 19:51:25,327 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-11 19:51:25,327 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-11 19:51:25,328 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-11 19:51:25,328 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-11 19:51:25,328 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-11 19:51:25,329 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-11 19:51:25,329 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-11 19:51:25,331 INFO L153 SettingsManager]: * Use SBE=true [2024-11-11 19:51:25,331 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-11 19:51:25,332 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-11 19:51:25,332 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-11 19:51:25,332 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-11 19:51:25,332 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-11 19:51:25,332 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-11 19:51:25,335 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-11 19:51:25,335 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-11 19:51:25,336 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-11 19:51:25,336 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-11 19:51:25,336 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-11 19:51:25,336 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-11 19:51:25,336 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-11 19:51:25,337 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-11 19:51:25,337 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-11 19:51:25,337 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-11 19:51:25,337 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-11 19:51:25,337 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 19:51:25,337 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-11 19:51:25,337 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-11 19:51:25,338 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-11 19:51:25,338 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-11 19:51:25,338 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-11 19:51:25,338 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-11 19:51:25,338 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-11 19:51:25,338 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-11 19:51:25,339 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-11 19:51:25,339 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 -> ed8e064f31e82b4c33cb383334d25637eef982ae8d5b8603579b97c7fdfe808e [2024-11-11 19:51:25,555 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-11 19:51:25,575 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-11 19:51:25,577 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-11 19:51:25,578 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-11 19:51:25,579 INFO L274 PluginConnector]: CDTParser initialized [2024-11-11 19:51:25,579 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/loops-crafted-1/nested3-1.c [2024-11-11 19:51:26,903 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-11 19:51:27,057 INFO L384 CDTParser]: Found 1 translation units. [2024-11-11 19:51:27,058 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/loops-crafted-1/nested3-1.c [2024-11-11 19:51:27,064 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5ee020f02/8e3579fa44c94cef894522b57c2947ab/FLAGa1058ff31 [2024-11-11 19:51:27,464 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5ee020f02/8e3579fa44c94cef894522b57c2947ab [2024-11-11 19:51:27,466 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-11 19:51:27,467 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-11 19:51:27,470 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-11 19:51:27,470 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-11 19:51:27,474 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-11 19:51:27,475 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,476 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2fd2cffc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27, skipping insertion in model container [2024-11-11 19:51:27,476 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,489 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-11 19:51:27,625 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/loops-crafted-1/nested3-1.c[321,334] [2024-11-11 19:51:27,635 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 19:51:27,641 INFO L200 MainTranslator]: Completed pre-run [2024-11-11 19:51:27,649 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/loops-crafted-1/nested3-1.c[321,334] [2024-11-11 19:51:27,658 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 19:51:27,669 INFO L204 MainTranslator]: Completed translation [2024-11-11 19:51:27,670 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27 WrapperNode [2024-11-11 19:51:27,670 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-11 19:51:27,671 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-11 19:51:27,671 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-11 19:51:27,671 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-11 19:51:27,676 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,680 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,691 INFO L138 Inliner]: procedures = 12, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 41 [2024-11-11 19:51:27,691 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-11 19:51:27,692 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-11 19:51:27,692 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-11 19:51:27,692 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-11 19:51:27,699 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,699 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,700 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,734 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-11 19:51:27,734 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,735 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,736 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,739 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,739 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,740 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,742 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-11 19:51:27,742 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-11 19:51:27,742 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-11 19:51:27,742 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-11 19:51:27,743 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (1/1) ... [2024-11-11 19:51:27,751 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 19:51:27,760 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:27,780 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-11 19:51:27,791 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-11 19:51:27,844 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-11 19:51:27,845 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-11 19:51:27,845 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-11 19:51:27,845 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-11 19:51:27,845 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-11 19:51:27,845 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-11 19:51:27,890 INFO L238 CfgBuilder]: Building ICFG [2024-11-11 19:51:27,892 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-11 19:51:27,992 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-11 19:51:27,993 INFO L287 CfgBuilder]: Performing block encoding [2024-11-11 19:51:28,001 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-11 19:51:28,001 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-11 19:51:28,001 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 07:51:28 BoogieIcfgContainer [2024-11-11 19:51:28,002 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-11 19:51:28,003 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-11 19:51:28,003 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-11 19:51:28,006 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-11 19:51:28,006 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.11 07:51:27" (1/3) ... [2024-11-11 19:51:28,007 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31c326e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 07:51:28, skipping insertion in model container [2024-11-11 19:51:28,007 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 07:51:27" (2/3) ... [2024-11-11 19:51:28,007 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@31c326e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 07:51:28, skipping insertion in model container [2024-11-11 19:51:28,007 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 07:51:28" (3/3) ... [2024-11-11 19:51:28,009 INFO L112 eAbstractionObserver]: Analyzing ICFG nested3-1.c [2024-11-11 19:51:28,020 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-11 19:51:28,020 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-11 19:51:28,058 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-11 19:51:28,062 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;@25311da5, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-11 19:51:28,063 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-11 19:51:28,065 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 14 states have (on average 1.5714285714285714) internal successors, (22), 15 states have internal predecessors, (22), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 19:51:28,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2024-11-11 19:51:28,069 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:28,070 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:28,070 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:28,074 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:28,074 INFO L85 PathProgramCache]: Analyzing trace with hash 1810304921, now seen corresponding path program 1 times [2024-11-11 19:51:28,081 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:28,081 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1539105760] [2024-11-11 19:51:28,081 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:28,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:28,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:28,270 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:28,271 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:28,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1539105760] [2024-11-11 19:51:28,273 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1539105760] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:51:28,273 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:51:28,273 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-11 19:51:28,274 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [782890857] [2024-11-11 19:51:28,275 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:51:28,278 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-11 19:51:28,278 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:28,297 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-11 19:51:28,297 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 19:51:28,299 INFO L87 Difference]: Start difference. First operand has 20 states, 14 states have (on average 1.5714285714285714) internal successors, (22), 15 states have internal predecessors, (22), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,330 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:28,330 INFO L93 Difference]: Finished difference Result 45 states and 74 transitions. [2024-11-11 19:51:28,331 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-11 19:51:28,336 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2024-11-11 19:51:28,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:28,341 INFO L225 Difference]: With dead ends: 45 [2024-11-11 19:51:28,341 INFO L226 Difference]: Without dead ends: 23 [2024-11-11 19:51:28,343 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 19:51:28,346 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 6 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 6 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 6 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:28,347 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 43 Invalid, 6 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 6 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:51:28,359 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2024-11-11 19:51:28,372 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 17. [2024-11-11 19:51:28,374 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 12 states have (on average 1.3333333333333333) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-11 19:51:28,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-11-11 19:51:28,376 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 7 [2024-11-11 19:51:28,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:28,377 INFO L471 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-11-11 19:51:28,377 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,377 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2024-11-11 19:51:28,377 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2024-11-11 19:51:28,378 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:28,378 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:28,378 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-11 19:51:28,378 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:28,379 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:28,379 INFO L85 PathProgramCache]: Analyzing trace with hash 300961951, now seen corresponding path program 1 times [2024-11-11 19:51:28,379 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:28,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2126088502] [2024-11-11 19:51:28,379 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:28,380 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:28,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:28,460 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:28,460 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:28,460 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2126088502] [2024-11-11 19:51:28,460 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2126088502] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:51:28,460 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:51:28,460 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-11 19:51:28,460 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1692702840] [2024-11-11 19:51:28,461 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:51:28,462 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-11 19:51:28,463 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:28,463 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-11 19:51:28,463 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 19:51:28,464 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:28,499 INFO L93 Difference]: Finished difference Result 35 states and 46 transitions. [2024-11-11 19:51:28,500 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-11 19:51:28,500 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2024-11-11 19:51:28,500 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:28,501 INFO L225 Difference]: With dead ends: 35 [2024-11-11 19:51:28,501 INFO L226 Difference]: Without dead ends: 21 [2024-11-11 19:51:28,501 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 19:51:28,502 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 3 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 5 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 5 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 5 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:28,502 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 34 Invalid, 5 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 5 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:51:28,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2024-11-11 19:51:28,510 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 18. [2024-11-11 19:51:28,510 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-11 19:51:28,511 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 22 transitions. [2024-11-11 19:51:28,511 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 22 transitions. Word has length 8 [2024-11-11 19:51:28,511 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:28,511 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 22 transitions. [2024-11-11 19:51:28,511 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,511 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 22 transitions. [2024-11-11 19:51:28,512 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-11-11 19:51:28,515 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:28,515 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:28,515 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-11 19:51:28,515 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:28,516 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:28,516 INFO L85 PathProgramCache]: Analyzing trace with hash 766069286, now seen corresponding path program 1 times [2024-11-11 19:51:28,516 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:28,516 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [122449254] [2024-11-11 19:51:28,516 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:28,516 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:28,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:28,571 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:28,571 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:28,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [122449254] [2024-11-11 19:51:28,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [122449254] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:51:28,571 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 19:51:28,571 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-11 19:51:28,571 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [74848823] [2024-11-11 19:51:28,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:51:28,572 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-11 19:51:28,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:28,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-11 19:51:28,572 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 19:51:28,572 INFO L87 Difference]: Start difference. First operand 18 states and 22 transitions. Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:28,583 INFO L93 Difference]: Finished difference Result 34 states and 43 transitions. [2024-11-11 19:51:28,583 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-11 19:51:28,583 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2024-11-11 19:51:28,583 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:28,584 INFO L225 Difference]: With dead ends: 34 [2024-11-11 19:51:28,584 INFO L226 Difference]: Without dead ends: 19 [2024-11-11 19:51:28,584 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 19:51:28,585 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 36 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:28,585 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 36 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:51:28,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2024-11-11 19:51:28,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2024-11-11 19:51:28,591 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-11 19:51:28,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 23 transitions. [2024-11-11 19:51:28,592 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 23 transitions. Word has length 9 [2024-11-11 19:51:28,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:28,593 INFO L471 AbstractCegarLoop]: Abstraction has 19 states and 23 transitions. [2024-11-11 19:51:28,593 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,594 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 23 transitions. [2024-11-11 19:51:28,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-11 19:51:28,594 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:28,594 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:28,594 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-11 19:51:28,594 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:28,595 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:28,597 INFO L85 PathProgramCache]: Analyzing trace with hash -1993625471, now seen corresponding path program 1 times [2024-11-11 19:51:28,597 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:28,597 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1750040482] [2024-11-11 19:51:28,597 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:28,598 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:28,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:28,705 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:28,707 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:28,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1750040482] [2024-11-11 19:51:28,707 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1750040482] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:51:28,710 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1541174377] [2024-11-11 19:51:28,710 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:28,710 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:28,711 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:28,712 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-11 19:51:28,716 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-11 19:51:28,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:28,756 INFO L256 TraceCheckSpWp]: Trace formula consists of 48 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-11 19:51:28,759 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:51:28,802 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:28,803 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:51:28,876 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:28,877 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1541174377] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:51:28,883 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:51:28,883 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 6, 6] total 11 [2024-11-11 19:51:28,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2031669952] [2024-11-11 19:51:28,884 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:51:28,884 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-11 19:51:28,884 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:28,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-11 19:51:28,885 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-11-11 19:51:28,885 INFO L87 Difference]: Start difference. First operand 19 states and 23 transitions. Second operand has 11 states, 11 states have (on average 1.6363636363636365) internal successors, (18), 9 states have internal predecessors, (18), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,969 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:28,970 INFO L93 Difference]: Finished difference Result 58 states and 77 transitions. [2024-11-11 19:51:28,970 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-11 19:51:28,970 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 1.6363636363636365) internal successors, (18), 9 states have internal predecessors, (18), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2024-11-11 19:51:28,971 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:28,972 INFO L225 Difference]: With dead ends: 58 [2024-11-11 19:51:28,972 INFO L226 Difference]: Without dead ends: 42 [2024-11-11 19:51:28,972 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2024-11-11 19:51:28,973 INFO L435 NwaCegarLoop]: 17 mSDtfsCounter, 19 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:28,974 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 128 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:51:28,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-11 19:51:28,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 27. [2024-11-11 19:51:28,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 20 states have (on average 1.3) internal successors, (26), 22 states have internal predecessors, (26), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 19:51:28,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2024-11-11 19:51:28,991 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 10 [2024-11-11 19:51:28,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:28,991 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2024-11-11 19:51:28,992 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 1.6363636363636365) internal successors, (18), 9 states have internal predecessors, (18), 3 states have call successors, (3), 3 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:28,992 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2024-11-11 19:51:28,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2024-11-11 19:51:28,992 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:28,992 INFO L218 NwaCegarLoop]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:29,009 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-11 19:51:29,193 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:29,194 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:29,195 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:29,195 INFO L85 PathProgramCache]: Analyzing trace with hash 775784678, now seen corresponding path program 2 times [2024-11-11 19:51:29,195 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:29,195 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1727998751] [2024-11-11 19:51:29,196 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:29,196 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:29,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:29,300 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:29,300 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:29,300 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1727998751] [2024-11-11 19:51:29,301 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1727998751] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:51:29,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1022237180] [2024-11-11 19:51:29,301 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-11 19:51:29,301 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:29,301 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:29,303 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-11 19:51:29,304 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-11 19:51:29,339 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-11 19:51:29,339 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 19:51:29,339 INFO L256 TraceCheckSpWp]: Trace formula consists of 57 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-11 19:51:29,340 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:51:29,356 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:29,356 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:51:29,425 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:29,425 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1022237180] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:51:29,425 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:51:29,425 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2024-11-11 19:51:29,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1870286644] [2024-11-11 19:51:29,426 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:51:29,426 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-11 19:51:29,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:29,427 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-11 19:51:29,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2024-11-11 19:51:29,427 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand has 13 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 13 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:29,564 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:29,564 INFO L93 Difference]: Finished difference Result 52 states and 70 transitions. [2024-11-11 19:51:29,567 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-11 19:51:29,567 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 13 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 13 [2024-11-11 19:51:29,567 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:29,568 INFO L225 Difference]: With dead ends: 52 [2024-11-11 19:51:29,568 INFO L226 Difference]: Without dead ends: 28 [2024-11-11 19:51:29,568 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=110, Invalid=162, Unknown=0, NotChecked=0, Total=272 [2024-11-11 19:51:29,569 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:29,569 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 104 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:51:29,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-11 19:51:29,575 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-11 19:51:29,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-11 19:51:29,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 32 transitions. [2024-11-11 19:51:29,578 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 32 transitions. Word has length 13 [2024-11-11 19:51:29,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:29,578 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 32 transitions. [2024-11-11 19:51:29,579 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.5384615384615385) internal successors, (20), 13 states have internal predecessors, (20), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:29,579 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 32 transitions. [2024-11-11 19:51:29,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-11 19:51:29,580 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:29,580 INFO L218 NwaCegarLoop]: trace histogram [10, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:29,593 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-11 19:51:29,781 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:29,782 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:29,783 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:29,783 INFO L85 PathProgramCache]: Analyzing trace with hash 2064634630, now seen corresponding path program 3 times [2024-11-11 19:51:29,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:29,786 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1681591115] [2024-11-11 19:51:29,786 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:29,786 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:29,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:30,006 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:30,008 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:30,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1681591115] [2024-11-11 19:51:30,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1681591115] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:51:30,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [363835542] [2024-11-11 19:51:30,008 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-11 19:51:30,008 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:30,009 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:30,012 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-11 19:51:30,013 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-11 19:51:30,073 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-11 19:51:30,073 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 19:51:30,075 INFO L256 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-11 19:51:30,076 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:51:30,256 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-11 19:51:30,256 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-11 19:51:30,257 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [363835542] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 19:51:30,257 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-11 19:51:30,257 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [13] total 17 [2024-11-11 19:51:30,257 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [207098154] [2024-11-11 19:51:30,257 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 19:51:30,257 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-11 19:51:30,258 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:30,258 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-11 19:51:30,258 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=221, Unknown=0, NotChecked=0, Total=272 [2024-11-11 19:51:30,258 INFO L87 Difference]: Start difference. First operand 28 states and 32 transitions. Second operand has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:30,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:30,323 INFO L93 Difference]: Finished difference Result 35 states and 38 transitions. [2024-11-11 19:51:30,323 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-11 19:51:30,324 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 19 [2024-11-11 19:51:30,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:30,324 INFO L225 Difference]: With dead ends: 35 [2024-11-11 19:51:30,324 INFO L226 Difference]: Without dead ends: 33 [2024-11-11 19:51:30,325 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=251, Unknown=0, NotChecked=0, Total=306 [2024-11-11 19:51:30,325 INFO L435 NwaCegarLoop]: 18 mSDtfsCounter, 8 mSDsluCounter, 51 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:30,325 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 69 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 19:51:30,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-11 19:51:30,330 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2024-11-11 19:51:30,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 27 states have internal predecessors, (30), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-11 19:51:30,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 35 transitions. [2024-11-11 19:51:30,331 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 35 transitions. Word has length 19 [2024-11-11 19:51:30,331 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:30,331 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 35 transitions. [2024-11-11 19:51:30,331 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.0) internal successors, (10), 5 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-11 19:51:30,332 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 35 transitions. [2024-11-11 19:51:30,332 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2024-11-11 19:51:30,332 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:30,332 INFO L218 NwaCegarLoop]: trace histogram [10, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:30,348 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-11 19:51:30,532 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:30,533 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:30,534 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:30,534 INFO L85 PathProgramCache]: Analyzing trace with hash 1529129531, now seen corresponding path program 1 times [2024-11-11 19:51:30,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:30,534 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [249209676] [2024-11-11 19:51:30,534 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:30,534 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:30,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:30,743 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2024-11-11 19:51:30,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:30,748 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 3 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 19:51:30,748 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:30,748 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [249209676] [2024-11-11 19:51:30,748 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [249209676] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:51:30,748 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [415823274] [2024-11-11 19:51:30,748 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:30,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:30,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:30,750 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-11 19:51:30,753 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-11 19:51:30,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:30,789 INFO L256 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-11 19:51:30,790 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:51:30,859 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-11 19:51:30,862 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:51:30,994 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 20 proven. 2 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-11 19:51:30,994 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [415823274] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:51:30,994 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:51:30,994 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 6, 6] total 21 [2024-11-11 19:51:30,994 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1901299273] [2024-11-11 19:51:30,994 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:51:30,995 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-11 19:51:30,995 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:30,995 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-11 19:51:30,996 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=347, Unknown=0, NotChecked=0, Total=420 [2024-11-11 19:51:30,996 INFO L87 Difference]: Start difference. First operand 32 states and 35 transitions. Second operand has 21 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 21 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 19:51:31,747 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:31,747 INFO L93 Difference]: Finished difference Result 107 states and 126 transitions. [2024-11-11 19:51:31,747 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2024-11-11 19:51:31,747 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 21 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 26 [2024-11-11 19:51:31,748 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:31,748 INFO L225 Difference]: With dead ends: 107 [2024-11-11 19:51:31,748 INFO L226 Difference]: Without dead ends: 78 [2024-11-11 19:51:31,750 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 47 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1107 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=618, Invalid=3542, Unknown=0, NotChecked=0, Total=4160 [2024-11-11 19:51:31,750 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 60 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 343 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 351 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 343 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:31,751 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 115 Invalid, 351 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 343 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-11 19:51:31,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 78 states. [2024-11-11 19:51:31,763 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 78 to 78. [2024-11-11 19:51:31,763 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 69 states have (on average 1.1014492753623188) internal successors, (76), 70 states have internal predecessors, (76), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-11 19:51:31,764 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 87 transitions. [2024-11-11 19:51:31,765 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 87 transitions. Word has length 26 [2024-11-11 19:51:31,765 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:31,765 INFO L471 AbstractCegarLoop]: Abstraction has 78 states and 87 transitions. [2024-11-11 19:51:31,765 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 21 states have internal predecessors, (39), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 19:51:31,765 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 87 transitions. [2024-11-11 19:51:31,767 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-11 19:51:31,767 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:31,767 INFO L218 NwaCegarLoop]: trace histogram [44, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:31,783 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-11 19:51:31,967 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:31,967 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:31,968 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:31,968 INFO L85 PathProgramCache]: Analyzing trace with hash 1271803231, now seen corresponding path program 2 times [2024-11-11 19:51:31,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:31,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [69600804] [2024-11-11 19:51:31,969 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:31,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:31,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:32,278 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-11 19:51:32,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:32,280 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-11 19:51:32,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:32,281 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-11-11 19:51:32,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:32,283 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 73 [2024-11-11 19:51:32,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:32,284 INFO L134 CoverageAnalysis]: Checked inductivity of 1182 backedges. 444 proven. 66 refuted. 0 times theorem prover too weak. 672 trivial. 0 not checked. [2024-11-11 19:51:32,285 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:32,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [69600804] [2024-11-11 19:51:32,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [69600804] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:51:32,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1419023448] [2024-11-11 19:51:32,285 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-11 19:51:32,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:32,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:32,287 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-11 19:51:32,288 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-11 19:51:32,350 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-11 19:51:32,350 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 19:51:32,354 INFO L256 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-11 19:51:32,356 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:51:32,562 INFO L134 CoverageAnalysis]: Checked inductivity of 1182 backedges. 8 proven. 931 refuted. 0 times theorem prover too weak. 243 trivial. 0 not checked. [2024-11-11 19:51:32,562 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:51:32,928 INFO L134 CoverageAnalysis]: Checked inductivity of 1182 backedges. 43 proven. 896 refuted. 0 times theorem prover too weak. 243 trivial. 0 not checked. [2024-11-11 19:51:32,928 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1419023448] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:51:32,929 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:51:32,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12, 12] total 34 [2024-11-11 19:51:32,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1040955462] [2024-11-11 19:51:32,930 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:51:32,930 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2024-11-11 19:51:32,930 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:32,931 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-11 19:51:32,931 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=196, Invalid=926, Unknown=0, NotChecked=0, Total=1122 [2024-11-11 19:51:32,931 INFO L87 Difference]: Start difference. First operand 78 states and 87 transitions. Second operand has 34 states, 34 states have (on average 2.1470588235294117) internal successors, (73), 34 states have internal predecessors, (73), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-11 19:51:36,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:36,655 INFO L93 Difference]: Finished difference Result 253 states and 299 transitions. [2024-11-11 19:51:36,655 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 136 states. [2024-11-11 19:51:36,655 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 34 states have (on average 2.1470588235294117) internal successors, (73), 34 states have internal predecessors, (73), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 84 [2024-11-11 19:51:36,655 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:36,656 INFO L225 Difference]: With dead ends: 253 [2024-11-11 19:51:36,657 INFO L226 Difference]: Without dead ends: 178 [2024-11-11 19:51:36,663 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 312 GetRequests, 157 SyntacticMatches, 0 SemanticMatches, 155 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8825 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=3165, Invalid=21327, Unknown=0, NotChecked=0, Total=24492 [2024-11-11 19:51:36,663 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 92 mSDsluCounter, 386 mSDsCounter, 0 mSdLazyCounter, 1352 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 415 SdHoareTripleChecker+Invalid, 1367 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 1352 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:36,664 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 415 Invalid, 1367 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 1352 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-11 19:51:36,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2024-11-11 19:51:36,686 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 178. [2024-11-11 19:51:36,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 163 states have (on average 1.0797546012269938) internal successors, (176), 164 states have internal predecessors, (176), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-11 19:51:36,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 199 transitions. [2024-11-11 19:51:36,691 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 199 transitions. Word has length 84 [2024-11-11 19:51:36,691 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:36,691 INFO L471 AbstractCegarLoop]: Abstraction has 178 states and 199 transitions. [2024-11-11 19:51:36,691 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 34 states have (on average 2.1470588235294117) internal successors, (73), 34 states have internal predecessors, (73), 9 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-11 19:51:36,692 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 199 transitions. [2024-11-11 19:51:36,697 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 209 [2024-11-11 19:51:36,697 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:36,698 INFO L218 NwaCegarLoop]: trace histogram [120, 11, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:36,710 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-11 19:51:36,900 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:36,901 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:36,902 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:36,902 INFO L85 PathProgramCache]: Analyzing trace with hash 1147001079, now seen corresponding path program 3 times [2024-11-11 19:51:36,902 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:36,902 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [540567372] [2024-11-11 19:51:36,902 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:36,903 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:36,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,514 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2024-11-11 19:51:37,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,517 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-11-11 19:51:37,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,519 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2024-11-11 19:51:37,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,521 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 77 [2024-11-11 19:51:37,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,523 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-11 19:51:37,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,524 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 117 [2024-11-11 19:51:37,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,527 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 137 [2024-11-11 19:51:37,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,528 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 157 [2024-11-11 19:51:37,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,531 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 177 [2024-11-11 19:51:37,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,533 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 197 [2024-11-11 19:51:37,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:37,536 INFO L134 CoverageAnalysis]: Checked inductivity of 8730 backedges. 1551 proven. 78 refuted. 0 times theorem prover too weak. 7101 trivial. 0 not checked. [2024-11-11 19:51:37,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:37,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [540567372] [2024-11-11 19:51:37,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [540567372] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:51:37,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [955320829] [2024-11-11 19:51:37,537 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-11 19:51:37,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:37,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:37,538 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-11 19:51:37,540 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-11 19:51:37,622 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 15 check-sat command(s) [2024-11-11 19:51:37,622 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 19:51:37,626 INFO L256 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-11 19:51:37,635 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:51:37,666 INFO L134 CoverageAnalysis]: Checked inductivity of 8730 backedges. 1531 proven. 78 refuted. 0 times theorem prover too weak. 7121 trivial. 0 not checked. [2024-11-11 19:51:37,667 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:51:37,968 INFO L134 CoverageAnalysis]: Checked inductivity of 8730 backedges. 1551 proven. 78 refuted. 0 times theorem prover too weak. 7101 trivial. 0 not checked. [2024-11-11 19:51:37,968 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [955320829] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:51:37,968 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:51:37,968 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15, 15] total 29 [2024-11-11 19:51:37,968 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [140609666] [2024-11-11 19:51:37,968 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:51:37,969 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-11-11 19:51:37,969 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:37,970 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-11 19:51:37,970 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=250, Invalid=562, Unknown=0, NotChecked=0, Total=812 [2024-11-11 19:51:37,970 INFO L87 Difference]: Start difference. First operand 178 states and 199 transitions. Second operand has 29 states, 29 states have (on average 1.5862068965517242) internal successors, (46), 29 states have internal predecessors, (46), 1 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-11 19:51:42,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 19:51:42,884 INFO L93 Difference]: Finished difference Result 493 states and 675 transitions. [2024-11-11 19:51:42,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-11-11 19:51:42,885 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 29 states have (on average 1.5862068965517242) internal successors, (46), 29 states have internal predecessors, (46), 1 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 208 [2024-11-11 19:51:42,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 19:51:42,886 INFO L225 Difference]: With dead ends: 493 [2024-11-11 19:51:42,886 INFO L226 Difference]: Without dead ends: 318 [2024-11-11 19:51:42,887 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 462 GetRequests, 423 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=598, Invalid=1042, Unknown=0, NotChecked=0, Total=1640 [2024-11-11 19:51:42,888 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 202 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 257 SdHoareTripleChecker+Invalid, 203 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 202 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 19:51:42,888 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 257 Invalid, 203 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 202 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 19:51:42,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 318 states. [2024-11-11 19:51:42,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 318 to 318. [2024-11-11 19:51:42,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 318 states, 303 states have (on average 1.0429042904290429) internal successors, (316), 304 states have internal predecessors, (316), 12 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-11 19:51:42,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 318 states to 318 states and 339 transitions. [2024-11-11 19:51:42,923 INFO L78 Accepts]: Start accepts. Automaton has 318 states and 339 transitions. Word has length 208 [2024-11-11 19:51:42,924 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 19:51:42,924 INFO L471 AbstractCegarLoop]: Abstraction has 318 states and 339 transitions. [2024-11-11 19:51:42,924 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 29 states have (on average 1.5862068965517242) internal successors, (46), 29 states have internal predecessors, (46), 1 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-11 19:51:42,924 INFO L276 IsEmpty]: Start isEmpty. Operand 318 states and 339 transitions. [2024-11-11 19:51:42,931 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 349 [2024-11-11 19:51:42,931 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 19:51:42,932 INFO L218 NwaCegarLoop]: trace histogram [260, 11, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 19:51:42,957 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-11 19:51:43,132 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:43,132 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 19:51:43,133 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 19:51:43,133 INFO L85 PathProgramCache]: Analyzing trace with hash 2942903, now seen corresponding path program 4 times [2024-11-11 19:51:43,133 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 19:51:43,133 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1362364361] [2024-11-11 19:51:43,133 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 19:51:43,133 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 19:51:43,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,761 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 31 [2024-11-11 19:51:44,762 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,764 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-11 19:51:44,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,765 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-11-11 19:51:44,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,766 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 133 [2024-11-11 19:51:44,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,767 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 167 [2024-11-11 19:51:44,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,768 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 201 [2024-11-11 19:51:44,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,771 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 235 [2024-11-11 19:51:44,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,773 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 269 [2024-11-11 19:51:44,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,774 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 303 [2024-11-11 19:51:44,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,776 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 337 [2024-11-11 19:51:44,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 19:51:44,786 INFO L134 CoverageAnalysis]: Checked inductivity of 36660 backedges. 6591 proven. 351 refuted. 0 times theorem prover too weak. 29718 trivial. 0 not checked. [2024-11-11 19:51:44,786 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 19:51:44,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1362364361] [2024-11-11 19:51:44,787 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1362364361] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 19:51:44,787 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2070803235] [2024-11-11 19:51:44,787 INFO L95 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-11 19:51:44,787 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 19:51:44,787 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 19:51:44,790 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-11 19:51:44,795 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-11 19:51:44,998 INFO L229 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-11 19:51:44,999 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 19:51:45,004 INFO L256 TraceCheckSpWp]: Trace formula consists of 972 conjuncts, 46 conjuncts are in the unsatisfiable core [2024-11-11 19:51:45,010 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 19:51:45,812 INFO L134 CoverageAnalysis]: Checked inductivity of 36660 backedges. 20 proven. 33181 refuted. 0 times theorem prover too weak. 3459 trivial. 0 not checked. [2024-11-11 19:51:45,813 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 19:51:47,265 INFO L134 CoverageAnalysis]: Checked inductivity of 36660 backedges. 196 proven. 33005 refuted. 0 times theorem prover too weak. 3459 trivial. 0 not checked. [2024-11-11 19:51:47,266 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2070803235] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 19:51:47,266 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 19:51:47,266 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 24, 24] total 73 [2024-11-11 19:51:47,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495715617] [2024-11-11 19:51:47,266 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 19:51:47,267 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 73 states [2024-11-11 19:51:47,267 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 19:51:47,268 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2024-11-11 19:51:47,269 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=697, Invalid=4559, Unknown=0, NotChecked=0, Total=5256 [2024-11-11 19:51:47,269 INFO L87 Difference]: Start difference. First operand 318 states and 339 transitions. Second operand has 73 states, 73 states have (on average 2.0273972602739727) internal successors, (148), 73 states have internal predecessors, (148), 21 states have call successors, (22), 2 states have call predecessors, (22), 1 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21)