./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/divbin_valuebound50.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8be7027f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/divbin_valuebound50.i -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 c7a9d89991bb39658ba66b50d9cb80ba7d1aa37f87b1a2f7972fc25c15a1ea38 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dk.perfect-tracechecks-8be7027-m [2024-11-11 20:02:39,989 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-11 20:02:40,053 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-11 20:02:40,063 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-11 20:02:40,064 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-11 20:02:40,086 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-11 20:02:40,086 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-11 20:02:40,087 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-11 20:02:40,087 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-11 20:02:40,087 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-11 20:02:40,087 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-11 20:02:40,088 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-11 20:02:40,088 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-11 20:02:40,088 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-11 20:02:40,089 INFO L153 SettingsManager]: * Use SBE=true [2024-11-11 20:02:40,089 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-11 20:02:40,089 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-11 20:02:40,090 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-11 20:02:40,090 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-11 20:02:40,090 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-11 20:02:40,090 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-11 20:02:40,091 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-11 20:02:40,091 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-11 20:02:40,091 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-11 20:02:40,091 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-11 20:02:40,092 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-11 20:02:40,092 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-11 20:02:40,092 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-11 20:02:40,092 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-11 20:02:40,093 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-11 20:02:40,093 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-11 20:02:40,093 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-11 20:02:40,093 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 20:02:40,094 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-11 20:02:40,094 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-11 20:02:40,094 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-11 20:02:40,094 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-11 20:02:40,095 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-11 20:02:40,095 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-11 20:02:40,095 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-11 20:02:40,095 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-11 20:02:40,096 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-11 20:02:40,096 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 -> c7a9d89991bb39658ba66b50d9cb80ba7d1aa37f87b1a2f7972fc25c15a1ea38 [2024-11-11 20:02:40,281 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-11 20:02:40,299 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-11 20:02:40,301 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-11 20:02:40,302 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-11 20:02:40,302 INFO L274 PluginConnector]: CDTParser initialized [2024-11-11 20:02:40,303 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/divbin_valuebound50.i [2024-11-11 20:02:41,572 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-11 20:02:41,710 INFO L384 CDTParser]: Found 1 translation units. [2024-11-11 20:02:41,711 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/divbin_valuebound50.i [2024-11-11 20:02:41,717 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c6566a21b/91dd68369122481ea8e73c957c6b8509/FLAG869eaa9c8 [2024-11-11 20:02:41,732 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c6566a21b/91dd68369122481ea8e73c957c6b8509 [2024-11-11 20:02:41,734 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-11 20:02:41,735 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-11 20:02:41,735 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-11 20:02:41,735 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-11 20:02:41,739 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-11 20:02:41,740 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,740 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@32fde0c9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41, skipping insertion in model container [2024-11-11 20:02:41,740 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,756 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-11 20:02:41,884 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/divbin_valuebound50.i[950,963] [2024-11-11 20:02:41,901 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 20:02:41,914 INFO L200 MainTranslator]: Completed pre-run [2024-11-11 20:02:41,924 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/divbin_valuebound50.i[950,963] [2024-11-11 20:02:41,931 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 20:02:41,947 INFO L204 MainTranslator]: Completed translation [2024-11-11 20:02:41,947 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41 WrapperNode [2024-11-11 20:02:41,947 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-11 20:02:41,948 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-11 20:02:41,949 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-11 20:02:41,949 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-11 20:02:41,954 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,959 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,973 INFO L138 Inliner]: procedures = 16, calls = 12, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 48 [2024-11-11 20:02:41,974 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-11 20:02:41,974 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-11 20:02:41,975 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-11 20:02:41,975 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-11 20:02:41,982 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,982 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,983 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,994 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-11-11 20:02:41,995 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,995 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:41,997 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:42,003 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:42,003 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:42,004 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:42,005 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-11 20:02:42,005 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-11 20:02:42,006 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-11 20:02:42,006 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-11 20:02:42,006 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (1/1) ... [2024-11-11 20:02:42,013 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 20:02:42,024 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:02:42,045 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-11 20:02:42,051 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-11 20:02:42,084 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-11 20:02:42,084 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-11 20:02:42,084 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-11 20:02:42,084 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-11 20:02:42,084 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-11 20:02:42,084 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-11 20:02:42,084 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-11 20:02:42,084 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-11 20:02:42,132 INFO L238 CfgBuilder]: Building ICFG [2024-11-11 20:02:42,134 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-11 20:02:42,232 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-11 20:02:42,233 INFO L287 CfgBuilder]: Performing block encoding [2024-11-11 20:02:42,245 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-11 20:02:42,246 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-11 20:02:42,246 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 08:02:42 BoogieIcfgContainer [2024-11-11 20:02:42,246 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-11 20:02:42,248 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-11 20:02:42,248 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-11 20:02:42,250 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-11 20:02:42,250 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.11 08:02:41" (1/3) ... [2024-11-11 20:02:42,251 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ca99c4c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 08:02:42, skipping insertion in model container [2024-11-11 20:02:42,251 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 08:02:41" (2/3) ... [2024-11-11 20:02:42,251 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ca99c4c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 08:02:42, skipping insertion in model container [2024-11-11 20:02:42,251 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 08:02:42" (3/3) ... [2024-11-11 20:02:42,252 INFO L112 eAbstractionObserver]: Analyzing ICFG divbin_valuebound50.i [2024-11-11 20:02:42,264 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-11 20:02:42,264 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-11 20:02:42,305 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-11 20:02:42,310 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;@3a9d6c70, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-11 20:02:42,310 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-11 20:02:42,314 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), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-11 20:02:42,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-11 20:02:42,319 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:02:42,320 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:02:42,320 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:02:42,325 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:02:42,325 INFO L85 PathProgramCache]: Analyzing trace with hash 913242413, now seen corresponding path program 1 times [2024-11-11 20:02:42,332 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:02:42,333 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1262821092] [2024-11-11 20:02:42,333 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:42,333 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:02:42,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:42,469 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:02:42,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:42,480 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 20:02:42,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:42,487 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-11 20:02:42,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:42,494 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-11 20:02:42,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:42,505 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-11 20:02:42,507 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:02:42,507 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1262821092] [2024-11-11 20:02:42,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1262821092] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:02:42,509 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:02:42,509 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-11 20:02:42,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1727370400] [2024-11-11 20:02:42,511 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:02:42,515 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-11 20:02:42,515 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:02:42,535 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-11 20:02:42,536 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-11 20:02:42,538 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), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-11 20:02:42,554 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:02:42,555 INFO L93 Difference]: Finished difference Result 55 states and 84 transitions. [2024-11-11 20:02:42,556 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-11 20:02:42,557 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2024-11-11 20:02:42,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:02:42,585 INFO L225 Difference]: With dead ends: 55 [2024-11-11 20:02:42,585 INFO L226 Difference]: Without dead ends: 25 [2024-11-11 20:02:42,588 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-11 20:02:42,596 INFO L435 NwaCegarLoop]: 35 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, 35 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-11 20:02:42,600 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 20:02:42,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-11 20:02:42,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-11 20:02:42,647 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), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-11 20:02:42,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 31 transitions. [2024-11-11 20:02:42,650 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 31 transitions. Word has length 30 [2024-11-11 20:02:42,650 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:02:42,650 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 31 transitions. [2024-11-11 20:02:42,651 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 6.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-11 20:02:42,651 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 31 transitions. [2024-11-11 20:02:42,652 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-11 20:02:42,652 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:02:42,653 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:02:42,653 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-11 20:02:42,653 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:02:42,654 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:02:42,655 INFO L85 PathProgramCache]: Analyzing trace with hash -2061833476, now seen corresponding path program 1 times [2024-11-11 20:02:42,655 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:02:42,655 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [718133635] [2024-11-11 20:02:42,655 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:42,655 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:02:42,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:02:42,718 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1281241586] [2024-11-11 20:02:42,718 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:42,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:02:42,719 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:02:42,721 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 20:02:42,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-11 20:02:42,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:42,788 INFO L256 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-11 20:02:42,794 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:02:43,105 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-11 20:02:43,105 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:02:43,406 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-11 20:02:43,406 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:02:43,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [718133635] [2024-11-11 20:02:43,407 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:02:43,407 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1281241586] [2024-11-11 20:02:43,407 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1281241586] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-11 20:02:43,408 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-11 20:02:43,408 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [10] total 12 [2024-11-11 20:02:43,408 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [661627787] [2024-11-11 20:02:43,409 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:02:43,409 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-11 20:02:43,409 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:02:43,410 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-11 20:02:43,410 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-11 20:02:43,411 INFO L87 Difference]: Start difference. First operand 25 states and 31 transitions. Second operand has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-11 20:02:43,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:02:43,570 INFO L93 Difference]: Finished difference Result 37 states and 45 transitions. [2024-11-11 20:02:43,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 20:02:43,571 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 31 [2024-11-11 20:02:43,571 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:02:43,572 INFO L225 Difference]: With dead ends: 37 [2024-11-11 20:02:43,572 INFO L226 Difference]: Without dead ends: 34 [2024-11-11 20:02:43,572 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 48 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2024-11-11 20:02:43,573 INFO L435 NwaCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 20:02:43,573 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 91 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 20:02:43,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2024-11-11 20:02:43,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2024-11-11 20:02:43,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 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-11 20:02:43,584 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 41 transitions. [2024-11-11 20:02:43,585 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 41 transitions. Word has length 31 [2024-11-11 20:02:43,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:02:43,587 INFO L471 AbstractCegarLoop]: Abstraction has 34 states and 41 transitions. [2024-11-11 20:02:43,587 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.1666666666666665) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-11 20:02:43,587 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 41 transitions. [2024-11-11 20:02:43,588 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-11 20:02:43,589 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:02:43,589 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:02:43,602 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-11 20:02:43,789 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:02:43,790 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:02:43,790 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:02:43,791 INFO L85 PathProgramCache]: Analyzing trace with hash -1044269705, now seen corresponding path program 1 times [2024-11-11 20:02:43,794 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:02:43,794 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [567632286] [2024-11-11 20:02:43,794 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:43,794 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:02:43,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:02:43,838 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1024163278] [2024-11-11 20:02:43,838 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:43,839 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:02:43,839 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:02:43,840 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 20:02:43,841 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-11 20:02:43,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:43,885 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-11 20:02:43,888 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:02:43,993 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-11 20:02:43,993 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:02:44,073 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-11 20:02:44,073 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:02:44,073 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [567632286] [2024-11-11 20:02:44,074 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:02:44,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1024163278] [2024-11-11 20:02:44,074 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1024163278] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-11 20:02:44,074 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-11 20:02:44,074 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [8] total 9 [2024-11-11 20:02:44,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1312075174] [2024-11-11 20:02:44,074 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:02:44,075 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-11 20:02:44,075 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:02:44,075 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-11 20:02:44,075 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-11 20:02:44,075 INFO L87 Difference]: Start difference. First operand 34 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-11 20:02:48,118 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [1] [2024-11-11 20:02:52,129 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [1] [2024-11-11 20:02:52,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:02:52,143 INFO L93 Difference]: Finished difference Result 44 states and 52 transitions. [2024-11-11 20:02:52,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-11 20:02:52,143 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), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 33 [2024-11-11 20:02:52,144 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:02:52,144 INFO L225 Difference]: With dead ends: 44 [2024-11-11 20:02:52,144 INFO L226 Difference]: Without dead ends: 42 [2024-11-11 20:02:52,145 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 55 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-11 20:02:52,145 INFO L435 NwaCegarLoop]: 25 mSDtfsCounter, 4 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.1s IncrementalHoareTripleChecker+Time [2024-11-11 20:02:52,147 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 94 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 2 Unknown, 0 Unchecked, 8.1s Time] [2024-11-11 20:02:52,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-11-11 20:02:52,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 40. [2024-11-11 20:02:52,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 29 states have internal predecessors, (32), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-11 20:02:52,158 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 47 transitions. [2024-11-11 20:02:52,159 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 47 transitions. Word has length 33 [2024-11-11 20:02:52,159 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:02:52,159 INFO L471 AbstractCegarLoop]: Abstraction has 40 states and 47 transitions. [2024-11-11 20:02:52,160 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), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-11 20:02:52,160 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 47 transitions. [2024-11-11 20:02:52,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-11 20:02:52,161 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:02:52,161 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:02:52,176 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-11 20:02:52,365 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-11 20:02:52,366 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:02:52,366 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:02:52,366 INFO L85 PathProgramCache]: Analyzing trace with hash -1786164585, now seen corresponding path program 1 times [2024-11-11 20:02:52,366 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:02:52,367 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1751024536] [2024-11-11 20:02:52,368 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:52,368 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:02:52,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,781 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:02:52,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,785 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 20:02:52,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,788 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-11 20:02:52,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,794 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-11 20:02:52,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,796 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 27 [2024-11-11 20:02:52,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,811 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-11 20:02:52,811 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:02:52,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1751024536] [2024-11-11 20:02:52,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1751024536] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 20:02:52,811 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 20:02:52,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-11 20:02:52,812 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2071544206] [2024-11-11 20:02:52,812 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 20:02:52,812 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-11 20:02:52,812 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:02:52,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-11 20:02:52,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-11 20:02:52,812 INFO L87 Difference]: Start difference. First operand 40 states and 47 transitions. Second operand has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-11 20:02:52,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:02:52,836 INFO L93 Difference]: Finished difference Result 51 states and 60 transitions. [2024-11-11 20:02:52,836 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-11 20:02:52,837 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2024-11-11 20:02:52,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:02:52,838 INFO L225 Difference]: With dead ends: 51 [2024-11-11 20:02:52,838 INFO L226 Difference]: Without dead ends: 33 [2024-11-11 20:02:52,839 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-11 20:02:52,839 INFO L435 NwaCegarLoop]: 29 mSDtfsCounter, 1 mSDsluCounter, 22 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 51 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-11 20:02:52,840 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 51 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-11 20:02:52,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-11-11 20:02:52,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2024-11-11 20:02:52,849 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 24 states have internal predecessors, (26), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-11 20:02:52,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 39 transitions. [2024-11-11 20:02:52,851 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 39 transitions. Word has length 39 [2024-11-11 20:02:52,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:02:52,851 INFO L471 AbstractCegarLoop]: Abstraction has 33 states and 39 transitions. [2024-11-11 20:02:52,851 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.75) internal successors, (19), 4 states have internal predecessors, (19), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-11 20:02:52,852 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 39 transitions. [2024-11-11 20:02:52,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-11 20:02:52,852 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:02:52,853 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:02:52,853 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-11 20:02:52,853 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:02:52,854 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:02:52,854 INFO L85 PathProgramCache]: Analyzing trace with hash -1444020969, now seen corresponding path program 1 times [2024-11-11 20:02:52,854 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:02:52,854 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [279471892] [2024-11-11 20:02:52,854 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:52,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:02:52,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,978 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:02:52,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,981 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 20:02:52,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,983 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-11 20:02:52,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,985 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-11 20:02:52,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,987 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-11 20:02:52,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:52,996 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-11 20:02:52,996 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:02:52,996 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [279471892] [2024-11-11 20:02:52,996 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [279471892] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 20:02:52,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1670971643] [2024-11-11 20:02:52,997 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:52,997 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:02:52,997 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:02:52,998 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 20:02:52,999 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-11 20:02:53,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:53,037 INFO L256 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-11 20:02:53,039 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:02:53,105 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-11 20:02:53,105 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:02:53,179 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-11 20:02:53,179 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1670971643] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 20:02:53,179 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 20:02:53,179 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 7, 6] total 12 [2024-11-11 20:02:53,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [312926052] [2024-11-11 20:02:53,180 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 20:02:53,180 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-11 20:02:53,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:02:53,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-11 20:02:53,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2024-11-11 20:02:53,181 INFO L87 Difference]: Start difference. First operand 33 states and 39 transitions. Second operand has 12 states, 12 states have (on average 2.8333333333333335) internal successors, (34), 11 states have internal predecessors, (34), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-11 20:02:53,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:02:53,523 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2024-11-11 20:02:53,524 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-11 20:02:53,524 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.8333333333333335) internal successors, (34), 11 states have internal predecessors, (34), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 39 [2024-11-11 20:02:53,525 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:02:53,526 INFO L225 Difference]: With dead ends: 49 [2024-11-11 20:02:53,527 INFO L226 Difference]: Without dead ends: 37 [2024-11-11 20:02:53,527 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 82 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=48, Invalid=192, Unknown=0, NotChecked=0, Total=240 [2024-11-11 20:02:53,528 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 6 mSDsluCounter, 173 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-11 20:02:53,528 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 199 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 104 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-11 20:02:53,529 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-11-11 20:02:53,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 32. [2024-11-11 20:02:53,536 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 6 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-11 20:02:53,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 37 transitions. [2024-11-11 20:02:53,540 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 37 transitions. Word has length 39 [2024-11-11 20:02:53,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:02:53,540 INFO L471 AbstractCegarLoop]: Abstraction has 32 states and 37 transitions. [2024-11-11 20:02:53,540 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.8333333333333335) internal successors, (34), 11 states have internal predecessors, (34), 4 states have call successors, (9), 4 states have call predecessors, (9), 2 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-11 20:02:53,540 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 37 transitions. [2024-11-11 20:02:53,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-11 20:02:53,541 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:02:53,541 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:02:53,556 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-11 20:02:53,741 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:02:53,742 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:02:53,742 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:02:53,742 INFO L85 PathProgramCache]: Analyzing trace with hash 145189394, now seen corresponding path program 1 times [2024-11-11 20:02:53,742 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:02:53,743 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [750485283] [2024-11-11 20:02:53,743 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:53,743 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:02:53,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:02:53,767 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1627383552] [2024-11-11 20:02:53,768 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:02:53,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:02:53,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:02:53,770 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 20:02:53,771 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-11 20:02:53,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:02:53,847 INFO L256 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-11 20:02:53,849 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:02:54,002 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-11 20:02:54,002 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:03:06,525 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:06,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [750485283] [2024-11-11 20:03:06,525 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 20:03:06,526 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1627383552] [2024-11-11 20:03:06,526 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1627383552] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 20:03:06,526 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-11 20:03:06,526 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2024-11-11 20:03:06,526 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1620976299] [2024-11-11 20:03:06,526 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-11 20:03:06,526 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-11 20:03:06,526 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:06,527 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-11 20:03:06,527 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=171, Unknown=3, NotChecked=0, Total=210 [2024-11-11 20:03:06,527 INFO L87 Difference]: Start difference. First operand 32 states and 37 transitions. Second operand has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-11 20:03:06,638 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:06,638 INFO L93 Difference]: Finished difference Result 45 states and 52 transitions. [2024-11-11 20:03:06,638 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-11 20:03:06,639 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 41 [2024-11-11 20:03:06,639 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:06,639 INFO L225 Difference]: With dead ends: 45 [2024-11-11 20:03:06,639 INFO L226 Difference]: Without dead ends: 43 [2024-11-11 20:03:06,640 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 33 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 12.5s TimeCoverageRelationStatistics Valid=42, Invalid=195, Unknown=3, NotChecked=0, Total=240 [2024-11-11 20:03:06,640 INFO L435 NwaCegarLoop]: 16 mSDtfsCounter, 9 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 164 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 165 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 164 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 20:03:06,640 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 132 Invalid, 165 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 164 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 20:03:06,641 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-11 20:03:06,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2024-11-11 20:03:06,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 31 states have internal predecessors, (33), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 6 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-11 20:03:06,650 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 49 transitions. [2024-11-11 20:03:06,650 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 49 transitions. Word has length 41 [2024-11-11 20:03:06,650 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:06,651 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 49 transitions. [2024-11-11 20:03:06,651 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.090909090909091) internal successors, (23), 10 states have internal predecessors, (23), 4 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-11 20:03:06,651 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 49 transitions. [2024-11-11 20:03:06,651 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-11 20:03:06,652 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:06,652 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:03:06,662 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-11 20:03:06,856 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:06,856 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:06,857 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:06,857 INFO L85 PathProgramCache]: Analyzing trace with hash 2114474925, now seen corresponding path program 2 times [2024-11-11 20:03:06,857 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:06,857 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2102318950] [2024-11-11 20:03:06,857 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:06,857 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:06,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,146 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 20:03:07,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,149 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 20:03:07,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,150 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2024-11-11 20:03:07,151 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,151 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-11 20:03:07,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,153 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-11 20:03:07,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,159 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-11-11 20:03:07,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 20:03:07,163 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 9 proven. 5 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-11 20:03:07,164 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 20:03:07,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2102318950] [2024-11-11 20:03:07,164 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2102318950] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 20:03:07,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1940649513] [2024-11-11 20:03:07,164 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-11 20:03:07,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:07,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:07,166 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 20:03:07,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-11 20:03:07,252 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-11 20:03:07,252 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 20:03:07,254 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-11 20:03:07,256 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:07,597 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 12 proven. 11 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-11 20:03:07,597 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:03:08,009 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 12 proven. 11 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-11 20:03:08,010 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1940649513] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 20:03:08,010 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 20:03:08,010 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 11, 9] total 21 [2024-11-11 20:03:08,010 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [290518053] [2024-11-11 20:03:08,010 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 20:03:08,011 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-11 20:03:08,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 20:03:08,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-11 20:03:08,012 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=344, Unknown=0, NotChecked=0, Total=420 [2024-11-11 20:03:08,013 INFO L87 Difference]: Start difference. First operand 42 states and 49 transitions. Second operand has 21 states, 20 states have (on average 2.4) internal successors, (48), 18 states have internal predecessors, (48), 10 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (16), 10 states have call predecessors, (16), 9 states have call successors, (16) [2024-11-11 20:03:08,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 20:03:08,473 INFO L93 Difference]: Finished difference Result 79 states and 95 transitions. [2024-11-11 20:03:08,474 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-11 20:03:08,475 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.4) internal successors, (48), 18 states have internal predecessors, (48), 10 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (16), 10 states have call predecessors, (16), 9 states have call successors, (16) Word has length 49 [2024-11-11 20:03:08,475 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 20:03:08,475 INFO L225 Difference]: With dead ends: 79 [2024-11-11 20:03:08,475 INFO L226 Difference]: Without dead ends: 49 [2024-11-11 20:03:08,476 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 154 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=138, Invalid=564, Unknown=0, NotChecked=0, Total=702 [2024-11-11 20:03:08,476 INFO L435 NwaCegarLoop]: 22 mSDtfsCounter, 63 mSDsluCounter, 149 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 171 SdHoareTripleChecker+Invalid, 175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-11 20:03:08,477 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 171 Invalid, 175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 153 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-11 20:03:08,477 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-11 20:03:08,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 44. [2024-11-11 20:03:08,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 33 states have internal predecessors, (35), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 6 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-11 20:03:08,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 51 transitions. [2024-11-11 20:03:08,492 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 51 transitions. Word has length 49 [2024-11-11 20:03:08,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 20:03:08,493 INFO L471 AbstractCegarLoop]: Abstraction has 44 states and 51 transitions. [2024-11-11 20:03:08,494 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.4) internal successors, (48), 18 states have internal predecessors, (48), 10 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (16), 10 states have call predecessors, (16), 9 states have call successors, (16) [2024-11-11 20:03:08,494 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 51 transitions. [2024-11-11 20:03:08,494 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-11 20:03:08,495 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 20:03:08,495 INFO L218 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 20:03:08,508 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-11 20:03:08,696 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:08,696 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 20:03:08,697 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 20:03:08,697 INFO L85 PathProgramCache]: Analyzing trace with hash 1596822888, now seen corresponding path program 3 times [2024-11-11 20:03:08,697 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 20:03:08,697 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [536331681] [2024-11-11 20:03:08,697 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 20:03:08,697 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 20:03:08,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 20:03:08,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1182830690] [2024-11-11 20:03:08,778 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-11 20:03:08,778 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 20:03:08,778 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 20:03:08,780 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 20:03:08,781 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-11 20:03:08,984 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-11 20:03:08,984 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 20:03:08,986 INFO L256 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 49 conjuncts are in the unsatisfiable core [2024-11-11 20:03:08,988 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 20:03:09,792 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 6 proven. 27 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-11 20:03:09,793 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 20:03:56,054 WARN L286 SmtUtils]: Spent 16.04s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-11 20:04:16,173 WARN L286 SmtUtils]: Spent 16.04s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)