./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.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_valuebound50.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 63cd3e528fa28694be9f2ecbe948122395c3f48db5408253e949dc50f2a74038 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-16 07:16:00,059 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-16 07:16:00,136 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-16 07:16:00,142 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-16 07:16:00,143 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-16 07:16:00,173 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-16 07:16:00,175 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-16 07:16:00,175 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-16 07:16:00,176 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-16 07:16:00,177 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-16 07:16:00,178 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-16 07:16:00,179 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-16 07:16:00,179 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-16 07:16:00,180 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-16 07:16:00,184 INFO L153 SettingsManager]: * Use SBE=true [2024-11-16 07:16:00,184 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-16 07:16:00,184 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-16 07:16:00,185 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-16 07:16:00,185 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-16 07:16:00,185 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-16 07:16:00,185 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-16 07:16:00,186 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-16 07:16:00,186 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-16 07:16:00,186 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-16 07:16:00,187 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-16 07:16:00,187 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-16 07:16:00,187 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-16 07:16:00,187 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-16 07:16:00,187 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-16 07:16:00,188 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-16 07:16:00,188 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-16 07:16:00,188 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-16 07:16:00,188 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:16:00,189 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-16 07:16:00,189 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-16 07:16:00,192 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-16 07:16:00,192 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-16 07:16:00,192 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-16 07:16:00,192 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-16 07:16:00,192 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-16 07:16:00,193 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-16 07:16:00,193 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-16 07:16:00,194 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 -> 63cd3e528fa28694be9f2ecbe948122395c3f48db5408253e949dc50f2a74038 [2024-11-16 07:16:00,459 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-16 07:16:00,482 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-16 07:16:00,486 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-16 07:16:00,487 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-16 07:16:00,487 INFO L274 PluginConnector]: CDTParser initialized [2024-11-16 07:16:00,489 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c [2024-11-16 07:16:01,989 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-16 07:16:02,165 INFO L384 CDTParser]: Found 1 translation units. [2024-11-16 07:16:02,166 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/hard2_valuebound50.c [2024-11-16 07:16:02,173 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aaae9398a/2afada301f90438db7c443fbc3785417/FLAG5a504027e [2024-11-16 07:16:02,186 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aaae9398a/2afada301f90438db7c443fbc3785417 [2024-11-16 07:16:02,188 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-16 07:16:02,190 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-16 07:16:02,191 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-16 07:16:02,191 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-16 07:16:02,195 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-16 07:16:02,196 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,196 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@497a765b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02, skipping insertion in model container [2024-11-16 07:16:02,197 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,217 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-16 07:16:02,401 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_valuebound50.c[526,539] [2024-11-16 07:16:02,425 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:16:02,440 INFO L200 MainTranslator]: Completed pre-run [2024-11-16 07:16:02,453 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_valuebound50.c[526,539] [2024-11-16 07:16:02,463 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-16 07:16:02,484 INFO L204 MainTranslator]: Completed translation [2024-11-16 07:16:02,484 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02 WrapperNode [2024-11-16 07:16:02,485 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-16 07:16:02,486 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-16 07:16:02,486 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-16 07:16:02,487 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-16 07:16:02,493 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:16:02" (1/1) ... [2024-11-16 07:16:02,502 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:16:02" (1/1) ... [2024-11-16 07:16:02,522 INFO L138 Inliner]: procedures = 14, calls = 23, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 62 [2024-11-16 07:16:02,523 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-16 07:16:02,524 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-16 07:16:02,524 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-16 07:16:02,524 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-16 07:16:02,534 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,535 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,540 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,559 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:16:02,559 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,559 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,562 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,564 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,565 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,569 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,570 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-16 07:16:02,571 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-16 07:16:02,573 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-16 07:16:02,573 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-16 07:16:02,574 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (1/1) ... [2024-11-16 07:16:02,579 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-16 07:16:02,590 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:02,607 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:16:02,610 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:16:02,670 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-16 07:16:02,671 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-16 07:16:02,671 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-16 07:16:02,671 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-16 07:16:02,671 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-16 07:16:02,672 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-16 07:16:02,672 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-16 07:16:02,732 INFO L256 CfgBuilder]: Building ICFG [2024-11-16 07:16:02,733 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-16 07:16:02,870 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-16 07:16:02,871 INFO L307 CfgBuilder]: Performing block encoding [2024-11-16 07:16:02,881 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-16 07:16:02,881 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-16 07:16:02,882 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:16:02 BoogieIcfgContainer [2024-11-16 07:16:02,882 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-16 07:16:02,883 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-16 07:16:02,883 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-16 07:16:02,886 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-16 07:16:02,887 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 16.11 07:16:02" (1/3) ... [2024-11-16 07:16:02,887 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@732d4424 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:16:02, skipping insertion in model container [2024-11-16 07:16:02,888 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.11 07:16:02" (2/3) ... [2024-11-16 07:16:02,888 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@732d4424 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 16.11 07:16:02, skipping insertion in model container [2024-11-16 07:16:02,889 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:16:02" (3/3) ... [2024-11-16 07:16:02,890 INFO L112 eAbstractionObserver]: Analyzing ICFG hard2_valuebound50.c [2024-11-16 07:16:02,902 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-16 07:16:02,902 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-16 07:16:02,953 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-16 07:16:02,960 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;@6288b688, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-16 07:16:02,960 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-16 07:16:02,966 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:02,973 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-16 07:16:02,973 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:02,974 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:02,974 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:02,979 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:02,980 INFO L85 PathProgramCache]: Analyzing trace with hash -292126860, now seen corresponding path program 1 times [2024-11-16 07:16:02,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:02,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1819170654] [2024-11-16 07:16:02,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:02,993 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:03,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:03,160 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:03,161 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:03,161 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1819170654] [2024-11-16 07:16:03,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1819170654] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:03,162 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:03,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-16 07:16:03,164 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [447683883] [2024-11-16 07:16:03,164 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:03,168 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-16 07:16:03,169 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:03,190 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-16 07:16:03,191 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-16 07:16:03,193 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:03,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:03,212 INFO L93 Difference]: Finished difference Result 55 states and 89 transitions. [2024-11-16 07:16:03,213 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-16 07:16:03,214 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:03,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:03,219 INFO L225 Difference]: With dead ends: 55 [2024-11-16 07:16:03,219 INFO L226 Difference]: Without dead ends: 25 [2024-11-16 07:16:03,221 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:03,225 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:03,227 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:03,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-16 07:16:03,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-16 07:16:03,267 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:03,268 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 33 transitions. [2024-11-16 07:16:03,270 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 33 transitions. Word has length 11 [2024-11-16 07:16:03,270 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:03,270 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 33 transitions. [2024-11-16 07:16:03,271 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:03,271 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 33 transitions. [2024-11-16 07:16:03,272 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-16 07:16:03,272 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:03,272 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:03,273 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-16 07:16:03,273 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:03,274 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:03,274 INFO L85 PathProgramCache]: Analyzing trace with hash -2099581323, now seen corresponding path program 1 times [2024-11-16 07:16:03,275 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:03,275 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1406941711] [2024-11-16 07:16:03,276 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:03,276 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:03,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:03,506 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:03,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:03,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1406941711] [2024-11-16 07:16:03,507 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1406941711] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:03,507 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:03,507 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:03,507 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [71975069] [2024-11-16 07:16:03,508 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:03,509 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:03,509 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:03,511 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:03,511 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:03,511 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:03,586 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:03,588 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2024-11-16 07:16:03,589 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:03,589 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:03,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:03,590 INFO L225 Difference]: With dead ends: 40 [2024-11-16 07:16:03,590 INFO L226 Difference]: Without dead ends: 37 [2024-11-16 07:16:03,590 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:03,591 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:03,592 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:03,596 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-16 07:16:03,607 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 29. [2024-11-16 07:16:03,608 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:03,609 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 36 transitions. [2024-11-16 07:16:03,610 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 36 transitions. Word has length 11 [2024-11-16 07:16:03,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:03,611 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 36 transitions. [2024-11-16 07:16:03,611 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:03,612 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 36 transitions. [2024-11-16 07:16:03,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2024-11-16 07:16:03,613 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:03,613 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:03,614 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-16 07:16:03,614 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:03,615 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:03,615 INFO L85 PathProgramCache]: Analyzing trace with hash 2100820203, now seen corresponding path program 1 times [2024-11-16 07:16:03,615 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:03,617 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [149060306] [2024-11-16 07:16:03,617 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:03,617 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:03,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:03,746 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:03,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:03,758 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:03,762 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:03,762 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [149060306] [2024-11-16 07:16:03,763 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [149060306] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:03,763 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:03,763 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:03,763 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1248051143] [2024-11-16 07:16:03,763 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:03,763 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:03,764 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:03,765 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:03,765 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:03,765 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:03,825 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:03,825 INFO L93 Difference]: Finished difference Result 44 states and 55 transitions. [2024-11-16 07:16:03,825 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:03,826 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:03,826 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:03,827 INFO L225 Difference]: With dead ends: 44 [2024-11-16 07:16:03,827 INFO L226 Difference]: Without dead ends: 41 [2024-11-16 07:16:03,827 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:03,828 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:03,828 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:03,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2024-11-16 07:16:03,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2024-11-16 07:16:03,839 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:03,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 39 transitions. [2024-11-16 07:16:03,841 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 39 transitions. Word has length 16 [2024-11-16 07:16:03,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:03,842 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 39 transitions. [2024-11-16 07:16:03,842 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:03,842 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 39 transitions. [2024-11-16 07:16:03,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2024-11-16 07:16:03,843 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:03,843 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:03,843 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-16 07:16:03,843 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:03,844 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:03,844 INFO L85 PathProgramCache]: Analyzing trace with hash 1262954485, now seen corresponding path program 1 times [2024-11-16 07:16:03,847 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:03,847 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1659086685] [2024-11-16 07:16:03,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:03,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:03,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:03,871 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1995898774] [2024-11-16 07:16:03,872 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:03,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:03,873 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:03,875 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:03,877 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:03,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:03,937 INFO L255 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-16 07:16:03,944 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:04,058 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:04,059 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:16:04,060 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:04,060 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1659086685] [2024-11-16 07:16:04,060 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:04,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1995898774] [2024-11-16 07:16:04,061 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1995898774] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:04,062 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:04,062 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:04,062 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [629843295] [2024-11-16 07:16:04,062 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:04,062 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:04,063 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:04,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:04,063 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:04,063 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:04,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:04,143 INFO L93 Difference]: Finished difference Result 63 states and 80 transitions. [2024-11-16 07:16:04,144 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:04,144 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:04,144 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:04,146 INFO L225 Difference]: With dead ends: 63 [2024-11-16 07:16:04,147 INFO L226 Difference]: Without dead ends: 48 [2024-11-16 07:16:04,148 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:04,149 INFO L432 NwaCegarLoop]: 29 mSDtfsCounter, 6 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s 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:04,149 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:04,152 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-11-16 07:16:04,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2024-11-16 07:16:04,165 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:04,166 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 59 transitions. [2024-11-16 07:16:04,167 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 59 transitions. Word has length 21 [2024-11-16 07:16:04,167 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:04,168 INFO L471 AbstractCegarLoop]: Abstraction has 48 states and 59 transitions. [2024-11-16 07:16:04,168 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:04,168 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 59 transitions. [2024-11-16 07:16:04,169 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-16 07:16:04,170 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:04,170 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:04,189 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:04,374 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:04,375 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:04,375 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:04,376 INFO L85 PathProgramCache]: Analyzing trace with hash -23433476, now seen corresponding path program 1 times [2024-11-16 07:16:04,376 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:04,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1236441832] [2024-11-16 07:16:04,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:04,376 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:04,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:04,398 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [739038157] [2024-11-16 07:16:04,400 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:04,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:04,401 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:04,402 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:04,409 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:04,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,465 INFO L255 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:16:04,467 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:04,552 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:04,553 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-16 07:16:04,553 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:04,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1236441832] [2024-11-16 07:16:04,553 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:04,553 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [739038157] [2024-11-16 07:16:04,554 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [739038157] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:04,554 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:04,554 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:04,554 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2144085967] [2024-11-16 07:16:04,554 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:04,555 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:04,555 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:04,555 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:04,556 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:04,556 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:04,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:04,625 INFO L93 Difference]: Finished difference Result 63 states and 78 transitions. [2024-11-16 07:16:04,625 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:04,626 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:04,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:04,627 INFO L225 Difference]: With dead ends: 63 [2024-11-16 07:16:04,627 INFO L226 Difference]: Without dead ends: 60 [2024-11-16 07:16:04,628 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:04,628 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.0s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:04,629 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.0s Time] [2024-11-16 07:16:04,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-16 07:16:04,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2024-11-16 07:16:04,638 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:04,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 74 transitions. [2024-11-16 07:16:04,639 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 74 transitions. Word has length 29 [2024-11-16 07:16:04,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:04,640 INFO L471 AbstractCegarLoop]: Abstraction has 59 states and 74 transitions. [2024-11-16 07:16:04,640 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:04,640 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 74 transitions. [2024-11-16 07:16:04,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-16 07:16:04,641 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:04,641 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:04,662 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:04,841 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:04,842 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:04,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:04,843 INFO L85 PathProgramCache]: Analyzing trace with hash 253378592, now seen corresponding path program 1 times [2024-11-16 07:16:04,843 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:04,843 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [761451211] [2024-11-16 07:16:04,843 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:04,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:04,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:04,878 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [617081213] [2024-11-16 07:16:04,878 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:04,879 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:04,879 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:04,884 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:04,885 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:04,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:04,933 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-16 07:16:04,936 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:05,091 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:05,091 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:05,197 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:05,201 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:05,201 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [761451211] [2024-11-16 07:16:05,201 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:05,202 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [617081213] [2024-11-16 07:16:05,202 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [617081213] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:05,202 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:16:05,202 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2024-11-16 07:16:05,202 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [449618485] [2024-11-16 07:16:05,202 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:05,202 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:05,203 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:05,203 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:05,203 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-16 07:16:05,204 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:06,607 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.34s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:16:06,620 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:06,620 INFO L93 Difference]: Finished difference Result 71 states and 88 transitions. [2024-11-16 07:16:06,620 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:06,621 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:06,621 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:06,623 INFO L225 Difference]: With dead ends: 71 [2024-11-16 07:16:06,623 INFO L226 Difference]: Without dead ends: 68 [2024-11-16 07:16:06,623 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:06,624 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:06,624 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:06,625 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2024-11-16 07:16:06,638 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 67. [2024-11-16 07:16:06,639 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:06,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 83 transitions. [2024-11-16 07:16:06,640 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 83 transitions. Word has length 39 [2024-11-16 07:16:06,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:06,640 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 83 transitions. [2024-11-16 07:16:06,641 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:06,641 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 83 transitions. [2024-11-16 07:16:06,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2024-11-16 07:16:06,642 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:06,642 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:06,659 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-16 07:16:06,842 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:06,843 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:06,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:06,843 INFO L85 PathProgramCache]: Analyzing trace with hash -1361005644, now seen corresponding path program 1 times [2024-11-16 07:16:06,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:06,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1411361578] [2024-11-16 07:16:06,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:06,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:06,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:06,972 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:06,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:06,977 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:16:06,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:06,984 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:16:06,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:06,991 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:16:06,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:06,999 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:16:07,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:07,005 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-11-16 07:16:07,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:07,009 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:07,010 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:07,010 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1411361578] [2024-11-16 07:16:07,010 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1411361578] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-16 07:16:07,010 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-16 07:16:07,010 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-16 07:16:07,011 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1813407267] [2024-11-16 07:16:07,011 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-16 07:16:07,011 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-16 07:16:07,011 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:07,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-16 07:16:07,012 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-16 07:16:07,012 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:07,070 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:07,070 INFO L93 Difference]: Finished difference Result 76 states and 92 transitions. [2024-11-16 07:16:07,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-16 07:16:07,071 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:07,071 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:07,072 INFO L225 Difference]: With dead ends: 76 [2024-11-16 07:16:07,072 INFO L226 Difference]: Without dead ends: 62 [2024-11-16 07:16:07,073 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:07,073 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:07,073 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:07,074 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2024-11-16 07:16:07,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2024-11-16 07:16:07,090 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:07,091 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 75 transitions. [2024-11-16 07:16:07,091 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 75 transitions. Word has length 45 [2024-11-16 07:16:07,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:07,091 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 75 transitions. [2024-11-16 07:16:07,091 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:07,091 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 75 transitions. [2024-11-16 07:16:07,097 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2024-11-16 07:16:07,097 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:07,097 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:07,097 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-16 07:16:07,097 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:07,098 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:07,098 INFO L85 PathProgramCache]: Analyzing trace with hash -646613615, now seen corresponding path program 1 times [2024-11-16 07:16:07,098 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:07,098 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1856794107] [2024-11-16 07:16:07,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:07,098 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:07,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:07,143 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1357391183] [2024-11-16 07:16:07,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:07,143 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:07,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:07,148 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:07,150 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:07,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:07,209 INFO L255 TraceCheckSpWp]: Trace formula consists of 160 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-16 07:16:07,212 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:07,583 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:07,584 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:09,199 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:09,200 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:09,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1856794107] [2024-11-16 07:16:09,200 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:09,200 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1357391183] [2024-11-16 07:16:09,200 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1357391183] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:09,200 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:09,201 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2024-11-16 07:16:09,201 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1067109260] [2024-11-16 07:16:09,201 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:09,201 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-16 07:16:09,202 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:09,202 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-16 07:16:09,202 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2024-11-16 07:16:09,203 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:09,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:09,861 INFO L93 Difference]: Finished difference Result 148 states and 193 transitions. [2024-11-16 07:16:09,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-16 07:16:09,862 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:09,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:09,864 INFO L225 Difference]: With dead ends: 148 [2024-11-16 07:16:09,864 INFO L226 Difference]: Without dead ends: 122 [2024-11-16 07:16:09,865 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 107 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2024-11-16 07:16:09,865 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:09,866 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:09,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2024-11-16 07:16:09,894 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 120. [2024-11-16 07:16:09,895 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:09,896 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 153 transitions. [2024-11-16 07:16:09,896 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 153 transitions. Word has length 61 [2024-11-16 07:16:09,896 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:09,896 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 153 transitions. [2024-11-16 07:16:09,897 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:09,897 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 153 transitions. [2024-11-16 07:16:09,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-16 07:16:09,901 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:09,901 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:09,920 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-16 07:16:10,105 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:10,106 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:10,106 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:10,107 INFO L85 PathProgramCache]: Analyzing trace with hash -641848553, now seen corresponding path program 1 times [2024-11-16 07:16:10,107 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:10,107 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1918021988] [2024-11-16 07:16:10,107 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:10,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:10,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:10,131 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1499015306] [2024-11-16 07:16:10,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:10,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:10,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:10,133 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:10,135 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:10,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:10,193 INFO L255 TraceCheckSpWp]: Trace formula consists of 180 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-16 07:16:10,195 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:10,557 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:10,557 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:11,331 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:11,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:11,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1918021988] [2024-11-16 07:16:11,333 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:11,334 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1499015306] [2024-11-16 07:16:11,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1499015306] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:11,334 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:11,334 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 20 [2024-11-16 07:16:11,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [343617951] [2024-11-16 07:16:11,334 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:11,335 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-16 07:16:11,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:11,336 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-16 07:16:11,336 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=294, Unknown=0, NotChecked=0, Total=380 [2024-11-16 07:16:11,337 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:11,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:11,877 INFO L93 Difference]: Finished difference Result 192 states and 246 transitions. [2024-11-16 07:16:11,877 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-16 07:16:11,878 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:11,878 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:11,880 INFO L225 Difference]: With dead ends: 192 [2024-11-16 07:16:11,880 INFO L226 Difference]: Without dead ends: 140 [2024-11-16 07:16:11,881 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:11,881 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.4s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:11,881 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.4s Time] [2024-11-16 07:16:11,882 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-11-16 07:16:11,908 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 113. [2024-11-16 07:16:11,909 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:11,910 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 137 transitions. [2024-11-16 07:16:11,910 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 137 transitions. Word has length 72 [2024-11-16 07:16:11,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:11,910 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 137 transitions. [2024-11-16 07:16:11,910 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:11,911 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 137 transitions. [2024-11-16 07:16:11,914 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-16 07:16:11,914 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:11,915 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:11,932 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:12,115 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:12,116 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:12,116 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:12,116 INFO L85 PathProgramCache]: Analyzing trace with hash 1640886345, now seen corresponding path program 1 times [2024-11-16 07:16:12,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:12,116 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1521853473] [2024-11-16 07:16:12,116 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:12,117 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:12,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,440 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:12,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,445 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:16:12,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,449 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:16:12,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,457 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:16:12,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,464 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:16:12,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,472 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-16 07:16:12,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,476 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-16 07:16:12,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,480 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-16 07:16:12,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,484 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2024-11-16 07:16:12,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,491 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 61 [2024-11-16 07:16:12,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,495 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 67 [2024-11-16 07:16:12,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,501 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:12,501 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:12,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1521853473] [2024-11-16 07:16:12,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1521853473] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:12,502 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1905800089] [2024-11-16 07:16:12,502 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:12,502 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:12,502 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:12,504 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:12,506 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:12,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:12,561 INFO L255 TraceCheckSpWp]: Trace formula consists of 189 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-16 07:16:12,563 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:12,725 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:12,726 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:13,115 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:13,115 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1905800089] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:13,115 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:16:13,115 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 13 [2024-11-16 07:16:13,116 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2035278265] [2024-11-16 07:16:13,116 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:13,116 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-16 07:16:13,117 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:13,117 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-16 07:16:13,117 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=120, Unknown=0, NotChecked=0, Total=156 [2024-11-16 07:16:13,118 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:13,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:13,280 INFO L93 Difference]: Finished difference Result 133 states and 157 transitions. [2024-11-16 07:16:13,280 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-16 07:16:13,281 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:13,281 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:13,282 INFO L225 Difference]: With dead ends: 133 [2024-11-16 07:16:13,282 INFO L226 Difference]: Without dead ends: 103 [2024-11-16 07:16:13,282 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:13,283 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:13,283 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:13,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-16 07:16:13,313 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2024-11-16 07:16:13,314 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:13,315 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 120 transitions. [2024-11-16 07:16:13,315 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 120 transitions. Word has length 77 [2024-11-16 07:16:13,315 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:13,315 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 120 transitions. [2024-11-16 07:16:13,316 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:13,316 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 120 transitions. [2024-11-16 07:16:13,317 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 94 [2024-11-16 07:16:13,317 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:13,317 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:13,334 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-16 07:16:13,521 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:13,522 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:13,522 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:13,522 INFO L85 PathProgramCache]: Analyzing trace with hash 985163622, now seen corresponding path program 2 times [2024-11-16 07:16:13,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:13,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2100509269] [2024-11-16 07:16:13,523 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:13,523 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:13,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:13,573 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2048499624] [2024-11-16 07:16:13,574 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:16:13,574 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:13,574 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:13,576 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:13,577 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:13,641 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:16:13,642 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:16:13,648 INFO L255 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 45 conjuncts are in the unsatisfiable core [2024-11-16 07:16:13,651 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:14,034 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:14,034 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:26,321 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:26,321 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:26,321 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2100509269] [2024-11-16 07:16:26,321 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:26,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2048499624] [2024-11-16 07:16:26,322 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2048499624] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:26,322 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:26,322 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2024-11-16 07:16:26,322 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [571946628] [2024-11-16 07:16:26,322 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:26,322 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-16 07:16:26,323 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:26,323 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-16 07:16:26,323 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2024-11-16 07:16:26,326 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:38,213 WARN L286 SmtUtils]: Spent 11.66s 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:39,974 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.27s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:16:41,218 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.22s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:16:44,617 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-16 07:16:45,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:45,981 INFO L93 Difference]: Finished difference Result 226 states and 289 transitions. [2024-11-16 07:16:45,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-16 07:16:45,981 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:45,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:45,984 INFO L225 Difference]: With dead ends: 226 [2024-11-16 07:16:45,984 INFO L226 Difference]: Without dead ends: 189 [2024-11-16 07:16:45,984 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 165 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 14.8s TimeCoverageRelationStatistics Valid=158, Invalid=544, Unknown=0, NotChecked=0, Total=702 [2024-11-16 07:16:45,985 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 83 mSDsluCounter, 450 mSDsCounter, 0 mSdLazyCounter, 577 mSolverCounterSat, 112 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.2s 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, 6.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:45,985 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [92 Valid, 498 Invalid, 689 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [112 Valid, 577 Invalid, 0 Unknown, 0 Unchecked, 6.2s Time] [2024-11-16 07:16:45,986 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 189 states. [2024-11-16 07:16:46,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 189 to 185. [2024-11-16 07:16:46,041 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:46,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 236 transitions. [2024-11-16 07:16:46,043 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 236 transitions. Word has length 93 [2024-11-16 07:16:46,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:46,044 INFO L471 AbstractCegarLoop]: Abstraction has 185 states and 236 transitions. [2024-11-16 07:16:46,044 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:46,044 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 236 transitions. [2024-11-16 07:16:46,046 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2024-11-16 07:16:46,046 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:46,046 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:46,064 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-16 07:16:46,250 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:46,251 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:46,252 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:46,252 INFO L85 PathProgramCache]: Analyzing trace with hash 515453474, now seen corresponding path program 2 times [2024-11-16 07:16:46,252 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:46,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1705768012] [2024-11-16 07:16:46,253 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:46,253 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:46,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:46,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2129237594] [2024-11-16 07:16:46,314 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:16:46,314 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:46,314 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:46,317 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:46,318 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:46,390 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:16:46,390 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:16:46,392 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-16 07:16:46,394 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:46,861 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-16 07:16:46,862 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:49,910 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 32 proven. 74 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-16 07:16:49,911 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:49,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1705768012] [2024-11-16 07:16:49,911 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:49,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2129237594] [2024-11-16 07:16:49,911 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2129237594] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:49,911 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:16:49,911 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 27 [2024-11-16 07:16:49,911 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1491468340] [2024-11-16 07:16:49,912 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:49,912 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-16 07:16:49,912 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:49,913 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-16 07:16:49,913 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=555, Unknown=0, NotChecked=0, Total=702 [2024-11-16 07:16:49,913 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:56,102 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:56,102 INFO L93 Difference]: Finished difference Result 268 states and 345 transitions. [2024-11-16 07:16:56,102 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-16 07:16:56,102 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,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:56,104 INFO L225 Difference]: With dead ends: 268 [2024-11-16 07:16:56,104 INFO L226 Difference]: Without dead ends: 194 [2024-11-16 07:16:56,105 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 215 GetRequests, 181 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 192 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=292, Invalid=968, Unknown=0, NotChecked=0, Total=1260 [2024-11-16 07:16:56,105 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 80 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 411 mSolverCounterSat, 121 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 84 SdHoareTripleChecker+Valid, 404 SdHoareTripleChecker+Invalid, 532 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 121 IncrementalHoareTripleChecker+Valid, 411 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:56,106 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [84 Valid, 404 Invalid, 532 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [121 Valid, 411 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-16 07:16:56,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 194 states. [2024-11-16 07:16:56,153 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 194 to 165. [2024-11-16 07:16:56,153 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 165 states, 108 states have (on average 1.1111111111111112) internal successors, (120), 114 states have internal predecessors, (120), 41 states have call successors, (41), 15 states have call predecessors, (41), 15 states have return successors, (40), 35 states have call predecessors, (40), 40 states have call successors, (40) [2024-11-16 07:16:56,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 201 transitions. [2024-11-16 07:16:56,155 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 201 transitions. Word has length 104 [2024-11-16 07:16:56,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:56,155 INFO L471 AbstractCegarLoop]: Abstraction has 165 states and 201 transitions. [2024-11-16 07:16:56,155 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,156 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 201 transitions. [2024-11-16 07:16:56,157 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2024-11-16 07:16:56,157 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:56,157 INFO L215 NwaCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:16:56,171 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,357 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,358 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:56,358 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:56,358 INFO L85 PathProgramCache]: Analyzing trace with hash -329018397, now seen corresponding path program 1 times [2024-11-16 07:16:56,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:56,359 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [829441205] [2024-11-16 07:16:56,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:56,359 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:56,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:16:56,393 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [679570282] [2024-11-16 07:16:56,394 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:56,394 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:56,394 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:56,398 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:56,400 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:56,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:56,464 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 46 conjuncts are in the unsatisfiable core [2024-11-16 07:16:56,466 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:56,807 INFO L134 CoverageAnalysis]: Checked inductivity of 484 backedges. 29 proven. 77 refuted. 0 times theorem prover too weak. 378 trivial. 0 not checked. [2024-11-16 07:16:56,808 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:57,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:57,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [829441205] [2024-11-16 07:16:57,536 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:16:57,536 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [679570282] [2024-11-16 07:16:57,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [679570282] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:57,537 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:16:57,537 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2024-11-16 07:16:57,537 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [965564999] [2024-11-16 07:16:57,537 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:57,538 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-16 07:16:57,539 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:57,539 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-16 07:16:57,539 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=326, Unknown=0, NotChecked=0, Total=420 [2024-11-16 07:16:57,540 INFO L87 Difference]: Start difference. First operand 165 states and 201 transitions. Second operand has 14 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 13 states have internal predecessors, (34), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2024-11-16 07:16:57,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:16:57,812 INFO L93 Difference]: Finished difference Result 174 states and 210 transitions. [2024-11-16 07:16:57,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-16 07:16:57,813 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 13 states have internal predecessors, (34), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 104 [2024-11-16 07:16:57,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:16:57,814 INFO L225 Difference]: With dead ends: 174 [2024-11-16 07:16:57,814 INFO L226 Difference]: Without dead ends: 171 [2024-11-16 07:16:57,815 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 119 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=101, Invalid=361, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:16:57,815 INFO L432 NwaCegarLoop]: 40 mSDtfsCounter, 4 mSDsluCounter, 323 mSDsCounter, 0 mSdLazyCounter, 368 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 363 SdHoareTripleChecker+Invalid, 382 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 368 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:16:57,815 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 363 Invalid, 382 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 368 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:16:57,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2024-11-16 07:16:57,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 163. [2024-11-16 07:16:57,872 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:57,873 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 198 transitions. [2024-11-16 07:16:57,874 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 198 transitions. Word has length 104 [2024-11-16 07:16:57,874 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:16:57,874 INFO L471 AbstractCegarLoop]: Abstraction has 163 states and 198 transitions. [2024-11-16 07:16:57,874 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 13 states have internal predecessors, (34), 6 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2024-11-16 07:16:57,874 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 198 transitions. [2024-11-16 07:16:57,875 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 110 [2024-11-16 07:16:57,875 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:16:57,876 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:57,894 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:58,076 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:58,077 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:16:58,077 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:16:58,078 INFO L85 PathProgramCache]: Analyzing trace with hash 107255838, now seen corresponding path program 2 times [2024-11-16 07:16:58,079 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:16:58,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1386289051] [2024-11-16 07:16:58,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:16:58,079 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:16:58,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,450 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:16:58,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,455 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:16:58,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,458 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:16:58,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,462 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:16:58,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,466 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:16:58,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,470 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-16 07:16:58,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,475 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-16 07:16:58,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,480 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-16 07:16:58,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,484 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-16 07:16:58,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,493 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-16 07:16:58,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,497 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-16 07:16:58,499 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,501 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 74 [2024-11-16 07:16:58,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,505 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 79 [2024-11-16 07:16:58,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,512 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 88 [2024-11-16 07:16:58,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,515 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 93 [2024-11-16 07:16:58,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,518 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 99 [2024-11-16 07:16:58,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:16:58,521 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,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:16:58,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1386289051] [2024-11-16 07:16:58,523 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1386289051] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:16:58,523 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [172925546] [2024-11-16 07:16:58,523 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:16:58,524 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:16:58,524 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:16:58,525 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:58,526 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:58,592 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:16:58,593 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:16:58,594 INFO L255 TraceCheckSpWp]: Trace formula consists of 253 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-16 07:16:58,596 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:16:58,840 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,840 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:16:59,859 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:59,860 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [172925546] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:16:59,860 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:16:59,860 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 8] total 19 [2024-11-16 07:16:59,860 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [615215483] [2024-11-16 07:16:59,860 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:16:59,861 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-16 07:16:59,861 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:16:59,861 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-16 07:16:59,862 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-16 07:16:59,862 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:17:00,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:17:00,180 INFO L93 Difference]: Finished difference Result 189 states and 225 transitions. [2024-11-16 07:17:00,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-16 07:17:00,181 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:17:00,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:17:00,182 INFO L225 Difference]: With dead ends: 189 [2024-11-16 07:17:00,183 INFO L226 Difference]: Without dead ends: 146 [2024-11-16 07:17:00,183 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 237 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 134 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=96, Invalid=366, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:17:00,184 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 13 mSDsluCounter, 288 mSDsCounter, 0 mSdLazyCounter, 264 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 332 SdHoareTripleChecker+Invalid, 284 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 264 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-16 07:17:00,184 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 332 Invalid, 284 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 264 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-16 07:17:00,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-16 07:17:00,236 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 146. [2024-11-16 07:17:00,236 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:17:00,237 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 172 transitions. [2024-11-16 07:17:00,237 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 172 transitions. Word has length 109 [2024-11-16 07:17:00,238 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:17:00,238 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 172 transitions. [2024-11-16 07:17:00,238 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:17:00,238 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 172 transitions. [2024-11-16 07:17:00,239 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2024-11-16 07:17:00,241 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:17:00,241 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:17:00,258 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-16 07:17:00,442 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,442 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:17:00,442 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:17:00,443 INFO L85 PathProgramCache]: Analyzing trace with hash 443438552, now seen corresponding path program 2 times [2024-11-16 07:17:00,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:17:00,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [573739793] [2024-11-16 07:17:00,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:17:00,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:17:00,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,638 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-16 07:17:00,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,641 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-16 07:17:00,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,644 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-11-16 07:17:00,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,649 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2024-11-16 07:17:00,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,652 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-16 07:17:00,653 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,655 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-16 07:17:00,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,658 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 42 [2024-11-16 07:17:00,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,661 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-16 07:17:00,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,664 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2024-11-16 07:17:00,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,667 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-16 07:17:00,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,672 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 65 [2024-11-16 07:17:00,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,675 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 70 [2024-11-16 07:17:00,676 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,678 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 78 [2024-11-16 07:17:00,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,681 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 83 [2024-11-16 07:17:00,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,684 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 92 [2024-11-16 07:17:00,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,687 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 97 [2024-11-16 07:17:00,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,690 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 106 [2024-11-16 07:17:00,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,693 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 111 [2024-11-16 07:17:00,694 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-16 07:17:00,696 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:17:00,696 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:17:00,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [573739793] [2024-11-16 07:17:00,697 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [573739793] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:17:00,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [25800266] [2024-11-16 07:17:00,697 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-16 07:17:00,697 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:17:00,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:17:00,699 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,701 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,770 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-16 07:17:00,771 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:17:00,772 INFO L255 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-16 07:17:00,775 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:17:00,841 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:17:00,841 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:17:00,972 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:17:00,972 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [25800266] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:17:00,972 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-16 07:17:00,972 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 6] total 9 [2024-11-16 07:17:00,972 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1802376932] [2024-11-16 07:17:00,973 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-16 07:17:00,973 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-16 07:17:00,973 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:17:00,974 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-16 07:17:00,974 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2024-11-16 07:17:00,974 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:17:01,095 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:17:01,095 INFO L93 Difference]: Finished difference Result 153 states and 178 transitions. [2024-11-16 07:17:01,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-16 07:17:01,096 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:17:01,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:17:01,097 INFO L225 Difference]: With dead ends: 153 [2024-11-16 07:17:01,097 INFO L226 Difference]: Without dead ends: 145 [2024-11-16 07:17:01,097 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 273 SyntacticMatches, 6 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2024-11-16 07:17:01,098 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 8 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:17:01,098 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 151 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:17:01,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-16 07:17:01,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 140. [2024-11-16 07:17:01,137 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:17:01,137 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 163 transitions. [2024-11-16 07:17:01,138 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 163 transitions. Word has length 122 [2024-11-16 07:17:01,138 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:17:01,138 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 163 transitions. [2024-11-16 07:17:01,138 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:17:01,138 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 163 transitions. [2024-11-16 07:17:01,140 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 126 [2024-11-16 07:17:01,140 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:17:01,140 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:17:01,154 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-16 07:17:01,341 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-16 07:17:01,341 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:17:01,341 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:17:01,341 INFO L85 PathProgramCache]: Analyzing trace with hash -399076229, now seen corresponding path program 3 times [2024-11-16 07:17:01,341 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:17:01,341 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1442324129] [2024-11-16 07:17:01,342 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:17:01,342 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:17:01,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:17:01,396 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1666880693] [2024-11-16 07:17:01,396 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 07:17:01,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:17:01,397 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:17:01,399 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:17:01,400 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-16 07:17:01,462 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-16 07:17:01,462 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:17:01,463 INFO L255 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-16 07:17:01,466 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:17:01,628 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,629 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:17:03,449 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:17:03,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1442324129] [2024-11-16 07:17:03,449 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:17:03,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1666880693] [2024-11-16 07:17:03,450 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1666880693] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-16 07:17:03,450 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-16 07:17:03,450 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2024-11-16 07:17:03,450 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [891768351] [2024-11-16 07:17:03,450 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-16 07:17:03,451 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-16 07:17:03,451 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:17:03,451 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-16 07:17:03,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2024-11-16 07:17:03,452 INFO L87 Difference]: Start difference. First operand 140 states and 163 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 9 states have internal predecessors, (29), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-16 07:17:03,629 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:17:03,629 INFO L93 Difference]: Finished difference Result 148 states and 170 transitions. [2024-11-16 07:17:03,630 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-16 07:17:03,630 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 9 states have internal predecessors, (29), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) Word has length 125 [2024-11-16 07:17:03,630 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:17:03,631 INFO L225 Difference]: With dead ends: 148 [2024-11-16 07:17:03,631 INFO L226 Difference]: Without dead ends: 145 [2024-11-16 07:17:03,632 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=65, Invalid=241, Unknown=0, NotChecked=0, Total=306 [2024-11-16 07:17:03,632 INFO L432 NwaCegarLoop]: 20 mSDtfsCounter, 23 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 78 SdHoareTripleChecker+Invalid, 118 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:17:03,633 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 78 Invalid, 118 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:17:03,634 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-16 07:17:03,687 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 144. [2024-11-16 07:17:03,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 96 states have (on average 1.09375) internal successors, (105), 100 states have internal predecessors, (105), 31 states have call successors, (31), 16 states have call predecessors, (31), 16 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2024-11-16 07:17:03,690 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 166 transitions. [2024-11-16 07:17:03,691 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 166 transitions. Word has length 125 [2024-11-16 07:17:03,691 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:17:03,692 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 166 transitions. [2024-11-16 07:17:03,692 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 9 states have internal predecessors, (29), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (11), 4 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-16 07:17:03,692 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 166 transitions. [2024-11-16 07:17:03,693 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 137 [2024-11-16 07:17:03,693 INFO L207 NwaCegarLoop]: Found error trace [2024-11-16 07:17:03,693 INFO L215 NwaCegarLoop]: trace histogram [21, 20, 20, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:17:03,710 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-16 07:17:03,893 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-11-16 07:17:03,894 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-16 07:17:03,894 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-16 07:17:03,894 INFO L85 PathProgramCache]: Analyzing trace with hash -1843431955, now seen corresponding path program 3 times [2024-11-16 07:17:03,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-16 07:17:03,894 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [686836760] [2024-11-16 07:17:03,894 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-16 07:17:03,894 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-16 07:17:03,944 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-16 07:17:03,945 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [951328490] [2024-11-16 07:17:03,945 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-16 07:17:03,945 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-16 07:17:03,945 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-16 07:17:03,947 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-16 07:17:03,948 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-16 07:17:04,007 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-16 07:17:04,007 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-16 07:17:04,008 INFO L255 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-16 07:17:04,011 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-16 07:17:04,145 INFO L134 CoverageAnalysis]: Checked inductivity of 869 backedges. 163 proven. 56 refuted. 0 times theorem prover too weak. 650 trivial. 0 not checked. [2024-11-16 07:17:04,146 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-16 07:17:04,301 INFO L134 CoverageAnalysis]: Checked inductivity of 869 backedges. 152 proven. 2 refuted. 0 times theorem prover too weak. 715 trivial. 0 not checked. [2024-11-16 07:17:04,301 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-16 07:17:04,301 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [686836760] [2024-11-16 07:17:04,301 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-16 07:17:04,302 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [951328490] [2024-11-16 07:17:04,302 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [951328490] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-16 07:17:04,302 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-16 07:17:04,302 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 16 [2024-11-16 07:17:04,302 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1322061170] [2024-11-16 07:17:04,302 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-16 07:17:04,302 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-16 07:17:04,302 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-16 07:17:04,303 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-16 07:17:04,303 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2024-11-16 07:17:04,303 INFO L87 Difference]: Start difference. First operand 144 states and 166 transitions. Second operand has 16 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 11 states have internal predecessors, (40), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2024-11-16 07:17:04,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-16 07:17:04,488 INFO L93 Difference]: Finished difference Result 145 states and 167 transitions. [2024-11-16 07:17:04,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-16 07:17:04,489 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 11 states have internal predecessors, (40), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) Word has length 136 [2024-11-16 07:17:04,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-16 07:17:04,489 INFO L225 Difference]: With dead ends: 145 [2024-11-16 07:17:04,490 INFO L226 Difference]: Without dead ends: 0 [2024-11-16 07:17:04,490 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 278 GetRequests, 258 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=98, Invalid=364, Unknown=0, NotChecked=0, Total=462 [2024-11-16 07:17:04,491 INFO L432 NwaCegarLoop]: 18 mSDtfsCounter, 44 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-16 07:17:04,491 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 133 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-16 07:17:04,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-16 07:17:04,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-16 07:17:04,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-16 07:17:04,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-16 07:17:04,492 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 136 [2024-11-16 07:17:04,492 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-16 07:17:04,492 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-16 07:17:04,492 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 12 states have (on average 3.3333333333333335) internal successors, (40), 11 states have internal predecessors, (40), 7 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2024-11-16 07:17:04,493 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-16 07:17:04,493 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-16 07:17:04,496 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-16 07:17:04,511 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-16 07:17:04,700 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-16 07:17:04,703 INFO L407 BasicCegarLoop]: Path program histogram: [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-16 07:17:04,705 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-11-16 07:17:07,331 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-16 07:17:07,349 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 16.11 07:17:07 BoogieIcfgContainer [2024-11-16 07:17:07,350 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-16 07:17:07,350 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-16 07:17:07,350 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-16 07:17:07,351 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-16 07:17:07,351 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 16.11 07:16:02" (3/4) ... [2024-11-16 07:17:07,353 INFO L143 WitnessPrinter]: Generating witness for correct program [2024-11-16 07:17:07,357 INFO L393 IcfgBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-11-16 07:17:07,360 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 20 nodes and edges [2024-11-16 07:17:07,361 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 7 nodes and edges [2024-11-16 07:17:07,361 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2024-11-16 07:17:07,361 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-16 07:17:07,361 INFO L925 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-11-16 07:17:07,435 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-16 07:17:07,435 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.yml [2024-11-16 07:17:07,435 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-16 07:17:07,436 INFO L158 Benchmark]: Toolchain (without parser) took 65246.08ms. Allocated memory was 178.3MB in the beginning and 310.4MB in the end (delta: 132.1MB). Free memory was 107.3MB in the beginning and 144.7MB in the end (delta: -37.4MB). Peak memory consumption was 96.2MB. Max. memory is 16.1GB. [2024-11-16 07:17:07,436 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 119.5MB. Free memory is still 79.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-16 07:17:07,436 INFO L158 Benchmark]: CACSL2BoogieTranslator took 294.34ms. Allocated memory is still 178.3MB. Free memory was 107.1MB in the beginning and 94.3MB in the end (delta: 12.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-16 07:17:07,436 INFO L158 Benchmark]: Boogie Procedure Inliner took 37.84ms. Allocated memory is still 178.3MB. Free memory was 94.3MB in the beginning and 92.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-16 07:17:07,436 INFO L158 Benchmark]: Boogie Preprocessor took 46.63ms. Allocated memory is still 178.3MB. Free memory was 92.8MB in the beginning and 91.2MB in the end (delta: 1.6MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-16 07:17:07,437 INFO L158 Benchmark]: IcfgBuilder took 310.39ms. Allocated memory is still 178.3MB. Free memory was 91.0MB in the beginning and 139.5MB in the end (delta: -48.4MB). Peak memory consumption was 9.3MB. Max. memory is 16.1GB. [2024-11-16 07:17:07,437 INFO L158 Benchmark]: TraceAbstraction took 64466.49ms. Allocated memory was 178.3MB in the beginning and 310.4MB in the end (delta: 132.1MB). Free memory was 139.5MB in the beginning and 148.8MB in the end (delta: -9.4MB). Peak memory consumption was 178.0MB. Max. memory is 16.1GB. [2024-11-16 07:17:07,437 INFO L158 Benchmark]: Witness Printer took 84.90ms. Allocated memory is still 310.4MB. Free memory was 148.8MB in the beginning and 144.7MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-11-16 07:17:07,441 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.18ms. Allocated memory is still 119.5MB. Free memory is still 79.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 294.34ms. Allocated memory is still 178.3MB. Free memory was 107.1MB in the beginning and 94.3MB in the end (delta: 12.8MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 37.84ms. Allocated memory is still 178.3MB. Free memory was 94.3MB in the beginning and 92.8MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 46.63ms. Allocated memory is still 178.3MB. Free memory was 92.8MB in the beginning and 91.2MB in the end (delta: 1.6MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 310.39ms. Allocated memory is still 178.3MB. Free memory was 91.0MB in the beginning and 139.5MB in the end (delta: -48.4MB). Peak memory consumption was 9.3MB. Max. memory is 16.1GB. * TraceAbstraction took 64466.49ms. Allocated memory was 178.3MB in the beginning and 310.4MB in the end (delta: 132.1MB). Free memory was 139.5MB in the beginning and 148.8MB in the end (delta: -9.4MB). Peak memory consumption was 178.0MB. Max. memory is 16.1GB. * Witness Printer took 84.90ms. Allocated memory is still 310.4MB. Free memory was 148.8MB in the beginning and 144.7MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 61.8s, OverallIterations: 17, TraceHistogramMax: 21, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 30.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 415 SdHoareTripleChecker+Valid, 10.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 367 mSDsluCounter, 3259 SdHoareTripleChecker+Invalid, 10.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2691 mSDsCounter, 467 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2725 IncrementalHoareTripleChecker+Invalid, 3192 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 467 mSolverCounterUnsat, 568 mSDtfsCounter, 2725 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2118 GetRequests, 1886 SyntacticMatches, 13 SemanticMatches, 219 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 739 ImplicationChecksByTransitivity, 23.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=185occurred in iteration=11, InterpolantAutomatonStates: 170, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.5s AutomataMinimizationTime, 17 MinimizatonAttempts, 94 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 26.7s InterpolantComputationTime, 2267 NumberOfCodeBlocks, 2149 NumberOfCodeBlocksAsserted, 40 NumberOfCheckSat, 2267 ConstructedInterpolants, 0 QuantifiedInterpolants, 26801 SizeOfPredicates, 29 NumberOfNonLiveVariables, 2436 ConjunctsInSsa, 360 ConjunctsInUnsatCore, 29 InterpolantComputations, 7 PerfectInterpolantSequences, 9236/10040 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 34]: Location Invariant Derived location invariant: null - InvariantResult [Line: 22]: Location Invariant Derived location invariant: ((((1 <= p) && (A == ((long long) q + r))) && (d == p)) && (B == 1)) - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (cond != 0) Ensures: (cond != 0) RESULT: Ultimate proved your program to be correct! [2024-11-16 07:17:07,520 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE