./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3289d67d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.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 a077c1334c11d8329da2d0c58ca917b2036581fa7e949d1d304e3346ec54a811 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-16 07:15:57,390 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-16 07:15:57,479 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-16 07:15:57,484 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-16 07:15:57,485 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-16 07:15:57,518 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-16 07:15:57,518 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-16 07:15:57,519 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-16 07:15:57,520 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-16 07:15:57,521 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-16 07:15:57,521 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-16 07:15:57,522 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-16 07:15:57,522 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-16 07:15:57,524 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-16 07:15:57,524 INFO L153 SettingsManager]: * Use SBE=true [2024-11-16 07:15:57,524 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-16 07:15:57,525 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-16 07:15:57,525 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-16 07:15:57,526 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-16 07:15:57,526 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-16 07:15:57,528 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-16 07:15:57,529 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-16 07:15:57,529 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-16 07:15:57,529 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-16 07:15:57,530 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-16 07:15:57,530 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-16 07:15:57,530 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-16 07:15:57,530 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-16 07:15:57,531 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-16 07:15:57,531 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-16 07:15:57,531 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-16 07:15:57,531 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-16 07:15:57,531 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:15:57,532 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-16 07:15:57,532 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-16 07:15:57,532 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-16 07:15:57,532 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-16 07:15:57,532 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-16 07:15:57,533 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-16 07:15:57,533 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-16 07:15:57,533 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-16 07:15:57,535 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-16 07:15:57,535 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 -> a077c1334c11d8329da2d0c58ca917b2036581fa7e949d1d304e3346ec54a811 [2024-11-16 07:15:57,774 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-16 07:15:57,796 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-16 07:15:57,801 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-16 07:15:57,802 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-16 07:15:57,802 INFO L274 PluginConnector]: CDTParser initialized [2024-11-16 07:15:57,803 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c [2024-11-16 07:15:59,209 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-16 07:15:59,390 INFO L384 CDTParser]: Found 1 translation units. [2024-11-16 07:15:59,391 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c [2024-11-16 07:15:59,397 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3cec90e7f/ce64ff4d341b4c2287b2d02fe7cfa64e/FLAG9d6ac942f [2024-11-16 07:15:59,410 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3cec90e7f/ce64ff4d341b4c2287b2d02fe7cfa64e [2024-11-16 07:15:59,413 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-16 07:15:59,414 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-16 07:15:59,415 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-16 07:15:59,416 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-16 07:15:59,421 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-16 07:15:59,422 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,423 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4a577260 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59, skipping insertion in model container [2024-11-16 07:15:59,423 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,443 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-16 07:15:59,652 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c[526,539] [2024-11-16 07:15:59,700 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:15:59,720 INFO L200 MainTranslator]: Completed pre-run [2024-11-16 07:15:59,745 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound5.c[526,539] [2024-11-16 07:15:59,769 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:15:59,786 INFO L204 MainTranslator]: Completed translation [2024-11-16 07:15:59,787 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59 WrapperNode [2024-11-16 07:15:59,787 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-16 07:15:59,788 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-16 07:15:59,788 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-16 07:15:59,788 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-16 07:15:59,795 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,800 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,817 INFO L138 Inliner]: procedures = 14, calls = 23, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 62 [2024-11-16 07:15:59,817 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-16 07:15:59,818 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-16 07:15:59,818 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-16 07:15:59,818 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-16 07:15:59,826 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,827 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,828 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,839 INFO L175 MemorySlicer]: Split 10 memory accesses to 2 slices as follows [2, 8]. 80 percent of accesses are in the largest equivalence class. The 10 initializations are split as follows [2, 8]. The 0 writes are split as follows [0, 0]. [2024-11-16 07:15:59,839 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,840 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,843 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,844 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,849 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,850 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,851 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-16 07:15:59,852 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-16 07:15:59,855 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-16 07:15:59,856 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-16 07:15:59,857 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (1/1) ... [2024-11-16 07:15:59,862 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:15:59,873 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:15:59,894 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-16 07:15:59,898 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-16 07:15:59,949 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-16 07:15:59,951 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-16 07:15:59,951 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-16 07:15:59,951 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-16 07:15:59,952 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-16 07:15:59,952 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-16 07:15:59,952 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-16 07:16:00,019 INFO L256 CfgBuilder]: Building ICFG [2024-11-16 07:16:00,023 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-16 07:16:00,199 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-16 07:16:00,199 INFO L307 CfgBuilder]: Performing block encoding [2024-11-16 07:16:00,216 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-16 07:16:00,216 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-16 07:16:00,217 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:16:00 BoogieIcfgContainer [2024-11-16 07:16:00,217 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-16 07:16:00,219 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-16 07:16:00,219 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-16 07:16:00,226 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-16 07:16:00,226 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.11 07:15:59" (1/3) ... [2024-11-16 07:16:00,227 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@560d420b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:16:00, skipping insertion in model container [2024-11-16 07:16:00,227 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:15:59" (2/3) ... [2024-11-16 07:16:00,228 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@560d420b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:16:00, skipping insertion in model container [2024-11-16 07:16:00,228 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:16:00" (3/3) ... [2024-11-16 07:16:00,229 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_valuebound5.c [2024-11-16 07:16:00,246 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-16 07:16:00,248 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-16 07:16:00,314 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-16 07:16:00,323 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;@21174573, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-16 07:16:00,323 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-16 07:16:00,328 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-16 07:16:00,334 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-16 07:16:00,335 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:00,336 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:00,337 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:00,342 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:00,343 INFO L85 PathProgramCache]: Analyzing trace with hash -292126860, now seen corresponding path program 1 times [2024-11-16 07:16:00,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:00,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2103755165] [2024-11-16 07:16:00,355 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:00,355 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:00,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:00,522 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-16 07:16:00,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:00,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2103755165] [2024-11-16 07:16:00,524 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2103755165] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:00,524 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:00,524 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-16 07:16:00,526 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1458070353] [2024-11-16 07:16:00,527 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:00,531 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-16 07:16:00,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:00,553 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-16 07:16:00,554 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 07:16:00,556 INFO L87 Difference]: Start difference. First operand has 29 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 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-16 07:16:00,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:00,582 INFO L93 Difference]: Finished difference Result 55 states and 89 transitions. [2024-11-16 07:16:00,583 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-16 07:16:00,584 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 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 11 [2024-11-16 07:16:00,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:00,591 INFO L225 Difference]: With dead ends: 55 [2024-11-16 07:16:00,591 INFO L226 Difference]: Without dead ends: 25 [2024-11-16 07:16:00,594 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 07:16:00,599 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 37 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:00,602 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:16:00,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-16 07:16:00,636 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-16 07:16:00,638 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-16 07:16:00,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 33 transitions. [2024-11-16 07:16:00,644 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 33 transitions. Word has length 11 [2024-11-16 07:16:00,644 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:00,644 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 33 transitions. [2024-11-16 07:16:00,645 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 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-16 07:16:00,645 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 33 transitions. [2024-11-16 07:16:00,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-16 07:16:00,647 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:00,647 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:00,647 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-16 07:16:00,647 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:00,648 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:00,648 INFO L85 PathProgramCache]: Analyzing trace with hash -2099581323, now seen corresponding path program 1 times [2024-11-16 07:16:00,648 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:00,649 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [153100560] [2024-11-16 07:16:00,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:00,649 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:00,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:00,837 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-16 07:16:00,837 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:00,838 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [153100560] [2024-11-16 07:16:00,838 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [153100560] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:00,838 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:00,838 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:00,839 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [107367772] [2024-11-16 07:16:00,839 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:00,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:00,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:00,844 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:00,845 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:00,845 INFO L87 Difference]: Start difference. First operand 25 states and 33 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 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-16 07:16:00,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:00,912 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2024-11-16 07:16:00,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:00,913 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 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 11 [2024-11-16 07:16:00,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:00,914 INFO L225 Difference]: With dead ends: 40 [2024-11-16 07:16:00,915 INFO L226 Difference]: Without dead ends: 37 [2024-11-16 07:16:00,915 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:16:00,916 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 10 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:00,917 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 101 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:16:00,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-16 07:16:00,925 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 29. [2024-11-16 07:16:00,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-16 07:16:00,930 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 36 transitions. [2024-11-16 07:16:00,931 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 36 transitions. Word has length 11 [2024-11-16 07:16:00,931 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:00,931 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 36 transitions. [2024-11-16 07:16:00,931 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 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-16 07:16:00,932 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 36 transitions. [2024-11-16 07:16:00,932 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-16 07:16:00,932 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:00,932 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:00,933 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-16 07:16:00,933 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:00,934 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:00,934 INFO L85 PathProgramCache]: Analyzing trace with hash 2100820203, now seen corresponding path program 1 times [2024-11-16 07:16:00,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:00,934 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [112451039] [2024-11-16 07:16:00,934 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:00,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:00,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:01,060 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:01,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:01,067 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-16 07:16:01,068 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:01,068 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [112451039] [2024-11-16 07:16:01,068 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [112451039] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:01,069 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:01,069 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:01,069 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [768944716] [2024-11-16 07:16:01,069 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:01,070 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:01,070 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:01,071 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:01,071 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:01,071 INFO L87 Difference]: Start difference. First operand 29 states and 36 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-16 07:16:01,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:01,129 INFO L93 Difference]: Finished difference Result 44 states and 55 transitions. [2024-11-16 07:16:01,130 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:01,130 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 16 [2024-11-16 07:16:01,130 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:01,131 INFO L225 Difference]: With dead ends: 44 [2024-11-16 07:16:01,131 INFO L226 Difference]: Without dead ends: 41 [2024-11-16 07:16:01,132 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:16:01,133 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 10 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:01,133 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 98 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:16:01,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-16 07:16:01,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2024-11-16 07:16:01,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-16 07:16:01,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 39 transitions. [2024-11-16 07:16:01,157 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 39 transitions. Word has length 16 [2024-11-16 07:16:01,157 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:01,157 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 39 transitions. [2024-11-16 07:16:01,158 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-16 07:16:01,158 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 39 transitions. [2024-11-16 07:16:01,158 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-16 07:16:01,159 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:01,159 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:01,159 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-16 07:16:01,159 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:01,160 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:01,160 INFO L85 PathProgramCache]: Analyzing trace with hash 1262954485, now seen corresponding path program 1 times [2024-11-16 07:16:01,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:01,161 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1796072164] [2024-11-16 07:16:01,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:01,161 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:01,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:01,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [129262523] [2024-11-16 07:16:01,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:01,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:01,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:01,212 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-16 07:16:01,213 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-16 07:16:01,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:01,280 INFO L255 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:16:01,285 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:01,416 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-16 07:16:01,417 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:16:01,417 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:01,417 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1796072164] [2024-11-16 07:16:01,418 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:01,418 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [129262523] [2024-11-16 07:16:01,418 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [129262523] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:01,419 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:01,419 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:01,419 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1660055193] [2024-11-16 07:16:01,419 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:01,420 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:01,420 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:01,420 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:01,420 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:01,421 INFO L87 Difference]: Start difference. First operand 33 states and 39 transitions. Second operand has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-16 07:16:01,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:01,495 INFO L93 Difference]: Finished difference Result 63 states and 80 transitions. [2024-11-16 07:16:01,495 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:01,495 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2024-11-16 07:16:01,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:01,497 INFO L225 Difference]: With dead ends: 63 [2024-11-16 07:16:01,498 INFO L226 Difference]: Without dead ends: 48 [2024-11-16 07:16:01,499 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:16:01,501 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 6 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:01,502 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [9 Valid, 101 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:16:01,503 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-16 07:16:01,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2024-11-16 07:16:01,515 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 31 states have (on average 1.1612903225806452) internal successors, (36), 32 states have internal predecessors, (36), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-16 07:16:01,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 59 transitions. [2024-11-16 07:16:01,518 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 59 transitions. Word has length 21 [2024-11-16 07:16:01,518 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:01,519 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 59 transitions. [2024-11-16 07:16:01,519 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.6) internal successors, (13), 4 states have internal predecessors, (13), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-16 07:16:01,519 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 59 transitions. [2024-11-16 07:16:01,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-16 07:16:01,521 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:01,521 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:01,539 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-16 07:16:01,722 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-16 07:16:01,722 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:01,723 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:01,723 INFO L85 PathProgramCache]: Analyzing trace with hash -23433476, now seen corresponding path program 1 times [2024-11-16 07:16:01,723 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:01,723 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [239736672] [2024-11-16 07:16:01,723 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:01,724 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:01,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:01,751 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2045967113] [2024-11-16 07:16:01,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:01,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:01,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:01,756 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-16 07:16:01,761 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-16 07:16:01,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:01,831 INFO L255 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:16:01,833 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:01,941 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-16 07:16:01,941 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:16:01,941 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:01,942 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [239736672] [2024-11-16 07:16:01,942 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:01,942 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2045967113] [2024-11-16 07:16:01,942 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2045967113] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:01,942 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:01,943 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:01,943 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [77348323] [2024-11-16 07:16:01,943 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:01,943 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:01,944 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:01,944 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:01,944 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:01,945 INFO L87 Difference]: Start difference. First operand 48 states and 59 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-16 07:16:02,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:02,019 INFO L93 Difference]: Finished difference Result 63 states and 78 transitions. [2024-11-16 07:16:02,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:02,019 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 29 [2024-11-16 07:16:02,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:02,021 INFO L225 Difference]: With dead ends: 63 [2024-11-16 07:16:02,021 INFO L226 Difference]: Without dead ends: 60 [2024-11-16 07:16:02,021 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:16:02,022 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 7 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:02,022 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 82 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:16:02,025 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-16 07:16:02,035 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-11-16 07:16:02,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 38 states have (on average 1.1842105263157894) internal successors, (45), 40 states have internal predecessors, (45), 15 states have call successors, (15), 5 states have call predecessors, (15), 5 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-16 07:16:02,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 74 transitions. [2024-11-16 07:16:02,037 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 74 transitions. Word has length 29 [2024-11-16 07:16:02,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:02,038 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 74 transitions. [2024-11-16 07:16:02,038 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-16 07:16:02,039 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 74 transitions. [2024-11-16 07:16:02,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-16 07:16:02,042 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:02,042 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:02,057 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-16 07:16:02,246 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-16 07:16:02,247 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:02,247 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:02,247 INFO L85 PathProgramCache]: Analyzing trace with hash 253378592, now seen corresponding path program 1 times [2024-11-16 07:16:02,247 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:02,248 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [9103715] [2024-11-16 07:16:02,248 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:02,248 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:02,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:02,276 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1815807006] [2024-11-16 07:16:02,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:02,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:02,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:02,278 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-16 07:16:02,279 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-16 07:16:02,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:02,325 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-16 07:16:02,328 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:02,472 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-16 07:16:02,473 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:02,569 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-16 07:16:02,569 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:02,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [9103715] [2024-11-16 07:16:02,569 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:02,569 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1815807006] [2024-11-16 07:16:02,569 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1815807006] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:02,569 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:16:02,570 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-16 07:16:02,570 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [942622640] [2024-11-16 07:16:02,570 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:02,570 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:02,570 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:02,571 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:02,571 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-16 07:16:02,571 INFO L87 Difference]: Start difference. First operand 59 states and 74 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-16 07:16:03,959 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.31s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:16:03,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:03,971 INFO L93 Difference]: Finished difference Result 71 states and 88 transitions. [2024-11-16 07:16:03,972 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:03,972 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 39 [2024-11-16 07:16:03,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:03,974 INFO L225 Difference]: With dead ends: 71 [2024-11-16 07:16:03,974 INFO L226 Difference]: Without dead ends: 68 [2024-11-16 07:16:03,974 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 69 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-16 07:16:03,975 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 6 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:03,976 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 93 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-11-16 07:16:03,977 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2024-11-16 07:16:03,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 67. [2024-11-16 07:16:03,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 43 states have (on average 1.1627906976744187) internal successors, (50), 46 states have internal predecessors, (50), 17 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-16 07:16:03,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 83 transitions. [2024-11-16 07:16:03,989 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 83 transitions. Word has length 39 [2024-11-16 07:16:03,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:03,990 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 83 transitions. [2024-11-16 07:16:03,990 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-16 07:16:03,990 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 83 transitions. [2024-11-16 07:16:03,991 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-16 07:16:03,991 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:03,992 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:04,009 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-16 07:16:04,192 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-16 07:16:04,193 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:04,193 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:04,193 INFO L85 PathProgramCache]: Analyzing trace with hash -1361005644, now seen corresponding path program 1 times [2024-11-16 07:16:04,193 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:04,193 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1070760388] [2024-11-16 07:16:04,193 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:04,193 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:04,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,299 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:04,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,308 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:16:04,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,316 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:16:04,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,324 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:16:04,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,334 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:16:04,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,340 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-16 07:16:04,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,344 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-11-16 07:16:04,344 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:04,344 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1070760388] [2024-11-16 07:16:04,344 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1070760388] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:04,345 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:04,345 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:04,345 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [925358084] [2024-11-16 07:16:04,345 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:04,345 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:04,345 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:04,346 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:04,346 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:04,346 INFO L87 Difference]: Start difference. First operand 67 states and 83 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-16 07:16:04,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:04,399 INFO L93 Difference]: Finished difference Result 76 states and 92 transitions. [2024-11-16 07:16:04,399 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:04,399 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) Word has length 45 [2024-11-16 07:16:04,400 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:04,401 INFO L225 Difference]: With dead ends: 76 [2024-11-16 07:16:04,401 INFO L226 Difference]: Without dead ends: 62 [2024-11-16 07:16:04,402 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-16 07:16:04,404 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 3 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:04,415 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 111 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-16 07:16:04,417 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-11-16 07:16:04,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2024-11-16 07:16:04,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 40 states have (on average 1.15) internal successors, (46), 43 states have internal predecessors, (46), 15 states have call successors, (15), 6 states have call predecessors, (15), 6 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-16 07:16:04,447 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 75 transitions. [2024-11-16 07:16:04,447 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 75 transitions. Word has length 45 [2024-11-16 07:16:04,447 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:04,448 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 75 transitions. [2024-11-16 07:16:04,448 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 1 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 1 states have call predecessors, (6), 1 states have call successors, (6) [2024-11-16 07:16:04,448 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 75 transitions. [2024-11-16 07:16:04,449 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-16 07:16:04,449 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:04,451 INFO L215 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:04,451 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-16 07:16:04,453 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:04,454 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:04,454 INFO L85 PathProgramCache]: Analyzing trace with hash -646613615, now seen corresponding path program 1 times [2024-11-16 07:16:04,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:04,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [784736980] [2024-11-16 07:16:04,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:04,455 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:04,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:04,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [596329667] [2024-11-16 07:16:04,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:04,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:04,532 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:04,536 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-16 07:16:04,538 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-16 07:16:04,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,607 INFO L255 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-16 07:16:04,610 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:04,964 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-16 07:16:04,964 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:06,810 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 15 proven. 31 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-16 07:16:06,810 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:06,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [784736980] [2024-11-16 07:16:06,810 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:06,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [596329667] [2024-11-16 07:16:06,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [596329667] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:06,811 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:06,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-16 07:16:06,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1083458883] [2024-11-16 07:16:06,811 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:06,811 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-16 07:16:06,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:06,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-16 07:16:06,814 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-11-16 07:16:06,815 INFO L87 Difference]: Start difference. First operand 62 states and 75 transitions. Second operand has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-16 07:16:07,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:07,484 INFO L93 Difference]: Finished difference Result 148 states and 193 transitions. [2024-11-16 07:16:07,484 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-16 07:16:07,484 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 61 [2024-11-16 07:16:07,485 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:07,486 INFO L225 Difference]: With dead ends: 148 [2024-11-16 07:16:07,487 INFO L226 Difference]: Without dead ends: 122 [2024-11-16 07:16:07,488 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 107 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2024-11-16 07:16:07,489 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 35 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 309 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 357 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 309 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:07,490 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 269 Invalid, 357 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 309 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-16 07:16:07,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-16 07:16:07,513 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 120. [2024-11-16 07:16:07,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 78 states have (on average 1.1794871794871795) internal successors, (92), 83 states have internal predecessors, (92), 31 states have call successors, (31), 10 states have call predecessors, (31), 10 states have return successors, (30), 26 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-16 07:16:07,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 153 transitions. [2024-11-16 07:16:07,516 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 153 transitions. Word has length 61 [2024-11-16 07:16:07,516 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:07,516 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 153 transitions. [2024-11-16 07:16:07,516 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 14 states have internal predecessors, (43), 7 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-16 07:16:07,517 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 153 transitions. [2024-11-16 07:16:07,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-16 07:16:07,518 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:07,519 INFO L215 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:07,536 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-16 07:16:07,722 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:07,723 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:07,723 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:07,723 INFO L85 PathProgramCache]: Analyzing trace with hash -641848553, now seen corresponding path program 1 times [2024-11-16 07:16:07,724 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:07,724 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [473782588] [2024-11-16 07:16:07,724 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:07,724 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:07,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:07,756 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1976840499] [2024-11-16 07:16:07,756 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:07,756 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:07,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:07,758 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-16 07:16:07,760 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-16 07:16:07,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:07,822 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-16 07:16:07,825 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:08,175 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-16 07:16:08,175 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:08,916 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 19 proven. 39 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2024-11-16 07:16:08,916 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:08,916 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [473782588] [2024-11-16 07:16:08,916 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:08,916 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1976840499] [2024-11-16 07:16:08,917 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1976840499] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:08,917 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:08,917 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2024-11-16 07:16:08,917 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [213679610] [2024-11-16 07:16:08,917 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:08,918 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-16 07:16:08,918 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:08,918 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-16 07:16:08,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=294, Unknown=0, NotChecked=0, Total=380 [2024-11-16 07:16:08,919 INFO L87 Difference]: Start difference. First operand 120 states and 153 transitions. Second operand has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) [2024-11-16 07:16:09,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:09,459 INFO L93 Difference]: Finished difference Result 192 states and 246 transitions. [2024-11-16 07:16:09,460 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-16 07:16:09,460 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) Word has length 72 [2024-11-16 07:16:09,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:09,462 INFO L225 Difference]: With dead ends: 192 [2024-11-16 07:16:09,462 INFO L226 Difference]: Without dead ends: 140 [2024-11-16 07:16:09,463 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 124 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=120, Invalid=386, Unknown=0, NotChecked=0, Total=506 [2024-11-16 07:16:09,463 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 27 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 238 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 238 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:09,464 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 208 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 238 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-16 07:16:09,464 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-11-16 07:16:09,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 113. [2024-11-16 07:16:09,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 74 states have (on average 1.135135135135135) internal successors, (84), 78 states have internal predecessors, (84), 27 states have call successors, (27), 11 states have call predecessors, (27), 11 states have return successors, (26), 23 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-16 07:16:09,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 137 transitions. [2024-11-16 07:16:09,487 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 137 transitions. Word has length 72 [2024-11-16 07:16:09,488 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:09,488 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 137 transitions. [2024-11-16 07:16:09,488 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 18 states have (on average 2.5) internal successors, (45), 18 states have internal predecessors, (45), 11 states have call successors, (22), 3 states have call predecessors, (22), 2 states have return successors, (20), 8 states have call predecessors, (20), 9 states have call successors, (20) [2024-11-16 07:16:09,488 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 137 transitions. [2024-11-16 07:16:09,490 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-16 07:16:09,490 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:09,490 INFO L215 NwaCegarLoop]: trace histogram [12, 11, 11, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:09,508 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-16 07:16:09,694 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:09,695 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:09,695 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:09,695 INFO L85 PathProgramCache]: Analyzing trace with hash 1640886345, now seen corresponding path program 1 times [2024-11-16 07:16:09,695 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:09,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1333384476] [2024-11-16 07:16:09,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:09,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:09,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,002 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:10,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,007 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:16:10,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,011 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:16:10,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,015 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:16:10,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,019 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:16:10,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,023 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-16 07:16:10,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,027 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-16 07:16:10,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,040 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-16 07:16:10,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,047 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2024-11-16 07:16:10,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,057 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-11-16 07:16:10,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,060 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2024-11-16 07:16:10,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,063 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-16 07:16:10,063 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:10,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1333384476] [2024-11-16 07:16:10,063 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1333384476] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:10,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [876910686] [2024-11-16 07:16:10,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:10,064 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:10,064 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:10,066 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-16 07:16:10,067 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-16 07:16:10,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,120 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-16 07:16:10,123 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:10,290 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-16 07:16:10,290 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:10,726 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2024-11-16 07:16:10,726 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [876910686] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:10,726 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:16:10,727 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2024-11-16 07:16:10,727 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1935922799] [2024-11-16 07:16:10,727 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:10,727 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-16 07:16:10,728 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:10,728 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-16 07:16:10,728 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2024-11-16 07:16:10,729 INFO L87 Difference]: Start difference. First operand 113 states and 137 transitions. Second operand has 13 states, 13 states have (on average 4.153846153846154) internal successors, (54), 11 states have internal predecessors, (54), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2024-11-16 07:16:10,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:10,925 INFO L93 Difference]: Finished difference Result 133 states and 157 transitions. [2024-11-16 07:16:10,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-16 07:16:10,925 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 4.153846153846154) internal successors, (54), 11 states have internal predecessors, (54), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) Word has length 77 [2024-11-16 07:16:10,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:10,927 INFO L225 Difference]: With dead ends: 133 [2024-11-16 07:16:10,928 INFO L226 Difference]: Without dead ends: 103 [2024-11-16 07:16:10,929 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 183 GetRequests, 168 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2024-11-16 07:16:10,929 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 8 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 102 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 200 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 102 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:10,930 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 200 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 102 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:16:10,931 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-16 07:16:10,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2024-11-16 07:16:10,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 68 states have (on average 1.1029411764705883) internal successors, (75), 71 states have internal predecessors, (75), 23 states have call successors, (23), 11 states have call predecessors, (23), 11 states have return successors, (22), 20 states have call predecessors, (22), 22 states have call successors, (22) [2024-11-16 07:16:10,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 120 transitions. [2024-11-16 07:16:10,963 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 120 transitions. Word has length 77 [2024-11-16 07:16:10,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:10,964 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 120 transitions. [2024-11-16 07:16:10,965 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 4.153846153846154) internal successors, (54), 11 states have internal predecessors, (54), 7 states have call successors, (35), 3 states have call predecessors, (35), 1 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2024-11-16 07:16:10,965 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 120 transitions. [2024-11-16 07:16:10,966 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-11-16 07:16:10,966 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:10,969 INFO L215 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:10,986 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-16 07:16:11,173 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:11,174 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:11,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:11,174 INFO L85 PathProgramCache]: Analyzing trace with hash 985163622, now seen corresponding path program 2 times [2024-11-16 07:16:11,174 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:11,175 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1527492896] [2024-11-16 07:16:11,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:11,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:11,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:11,206 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2083693388] [2024-11-16 07:16:11,206 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:16:11,206 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:11,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:11,208 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-16 07:16:11,209 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-16 07:16:11,275 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:16:11,275 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:16:11,277 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-16 07:16:11,279 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:11,686 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-16 07:16:11,686 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:23,673 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 28 proven. 64 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2024-11-16 07:16:23,673 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:23,673 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1527492896] [2024-11-16 07:16:23,673 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:23,673 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2083693388] [2024-11-16 07:16:23,673 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2083693388] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:23,673 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:23,673 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2024-11-16 07:16:23,674 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1354208068] [2024-11-16 07:16:23,674 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:23,677 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-16 07:16:23,677 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:23,678 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-16 07:16:23,678 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2024-11-16 07:16:23,679 INFO L87 Difference]: Start difference. First operand 103 states and 120 transitions. Second operand has 21 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-16 07:16:37,686 WARN L286 SmtUtils]: Spent 13.73s on a formula simplification. DAG size of input: 168 DAG size of output: 83 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-16 07:16:40,971 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.80s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:16:43,607 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:43,608 INFO L93 Difference]: Finished difference Result 226 states and 289 transitions. [2024-11-16 07:16:43,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-16 07:16:43,608 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) Word has length 93 [2024-11-16 07:16:43,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:43,610 INFO L225 Difference]: With dead ends: 226 [2024-11-16 07:16:43,610 INFO L226 Difference]: Without dead ends: 189 [2024-11-16 07:16:43,611 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 165 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 15.8s TimeCoverageRelationStatistics Valid=158, Invalid=544, Unknown=0, NotChecked=0, Total=702 [2024-11-16 07:16:43,612 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 83 mSDsluCounter, 450 mSDsCounter, 0 mSdLazyCounter, 577 mSolverCounterSat, 112 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 92 SdHoareTripleChecker+Valid, 498 SdHoareTripleChecker+Invalid, 689 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 112 IncrementalHoareTripleChecker+Valid, 577 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.3s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:43,612 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 498 Invalid, 689 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [112 Valid, 577 Invalid, 0 Unknown, 0 Unchecked, 5.3s Time] [2024-11-16 07:16:43,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-11-16 07:16:43,669 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 185. [2024-11-16 07:16:43,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 185 states, 121 states have (on average 1.1487603305785123) internal successors, (139), 129 states have internal predecessors, (139), 49 states have call successors, (49), 14 states have call predecessors, (49), 14 states have return successors, (48), 41 states have call predecessors, (48), 48 states have call successors, (48) [2024-11-16 07:16:43,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 236 transitions. [2024-11-16 07:16:43,672 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 236 transitions. Word has length 93 [2024-11-16 07:16:43,673 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:43,673 INFO L471 AbstractCegarLoop]: Abstraction has 185 states and 236 transitions. [2024-11-16 07:16:43,673 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.7142857142857144) internal successors, (57), 19 states have internal predecessors, (57), 11 states have call successors, (28), 3 states have call predecessors, (28), 2 states have return successors, (26), 9 states have call predecessors, (26), 9 states have call successors, (26) [2024-11-16 07:16:43,674 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 236 transitions. [2024-11-16 07:16:43,677 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2024-11-16 07:16:43,678 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:43,678 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:43,691 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-16 07:16:43,878 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:43,879 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:43,879 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:43,879 INFO L85 PathProgramCache]: Analyzing trace with hash 515453474, now seen corresponding path program 2 times [2024-11-16 07:16:43,879 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:43,879 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [546278047] [2024-11-16 07:16:43,879 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:43,879 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:43,926 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:43,927 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1920470502] [2024-11-16 07:16:43,927 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:16:43,927 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:43,927 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:43,929 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:16:43,934 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-16 07:16:43,991 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:16:43,991 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:16:43,992 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 50 conjuncts are in the unsatisfiable core [2024-11-16 07:16:43,995 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:44,443 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 50 proven. 56 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-16 07:16:44,444 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:47,856 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 50 proven. 56 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-16 07:16:47,857 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:47,857 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [546278047] [2024-11-16 07:16:47,857 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:47,857 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1920470502] [2024-11-16 07:16:47,857 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1920470502] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:47,857 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:47,857 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 27 [2024-11-16 07:16:47,857 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1124666903] [2024-11-16 07:16:47,857 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:47,858 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-16 07:16:47,858 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:47,858 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-16 07:16:47,859 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=547, Unknown=0, NotChecked=0, Total=702 [2024-11-16 07:16:47,859 INFO L87 Difference]: Start difference. First operand 185 states and 236 transitions. Second operand has 27 states, 25 states have (on average 2.36) internal successors, (59), 25 states have internal predecessors, (59), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-16 07:16:55,931 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.34s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:16:56,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:56,434 INFO L93 Difference]: Finished difference Result 263 states and 337 transitions. [2024-11-16 07:16:56,435 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-16 07:16:56,435 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 25 states have (on average 2.36) internal successors, (59), 25 states have internal predecessors, (59), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) Word has length 104 [2024-11-16 07:16:56,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:56,437 INFO L225 Difference]: With dead ends: 263 [2024-11-16 07:16:56,437 INFO L226 Difference]: Without dead ends: 189 [2024-11-16 07:16:56,439 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 213 GetRequests, 181 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 170 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=270, Invalid=852, Unknown=0, NotChecked=0, Total=1122 [2024-11-16 07:16:56,440 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 69 mSDsluCounter, 284 mSDsCounter, 0 mSdLazyCounter, 378 mSolverCounterSat, 110 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 324 SdHoareTripleChecker+Invalid, 488 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 110 IncrementalHoareTripleChecker+Valid, 378 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.9s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:56,440 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 324 Invalid, 488 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [110 Valid, 378 Invalid, 0 Unknown, 0 Unchecked, 2.9s Time] [2024-11-16 07:16:56,441 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-11-16 07:16:56,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 163. [2024-11-16 07:16:56,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 107 states have (on average 1.1121495327102804) internal successors, (119), 114 states have internal predecessors, (119), 40 states have call successors, (40), 15 states have call predecessors, (40), 15 states have return successors, (39), 33 states have call predecessors, (39), 39 states have call successors, (39) [2024-11-16 07:16:56,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 198 transitions. [2024-11-16 07:16:56,490 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 198 transitions. Word has length 104 [2024-11-16 07:16:56,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:56,490 INFO L471 AbstractCegarLoop]: Abstraction has 163 states and 198 transitions. [2024-11-16 07:16:56,490 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 25 states have (on average 2.36) internal successors, (59), 25 states have internal predecessors, (59), 15 states have call successors, (32), 3 states have call predecessors, (32), 2 states have return successors, (30), 13 states have call predecessors, (30), 13 states have call successors, (30) [2024-11-16 07:16:56,491 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 198 transitions. [2024-11-16 07:16:56,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-16 07:16:56,492 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:56,492 INFO L215 NwaCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:56,510 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-16 07:16:56,692 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-16 07:16:56,693 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:56,693 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:56,693 INFO L85 PathProgramCache]: Analyzing trace with hash 107255838, now seen corresponding path program 2 times [2024-11-16 07:16:56,693 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:56,693 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2037725194] [2024-11-16 07:16:56,693 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:56,693 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:56,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,046 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:57,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,050 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:16:57,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,054 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:16:57,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,058 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:16:57,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,062 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:16:57,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,068 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-16 07:16:57,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,072 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-16 07:16:57,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,075 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-16 07:16:57,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,078 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-16 07:16:57,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,082 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-16 07:16:57,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,086 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-16 07:16:57,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,089 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 74 [2024-11-16 07:16:57,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,093 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 79 [2024-11-16 07:16:57,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,098 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-11-16 07:16:57,099 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,101 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-11-16 07:16:57,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,104 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-11-16 07:16:57,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:57,109 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-16 07:16:57,109 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:57,109 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2037725194] [2024-11-16 07:16:57,110 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2037725194] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:57,110 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [223054967] [2024-11-16 07:16:57,110 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:16:57,110 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:57,110 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:57,112 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:16:57,113 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-16 07:16:57,177 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:16:57,177 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:16:57,179 INFO L255 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-16 07:16:57,181 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:57,487 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-16 07:16:57,487 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:58,472 INFO L134 CoverageAnalysis]: Checked inductivity of 546 backedges. 32 proven. 34 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2024-11-16 07:16:58,472 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [223054967] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:58,472 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:16:58,472 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 8] total 19 [2024-11-16 07:16:58,472 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1813410470] [2024-11-16 07:16:58,472 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:58,473 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-16 07:16:58,473 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:58,474 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-16 07:16:58,479 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-16 07:16:58,480 INFO L87 Difference]: Start difference. First operand 163 states and 198 transitions. Second operand has 19 states, 19 states have (on average 3.9473684210526314) internal successors, (75), 17 states have internal predecessors, (75), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) [2024-11-16 07:16:58,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:58,792 INFO L93 Difference]: Finished difference Result 189 states and 225 transitions. [2024-11-16 07:16:58,793 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-16 07:16:58,793 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 3.9473684210526314) internal successors, (75), 17 states have internal predecessors, (75), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) Word has length 109 [2024-11-16 07:16:58,793 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:58,794 INFO L225 Difference]: With dead ends: 189 [2024-11-16 07:16:58,794 INFO L226 Difference]: Without dead ends: 146 [2024-11-16 07:16:58,795 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 238 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=96, Invalid=366, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:16:58,795 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 12 mSDsluCounter, 339 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 383 SdHoareTripleChecker+Invalid, 277 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:58,795 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 383 Invalid, 277 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:16:58,796 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-16 07:16:58,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 146. [2024-11-16 07:16:58,833 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 96 states have (on average 1.1041666666666667) internal successors, (106), 101 states have internal predecessors, (106), 34 states have call successors, (34), 15 states have call predecessors, (34), 15 states have return successors, (32), 29 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-16 07:16:58,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 172 transitions. [2024-11-16 07:16:58,834 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 172 transitions. Word has length 109 [2024-11-16 07:16:58,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:58,834 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 172 transitions. [2024-11-16 07:16:58,835 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 3.9473684210526314) internal successors, (75), 17 states have internal predecessors, (75), 13 states have call successors, (50), 3 states have call predecessors, (50), 1 states have return successors, (47), 13 states have call predecessors, (47), 13 states have call successors, (47) [2024-11-16 07:16:58,835 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 172 transitions. [2024-11-16 07:16:58,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2024-11-16 07:16:58,836 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:58,836 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:58,853 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-16 07:16:59,040 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-16 07:16:59,041 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:59,041 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:59,041 INFO L85 PathProgramCache]: Analyzing trace with hash 443438552, now seen corresponding path program 1 times [2024-11-16 07:16:59,041 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:59,041 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [827167042] [2024-11-16 07:16:59,042 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:59,042 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:59,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,276 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:59,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,280 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:16:59,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,283 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:16:59,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,286 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:16:59,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,289 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:16:59,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,293 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-16 07:16:59,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,296 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-16 07:16:59,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,298 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-16 07:16:59,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,302 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-16 07:16:59,303 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,305 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-16 07:16:59,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,312 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-16 07:16:59,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,317 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-16 07:16:59,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,320 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-16 07:16:59,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,324 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-16 07:16:59,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,327 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-16 07:16:59,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,331 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-16 07:16:59,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,335 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 106 [2024-11-16 07:16:59,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,338 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 111 [2024-11-16 07:16:59,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,346 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 54 proven. 34 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-16 07:16:59,346 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:59,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [827167042] [2024-11-16 07:16:59,346 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [827167042] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:59,346 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2011071683] [2024-11-16 07:16:59,347 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:59,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:59,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:59,349 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:16:59,354 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-16 07:16:59,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:59,422 INFO L255 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:16:59,424 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:59,492 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 72 proven. 16 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-16 07:16:59,493 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:59,664 INFO L134 CoverageAnalysis]: Checked inductivity of 700 backedges. 72 proven. 16 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-16 07:16:59,664 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2011071683] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:59,664 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:16:59,664 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 6] total 9 [2024-11-16 07:16:59,665 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [228874039] [2024-11-16 07:16:59,665 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:59,665 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-16 07:16:59,665 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:59,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-16 07:16:59,666 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2024-11-16 07:16:59,666 INFO L87 Difference]: Start difference. First operand 146 states and 172 transitions. Second operand has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2024-11-16 07:16:59,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:59,782 INFO L93 Difference]: Finished difference Result 153 states and 178 transitions. [2024-11-16 07:16:59,782 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-16 07:16:59,782 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 122 [2024-11-16 07:16:59,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:59,784 INFO L225 Difference]: With dead ends: 153 [2024-11-16 07:16:59,784 INFO L226 Difference]: Without dead ends: 145 [2024-11-16 07:16:59,784 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 273 SyntacticMatches, 6 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2024-11-16 07:16:59,785 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 9 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 64 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:59,785 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 157 Invalid, 64 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:16:59,786 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-16 07:16:59,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 140. [2024-11-16 07:16:59,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 93 states have (on average 1.096774193548387) internal successors, (102), 97 states have internal predecessors, (102), 31 states have call successors, (31), 15 states have call predecessors, (31), 15 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-16 07:16:59,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 163 transitions. [2024-11-16 07:16:59,848 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 163 transitions. Word has length 122 [2024-11-16 07:16:59,848 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:59,848 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 163 transitions. [2024-11-16 07:16:59,849 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 8 states have call successors, (26), 2 states have call predecessors, (26), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2024-11-16 07:16:59,849 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 163 transitions. [2024-11-16 07:16:59,850 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 126 [2024-11-16 07:16:59,850 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:59,850 INFO L215 NwaCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:59,869 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-16 07:17:00,054 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-16 07:17:00,055 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:17:00,055 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:17:00,055 INFO L85 PathProgramCache]: Analyzing trace with hash -399076229, now seen corresponding path program 3 times [2024-11-16 07:17:00,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:17:00,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1659177070] [2024-11-16 07:17:00,055 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:17:00,056 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:17:00,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,698 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:17:00,700 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,703 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:17:00,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,709 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:17:00,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,714 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:17:00,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,719 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:17:00,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,723 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-16 07:17:00,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,728 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-16 07:17:00,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,732 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-16 07:17:00,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,736 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-16 07:17:00,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,740 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-16 07:17:00,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,744 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-16 07:17:00,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,748 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-16 07:17:00,750 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,753 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-16 07:17:00,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,758 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-16 07:17:00,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,762 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-16 07:17:00,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,767 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-16 07:17:00,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,771 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 106 [2024-11-16 07:17:00,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,777 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 111 [2024-11-16 07:17:00,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,782 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 45 proven. 54 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2024-11-16 07:17:00,782 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:17:00,782 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1659177070] [2024-11-16 07:17:00,783 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1659177070] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:17:00,783 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [96254168] [2024-11-16 07:17:00,783 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 07:17:00,783 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:17:00,783 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:17:00,785 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:17:00,786 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-16 07:17:00,849 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-16 07:17:00,849 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:17:00,850 INFO L255 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-16 07:17:00,853 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:17:01,137 INFO L134 CoverageAnalysis]: Checked inductivity of 711 backedges. 159 proven. 47 refuted. 0 times theorem prover too weak. 505 trivial. 0 not checked. [2024-11-16 07:17:01,137 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:17:26,491 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 10 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)