./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c7c6ca5d 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/dijkstra-u_valuebound20.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 ec2a850a3cd9252437037b0e2bf289d9622078bb11b0dcb40fb1cb3d7147f7c5 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-08 14:20:11,197 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-08 14:20:11,255 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-08 14:20:11,261 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-08 14:20:11,261 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-08 14:20:11,285 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-08 14:20:11,286 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-08 14:20:11,286 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-08 14:20:11,287 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-08 14:20:11,288 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-08 14:20:11,288 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-08 14:20:11,289 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-08 14:20:11,289 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-08 14:20:11,289 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-08 14:20:11,290 INFO L153 SettingsManager]: * Use SBE=true [2024-11-08 14:20:11,292 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-08 14:20:11,292 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-08 14:20:11,293 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-08 14:20:11,293 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-08 14:20:11,293 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-08 14:20:11,293 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-08 14:20:11,293 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-08 14:20:11,294 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-08 14:20:11,294 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-08 14:20:11,294 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-08 14:20:11,294 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-08 14:20:11,294 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-08 14:20:11,294 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-08 14:20:11,295 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-08 14:20:11,295 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-08 14:20:11,295 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-08 14:20:11,295 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-08 14:20:11,295 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:20:11,295 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-08 14:20:11,295 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-08 14:20:11,296 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-08 14:20:11,296 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-08 14:20:11,296 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-08 14:20:11,296 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-08 14:20:11,296 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-08 14:20:11,296 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-08 14:20:11,298 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-08 14:20:11,298 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 -> ec2a850a3cd9252437037b0e2bf289d9622078bb11b0dcb40fb1cb3d7147f7c5 [2024-11-08 14:20:11,544 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-08 14:20:11,563 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-08 14:20:11,564 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-08 14:20:11,565 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-08 14:20:11,566 INFO L274 PluginConnector]: CDTParser initialized [2024-11-08 14:20:11,567 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c [2024-11-08 14:20:12,100 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-08 14:20:13,084 INFO L384 CDTParser]: Found 1 translation units. [2024-11-08 14:20:13,090 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/dijkstra-u_valuebound20.c [2024-11-08 14:20:13,099 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7323e688e/461cf0496ace48689e497d494256f928/FLAG8071b4c18 [2024-11-08 14:20:14,422 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7323e688e/461cf0496ace48689e497d494256f928 [2024-11-08 14:20:14,424 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-08 14:20:14,425 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-08 14:20:14,426 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-08 14:20:14,426 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-08 14:20:14,445 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-08 14:20:14,446 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,447 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3462f3a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14, skipping insertion in model container [2024-11-08 14:20:14,447 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,463 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-08 14:20:14,593 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/dijkstra-u_valuebound20.c[525,538] [2024-11-08 14:20:14,614 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:20:14,621 INFO L200 MainTranslator]: Completed pre-run [2024-11-08 14:20:14,630 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/dijkstra-u_valuebound20.c[525,538] [2024-11-08 14:20:14,650 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-08 14:20:14,667 INFO L204 MainTranslator]: Completed translation [2024-11-08 14:20:14,667 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14 WrapperNode [2024-11-08 14:20:14,667 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-08 14:20:14,668 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-08 14:20:14,668 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-08 14:20:14,668 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-08 14:20:14,674 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,679 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,697 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 53 [2024-11-08 14:20:14,698 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-08 14:20:14,698 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-08 14:20:14,698 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-08 14:20:14,698 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-08 14:20:14,714 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,714 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,716 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,725 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-08 14:20:14,725 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,729 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,731 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,737 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,737 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,738 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,739 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-08 14:20:14,740 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-08 14:20:14,740 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-08 14:20:14,740 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-08 14:20:14,741 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (1/1) ... [2024-11-08 14:20:14,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-08 14:20:14,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:20:14,766 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-08 14:20:14,767 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-08 14:20:14,802 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-08 14:20:14,802 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-08 14:20:14,803 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-08 14:20:14,803 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-08 14:20:14,803 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-08 14:20:14,803 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-08 14:20:14,804 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-08 14:20:14,804 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-08 14:20:14,852 INFO L238 CfgBuilder]: Building ICFG [2024-11-08 14:20:14,855 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-08 14:20:15,063 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-08 14:20:15,063 INFO L287 CfgBuilder]: Performing block encoding [2024-11-08 14:20:15,076 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-08 14:20:15,076 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-08 14:20:15,077 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:20:15 BoogieIcfgContainer [2024-11-08 14:20:15,077 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-08 14:20:15,080 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-08 14:20:15,080 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-08 14:20:15,083 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-08 14:20:15,083 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 08.11 02:20:14" (1/3) ... [2024-11-08 14:20:15,084 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7f7f6a16 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:20:15, skipping insertion in model container [2024-11-08 14:20:15,085 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 08.11 02:20:14" (2/3) ... [2024-11-08 14:20:15,085 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7f7f6a16 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 08.11 02:20:15, skipping insertion in model container [2024-11-08 14:20:15,085 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 08.11 02:20:15" (3/3) ... [2024-11-08 14:20:15,086 INFO L112 eAbstractionObserver]: Analyzing ICFG dijkstra-u_valuebound20.c [2024-11-08 14:20:15,099 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-08 14:20:15,099 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-08 14:20:15,150 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-08 14:20:15,156 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;@1d61b514, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-08 14:20:15,157 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-08 14:20:15,160 INFO L276 IsEmpty]: Start isEmpty. Operand has 33 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-08 14:20:15,165 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-08 14:20:15,165 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:20:15,166 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:20:15,166 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:20:15,170 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:20:15,170 INFO L85 PathProgramCache]: Analyzing trace with hash -645822239, now seen corresponding path program 1 times [2024-11-08 14:20:15,178 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:20:15,178 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [680659309] [2024-11-08 14:20:15,178 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:15,179 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:20:15,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:15,274 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:20:15,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:15,280 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:20:15,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:15,286 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:20:15,287 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:20:15,287 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [680659309] [2024-11-08 14:20:15,288 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [680659309] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:20:15,288 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:20:15,288 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-08 14:20:15,289 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [486335949] [2024-11-08 14:20:15,290 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:20:15,292 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-08 14:20:15,293 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:20:15,308 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-08 14:20:15,308 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-08 14:20:15,310 INFO L87 Difference]: Start difference. First operand has 33 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:20:15,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:20:15,324 INFO L93 Difference]: Finished difference Result 63 states and 107 transitions. [2024-11-08 14:20:15,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-08 14:20:15,326 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 19 [2024-11-08 14:20:15,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:20:15,331 INFO L225 Difference]: With dead ends: 63 [2024-11-08 14:20:15,331 INFO L226 Difference]: Without dead ends: 29 [2024-11-08 14:20:15,333 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 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-08 14:20:15,335 INFO L432 NwaCegarLoop]: 44 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:20:15,336 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-08 14:20:15,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2024-11-08 14:20:15,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2024-11-08 14:20:15,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 11 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-08 14:20:15,401 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 40 transitions. [2024-11-08 14:20:15,402 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 40 transitions. Word has length 19 [2024-11-08 14:20:15,407 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:20:15,407 INFO L471 AbstractCegarLoop]: Abstraction has 29 states and 40 transitions. [2024-11-08 14:20:15,407 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-08 14:20:15,408 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 40 transitions. [2024-11-08 14:20:15,409 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-08 14:20:15,409 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:20:15,409 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:20:15,409 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-08 14:20:15,409 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:20:15,409 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:20:15,410 INFO L85 PathProgramCache]: Analyzing trace with hash -1757085840, now seen corresponding path program 1 times [2024-11-08 14:20:15,410 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:20:15,410 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1369473477] [2024-11-08 14:20:15,410 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:15,410 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:20:15,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:15,859 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:20:15,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:15,865 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:20:15,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:15,872 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:20:15,872 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:20:15,872 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1369473477] [2024-11-08 14:20:15,872 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1369473477] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:20:15,872 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:20:15,873 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-08 14:20:15,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1067273567] [2024-11-08 14:20:15,873 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:20:15,875 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-08 14:20:15,878 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:20:15,878 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-08 14:20:15,878 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-08 14:20:15,879 INFO L87 Difference]: Start difference. First operand 29 states and 40 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 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-08 14:20:19,963 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:20:20,028 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:20:20,028 INFO L93 Difference]: Finished difference Result 61 states and 89 transitions. [2024-11-08 14:20:20,029 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-08 14:20:20,029 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 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 20 [2024-11-08 14:20:20,029 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:20:20,030 INFO L225 Difference]: With dead ends: 61 [2024-11-08 14:20:20,030 INFO L226 Difference]: Without dead ends: 43 [2024-11-08 14:20:20,030 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:20:20,031 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 13 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 166 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:20:20,031 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 166 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 49 Invalid, 1 Unknown, 0 Unchecked, 4.1s Time] [2024-11-08 14:20:20,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-08 14:20:20,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2024-11-08 14:20:20,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 43 states, 22 states have (on average 1.2272727272727273) internal successors, (27), 23 states have internal predecessors, (27), 17 states have call successors, (17), 3 states have call predecessors, (17), 3 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2024-11-08 14:20:20,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 60 transitions. [2024-11-08 14:20:20,051 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 60 transitions. Word has length 20 [2024-11-08 14:20:20,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:20:20,051 INFO L471 AbstractCegarLoop]: Abstraction has 43 states and 60 transitions. [2024-11-08 14:20:20,051 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 5 states have internal predecessors, (12), 2 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-08 14:20:20,051 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 60 transitions. [2024-11-08 14:20:20,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-08 14:20:20,052 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:20:20,052 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:20:20,052 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-08 14:20:20,052 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:20:20,053 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:20:20,053 INFO L85 PathProgramCache]: Analyzing trace with hash -332038773, now seen corresponding path program 1 times [2024-11-08 14:20:20,053 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:20:20,053 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1322928838] [2024-11-08 14:20:20,053 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:20,053 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:20:20,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:20,372 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-08 14:20:20,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:20,374 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2024-11-08 14:20:20,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:20,380 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:20:20,380 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:20:20,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1322928838] [2024-11-08 14:20:20,381 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1322928838] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-08 14:20:20,381 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [995464946] [2024-11-08 14:20:20,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:20,381 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:20:20,381 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:20:20,386 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-08 14:20:20,388 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-08 14:20:20,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:20,430 INFO L255 TraceCheckSpWp]: Trace formula consists of 64 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-08 14:20:20,434 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:20:20,586 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:20:20,589 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:20:20,758 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:20:20,758 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [995464946] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:20:20,758 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-08 14:20:20,758 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 15 [2024-11-08 14:20:20,759 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [345917732] [2024-11-08 14:20:20,759 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-08 14:20:20,759 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-08 14:20:20,759 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:20:20,760 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-08 14:20:20,760 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2024-11-08 14:20:20,760 INFO L87 Difference]: Start difference. First operand 43 states and 60 transitions. Second operand has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 13 states have internal predecessors, (28), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:20:21,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:20:21,690 INFO L93 Difference]: Finished difference Result 112 states and 178 transitions. [2024-11-08 14:20:21,694 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-08 14:20:21,695 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 13 states have internal predecessors, (28), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 22 [2024-11-08 14:20:21,695 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:20:21,696 INFO L225 Difference]: With dead ends: 112 [2024-11-08 14:20:21,697 INFO L226 Difference]: Without dead ends: 94 [2024-11-08 14:20:21,697 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 39 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 84 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=93, Invalid=287, Unknown=0, NotChecked=0, Total=380 [2024-11-08 14:20:21,698 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 34 mSDsluCounter, 200 mSDsCounter, 0 mSdLazyCounter, 183 mSolverCounterSat, 140 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 48 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 323 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 140 IncrementalHoareTripleChecker+Valid, 183 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-08 14:20:21,700 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [48 Valid, 236 Invalid, 323 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [140 Valid, 183 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-08 14:20:21,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2024-11-08 14:20:21,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 62. [2024-11-08 14:20:21,726 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 32 states have (on average 1.21875) internal successors, (39), 35 states have internal predecessors, (39), 25 states have call successors, (25), 4 states have call predecessors, (25), 4 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-08 14:20:21,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 88 transitions. [2024-11-08 14:20:21,728 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 88 transitions. Word has length 22 [2024-11-08 14:20:21,729 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:20:21,729 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 88 transitions. [2024-11-08 14:20:21,729 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 13 states have internal predecessors, (28), 4 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-08 14:20:21,729 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 88 transitions. [2024-11-08 14:20:21,730 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-11-08 14:20:21,730 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:20:21,730 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:20:21,748 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-08 14:20:21,934 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:20:21,935 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:20:21,935 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:20:21,936 INFO L85 PathProgramCache]: Analyzing trace with hash 1041809680, now seen corresponding path program 1 times [2024-11-08 14:20:21,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:20:21,936 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1929643545] [2024-11-08 14:20:21,936 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:21,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:20:21,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:20:21,966 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1316079886] [2024-11-08 14:20:21,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:21,966 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:20:21,967 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:20:21,970 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-08 14:20:21,971 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-08 14:20:22,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:22,005 INFO L255 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-08 14:20:22,007 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:20:22,078 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-08 14:20:22,078 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:20:22,078 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:20:22,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1929643545] [2024-11-08 14:20:22,079 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:20:22,079 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1316079886] [2024-11-08 14:20:22,079 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1316079886] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:20:22,080 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:20:22,080 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-08 14:20:22,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [427675675] [2024-11-08 14:20:22,080 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:20:22,080 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-08 14:20:22,080 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:20:22,081 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-08 14:20:22,081 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-08 14:20:22,081 INFO L87 Difference]: Start difference. First operand 62 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:20:26,247 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:20:26,247 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:20:26,247 INFO L93 Difference]: Finished difference Result 87 states and 124 transitions. [2024-11-08 14:20:26,255 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-08 14:20:26,255 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2024-11-08 14:20:26,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:20:26,257 INFO L225 Difference]: With dead ends: 87 [2024-11-08 14:20:26,257 INFO L226 Difference]: Without dead ends: 84 [2024-11-08 14:20:26,257 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 26 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-08 14:20:26,260 INFO L432 NwaCegarLoop]: 37 mSDtfsCounter, 5 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 3 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-11-08 14:20:26,260 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 130 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 33 Invalid, 1 Unknown, 0 Unchecked, 4.1s Time] [2024-11-08 14:20:26,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2024-11-08 14:20:26,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2024-11-08 14:20:26,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 40 states have (on average 1.2) internal successors, (48), 42 states have internal predecessors, (48), 37 states have call successors, (37), 6 states have call predecessors, (37), 6 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2024-11-08 14:20:26,274 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 120 transitions. [2024-11-08 14:20:26,274 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 120 transitions. Word has length 30 [2024-11-08 14:20:26,275 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:20:26,275 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 120 transitions. [2024-11-08 14:20:26,275 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-08 14:20:26,275 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 120 transitions. [2024-11-08 14:20:26,276 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-08 14:20:26,276 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:20:26,276 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:20:26,291 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-08 14:20:26,480 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,SelfDestructingSolverStorable3 [2024-11-08 14:20:26,481 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:20:26,481 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:20:26,482 INFO L85 PathProgramCache]: Analyzing trace with hash -1015454531, now seen corresponding path program 1 times [2024-11-08 14:20:26,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:20:26,482 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [91009744] [2024-11-08 14:20:26,482 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:26,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:20:26,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:20:26,494 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [459820493] [2024-11-08 14:20:26,494 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:20:26,494 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:20:26,494 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:20:26,495 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-08 14:20:26,497 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-08 14:20:26,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:20:26,564 INFO L255 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-08 14:20:26,565 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:20:26,644 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:20:26,644 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:20:28,252 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-08 14:20:28,252 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:20:28,252 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [91009744] [2024-11-08 14:20:28,253 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:20:28,253 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [459820493] [2024-11-08 14:20:28,253 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [459820493] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-08 14:20:28,253 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-08 14:20:28,253 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2024-11-08 14:20:28,253 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [294688440] [2024-11-08 14:20:28,253 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-08 14:20:28,254 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-08 14:20:28,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:20:28,254 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-08 14:20:28,254 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2024-11-08 14:20:28,255 INFO L87 Difference]: Start difference. First operand 84 states and 120 transitions. Second operand has 10 states, 10 states have (on average 2.7) internal successors, (27), 9 states have internal predecessors, (27), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 14:20:39,991 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:20:42,697 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.30s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:20:46,858 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-08 14:20:50,884 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2024-11-08 14:20:54,897 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:20:56,398 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.49s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:20:57,727 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.11s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:20:59,717 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.96s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:04,629 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:08,634 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:12,639 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:16,658 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:20,663 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:24,680 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:28,695 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:32,795 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:37,004 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.60s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:41,040 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-08 14:21:41,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:21:41,046 INFO L93 Difference]: Finished difference Result 153 states and 223 transitions. [2024-11-08 14:21:41,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-08 14:21:41,047 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.7) internal successors, (27), 9 states have internal predecessors, (27), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 29 [2024-11-08 14:21:41,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:21:41,048 INFO L225 Difference]: With dead ends: 153 [2024-11-08 14:21:41,048 INFO L226 Difference]: Without dead ends: 129 [2024-11-08 14:21:41,049 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 47 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=38, Invalid=93, Unknown=1, NotChecked=0, Total=132 [2024-11-08 14:21:41,049 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 16 mSDsluCounter, 263 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 49 mSolverCounterUnsat, 13 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 64.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 316 SdHoareTripleChecker+Invalid, 253 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 13 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 65.0s IncrementalHoareTripleChecker+Time [2024-11-08 14:21:41,050 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 316 Invalid, 253 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 191 Invalid, 13 Unknown, 0 Unchecked, 65.0s Time] [2024-11-08 14:21:41,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2024-11-08 14:21:41,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 123. [2024-11-08 14:21:41,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 58 states have (on average 1.1896551724137931) internal successors, (69), 61 states have internal predecessors, (69), 55 states have call successors, (55), 9 states have call predecessors, (55), 9 states have return successors, (53), 52 states have call predecessors, (53), 53 states have call successors, (53) [2024-11-08 14:21:41,070 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 177 transitions. [2024-11-08 14:21:41,073 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 177 transitions. Word has length 29 [2024-11-08 14:21:41,073 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:21:41,073 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 177 transitions. [2024-11-08 14:21:41,073 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.7) internal successors, (27), 9 states have internal predecessors, (27), 3 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-08 14:21:41,073 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 177 transitions. [2024-11-08 14:21:41,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-08 14:21:41,074 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:21:41,074 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:21:41,096 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-08 14:21:41,275 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-08 14:21:41,276 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:21:41,276 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:21:41,276 INFO L85 PathProgramCache]: Analyzing trace with hash 142204962, now seen corresponding path program 1 times [2024-11-08 14:21:41,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:21:41,277 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2132799909] [2024-11-08 14:21:41,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:21:41,277 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:21:41,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:21:41,295 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [904207413] [2024-11-08 14:21:41,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:21:41,295 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:21:41,295 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:21:41,297 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-08 14:21:41,297 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-08 14:21:41,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:21:41,337 INFO L255 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-08 14:21:41,339 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:21:41,464 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-08 14:21:41,465 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-08 14:21:41,465 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-08 14:21:41,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2132799909] [2024-11-08 14:21:41,466 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-08 14:21:41,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [904207413] [2024-11-08 14:21:41,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [904207413] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-08 14:21:41,466 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-08 14:21:41,467 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-08 14:21:41,467 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1926783661] [2024-11-08 14:21:41,467 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-08 14:21:41,467 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-08 14:21:41,468 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-08 14:21:41,468 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-08 14:21:41,468 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2024-11-08 14:21:41,469 INFO L87 Difference]: Start difference. First operand 123 states and 177 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:21:42,060 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-08 14:21:42,060 INFO L93 Difference]: Finished difference Result 137 states and 188 transitions. [2024-11-08 14:21:42,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-08 14:21:42,061 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 41 [2024-11-08 14:21:42,061 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-08 14:21:42,063 INFO L225 Difference]: With dead ends: 137 [2024-11-08 14:21:42,063 INFO L226 Difference]: Without dead ends: 135 [2024-11-08 14:21:42,063 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=49, Unknown=0, NotChecked=0, Total=72 [2024-11-08 14:21:42,064 INFO L432 NwaCegarLoop]: 65 mSDtfsCounter, 9 mSDsluCounter, 160 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 125 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-08 14:21:42,064 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 225 Invalid, 125 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-08 14:21:42,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2024-11-08 14:21:42,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 135. [2024-11-08 14:21:42,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 67 states have (on average 1.164179104477612) internal successors, (78), 70 states have internal predecessors, (78), 55 states have call successors, (55), 12 states have call predecessors, (55), 12 states have return successors, (53), 52 states have call predecessors, (53), 53 states have call successors, (53) [2024-11-08 14:21:42,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 186 transitions. [2024-11-08 14:21:42,097 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 186 transitions. Word has length 41 [2024-11-08 14:21:42,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-08 14:21:42,098 INFO L471 AbstractCegarLoop]: Abstraction has 135 states and 186 transitions. [2024-11-08 14:21:42,098 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-08 14:21:42,100 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 186 transitions. [2024-11-08 14:21:42,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-11-08 14:21:42,101 INFO L207 NwaCegarLoop]: Found error trace [2024-11-08 14:21:42,102 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-08 14:21:42,117 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-08 14:21:42,302 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-08 14:21:42,302 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-08 14:21:42,304 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-08 14:21:42,304 INFO L85 PathProgramCache]: Analyzing trace with hash 1168270398, now seen corresponding path program 1 times [2024-11-08 14:21:42,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-08 14:21:42,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [139737333] [2024-11-08 14:21:42,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:21:42,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-08 14:21:42,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-08 14:21:42,340 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1968157114] [2024-11-08 14:21:42,340 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-08 14:21:42,340 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-08 14:21:42,340 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-08 14:21:42,341 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-08 14:21:42,346 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-08 14:21:42,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-08 14:21:42,391 INFO L255 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-08 14:21:42,393 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-08 14:21:42,509 INFO L134 CoverageAnalysis]: Checked inductivity of 102 backedges. 31 proven. 1 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2024-11-08 14:21:42,509 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-08 14:21:50,698 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify)