./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 3061b6dc 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/egcd-ll_unwindbound10.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 0a6d36c45579adaf3871b264b96aba9fa14294bc645c23d191a4e77c149500df --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-18 13:34:15,191 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-18 13:34:15,247 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-18 13:34:15,259 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-18 13:34:15,259 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-18 13:34:15,280 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-18 13:34:15,280 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-18 13:34:15,281 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-18 13:34:15,281 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-18 13:34:15,282 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-18 13:34:15,283 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-18 13:34:15,283 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-18 13:34:15,283 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-18 13:34:15,286 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-18 13:34:15,286 INFO L153 SettingsManager]: * Use SBE=true [2024-11-18 13:34:15,286 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-18 13:34:15,286 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-18 13:34:15,286 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-18 13:34:15,287 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-18 13:34:15,287 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-18 13:34:15,287 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-18 13:34:15,287 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-18 13:34:15,288 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-18 13:34:15,288 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-18 13:34:15,288 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-18 13:34:15,288 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-18 13:34:15,288 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-18 13:34:15,288 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-18 13:34:15,289 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-18 13:34:15,289 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-18 13:34:15,289 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-18 13:34:15,289 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-18 13:34:15,289 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:34:15,289 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-18 13:34:15,290 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-18 13:34:15,290 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-18 13:34:15,290 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-18 13:34:15,290 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-18 13:34:15,290 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-18 13:34:15,290 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-18 13:34:15,290 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-18 13:34:15,291 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-18 13:34:15,292 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 -> 0a6d36c45579adaf3871b264b96aba9fa14294bc645c23d191a4e77c149500df [2024-11-18 13:34:15,492 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-18 13:34:15,513 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-18 13:34:15,517 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-18 13:34:15,518 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-18 13:34:15,518 INFO L274 PluginConnector]: CDTParser initialized [2024-11-18 13:34:15,519 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound10.c [2024-11-18 13:34:16,737 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-18 13:34:16,904 INFO L384 CDTParser]: Found 1 translation units. [2024-11-18 13:34:16,905 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_unwindbound10.c [2024-11-18 13:34:16,910 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a33112f60/fde076d1088e441c8801b5635afa7509/FLAG07a3470f4 [2024-11-18 13:34:17,325 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a33112f60/fde076d1088e441c8801b5635afa7509 [2024-11-18 13:34:17,327 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-18 13:34:17,328 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-18 13:34:17,328 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-18 13:34:17,328 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-18 13:34:17,332 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-18 13:34:17,332 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,333 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1b4c911b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17, skipping insertion in model container [2024-11-18 13:34:17,333 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,351 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-18 13:34:17,484 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/egcd-ll_unwindbound10.c[489,502] [2024-11-18 13:34:17,503 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:34:17,512 INFO L200 MainTranslator]: Completed pre-run [2024-11-18 13:34:17,522 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/egcd-ll_unwindbound10.c[489,502] [2024-11-18 13:34:17,528 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-18 13:34:17,539 INFO L204 MainTranslator]: Completed translation [2024-11-18 13:34:17,540 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17 WrapperNode [2024-11-18 13:34:17,540 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-18 13:34:17,541 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-18 13:34:17,541 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-18 13:34:17,541 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-18 13:34:17,546 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,551 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,563 INFO L138 Inliner]: procedures = 14, calls = 16, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 60 [2024-11-18 13:34:17,564 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-18 13:34:17,564 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-18 13:34:17,564 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-18 13:34:17,564 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-18 13:34:17,572 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,573 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,574 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,583 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-18 13:34:17,583 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,584 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,587 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,588 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,590 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,590 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,594 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-18 13:34:17,595 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-18 13:34:17,595 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-18 13:34:17,595 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-18 13:34:17,595 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (1/1) ... [2024-11-18 13:34:17,599 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-18 13:34:17,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:17,623 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-18 13:34:17,625 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-18 13:34:17,662 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-18 13:34:17,662 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-18 13:34:17,663 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-18 13:34:17,663 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-18 13:34:17,663 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-18 13:34:17,664 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-18 13:34:17,664 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-18 13:34:17,665 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-18 13:34:17,716 INFO L238 CfgBuilder]: Building ICFG [2024-11-18 13:34:17,718 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-18 13:34:17,840 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2024-11-18 13:34:17,840 INFO L287 CfgBuilder]: Performing block encoding [2024-11-18 13:34:17,854 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-18 13:34:17,854 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-18 13:34:17,855 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:34:17 BoogieIcfgContainer [2024-11-18 13:34:17,855 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-18 13:34:17,858 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-18 13:34:17,859 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-18 13:34:17,861 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-18 13:34:17,862 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 18.11 01:34:17" (1/3) ... [2024-11-18 13:34:17,863 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b680af8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:34:17, skipping insertion in model container [2024-11-18 13:34:17,863 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 18.11 01:34:17" (2/3) ... [2024-11-18 13:34:17,863 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6b680af8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.11 01:34:17, skipping insertion in model container [2024-11-18 13:34:17,863 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:34:17" (3/3) ... [2024-11-18 13:34:17,864 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_unwindbound10.c [2024-11-18 13:34:17,877 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-18 13:34:17,878 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-18 13:34:17,932 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-18 13:34:17,938 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;@77729e97, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-18 13:34:17,939 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-18 13:34:17,942 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2024-11-18 13:34:17,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-11-18 13:34:17,948 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:17,948 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:17,949 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:17,953 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:17,953 INFO L85 PathProgramCache]: Analyzing trace with hash 1165920622, now seen corresponding path program 1 times [2024-11-18 13:34:17,959 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:17,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1658716023] [2024-11-18 13:34:17,961 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:17,961 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:18,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:18,062 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-18 13:34:18,063 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:18,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1658716023] [2024-11-18 13:34:18,064 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1658716023] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:34:18,064 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1951664870] [2024-11-18 13:34:18,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:18,064 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:18,065 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:18,066 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-18 13:34:18,070 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-18 13:34:18,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:18,122 INFO L255 TraceCheckSpWp]: Trace formula consists of 67 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-18 13:34:18,125 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:18,135 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-18 13:34:18,135 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:34:18,135 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1951664870] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:18,136 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:34:18,136 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-18 13:34:18,137 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [6648494] [2024-11-18 13:34:18,138 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:18,141 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-18 13:34:18,141 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:18,157 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-18 13:34:18,157 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-18 13:34:18,159 INFO L87 Difference]: Start difference. First operand has 30 states, 17 states have (on average 1.411764705882353) internal successors, (24), 18 states have internal predecessors, (24), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) 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, (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-18 13:34:18,173 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:18,173 INFO L93 Difference]: Finished difference Result 57 states and 89 transitions. [2024-11-18 13:34:18,173 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-18 13:34:18,174 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, (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 18 [2024-11-18 13:34:18,175 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:18,179 INFO L225 Difference]: With dead ends: 57 [2024-11-18 13:34:18,179 INFO L226 Difference]: Without dead ends: 26 [2024-11-18 13:34:18,181 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 19 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-18 13:34:18,183 INFO L432 NwaCegarLoop]: 39 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, 39 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-18 13:34:18,184 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:18,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2024-11-18 13:34:18,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2024-11-18 13:34:18,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 15 states have internal predecessors, (18), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-18 13:34:18,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2024-11-18 13:34:18,208 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 18 [2024-11-18 13:34:18,208 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:18,209 INFO L471 AbstractCegarLoop]: Abstraction has 26 states and 35 transitions. [2024-11-18 13:34:18,209 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, (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-18 13:34:18,209 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 35 transitions. [2024-11-18 13:34:18,210 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-18 13:34:18,210 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:18,210 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:18,224 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-18 13:34:18,412 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2024-11-18 13:34:18,412 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:18,413 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:18,413 INFO L85 PathProgramCache]: Analyzing trace with hash -542319922, now seen corresponding path program 1 times [2024-11-18 13:34:18,413 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:18,413 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2043496422] [2024-11-18 13:34:18,413 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:18,413 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:18,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:18,523 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-18 13:34:18,523 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:18,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2043496422] [2024-11-18 13:34:18,524 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2043496422] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:18,524 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:34:18,524 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-18 13:34:18,524 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1343204820] [2024-11-18 13:34:18,524 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:18,525 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-18 13:34:18,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:18,526 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-18 13:34:18,526 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-18 13:34:18,526 INFO L87 Difference]: Start difference. First operand 26 states and 35 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 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), 1 states have call successors, (2) [2024-11-18 13:34:18,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:18,543 INFO L93 Difference]: Finished difference Result 38 states and 50 transitions. [2024-11-18 13:34:18,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-18 13:34:18,543 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 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), 1 states have call successors, (2) Word has length 19 [2024-11-18 13:34:18,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:18,544 INFO L225 Difference]: With dead ends: 38 [2024-11-18 13:34:18,544 INFO L226 Difference]: Without dead ends: 28 [2024-11-18 13:34:18,545 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-18 13:34:18,546 INFO L432 NwaCegarLoop]: 33 mSDtfsCounter, 5 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 87 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:18,546 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 87 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:18,547 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2024-11-18 13:34:18,551 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 28. [2024-11-18 13:34:18,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 9 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2024-11-18 13:34:18,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 37 transitions. [2024-11-18 13:34:18,552 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 37 transitions. Word has length 19 [2024-11-18 13:34:18,553 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:18,553 INFO L471 AbstractCegarLoop]: Abstraction has 28 states and 37 transitions. [2024-11-18 13:34:18,554 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 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), 1 states have call successors, (2) [2024-11-18 13:34:18,554 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 37 transitions. [2024-11-18 13:34:18,554 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-18 13:34:18,554 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:18,554 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:18,554 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-18 13:34:18,555 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:18,555 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:18,555 INFO L85 PathProgramCache]: Analyzing trace with hash -540651626, now seen corresponding path program 1 times [2024-11-18 13:34:18,555 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:18,555 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [743787003] [2024-11-18 13:34:18,555 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:18,556 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:18,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:34:18,580 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [978221613] [2024-11-18 13:34:18,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:18,580 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:18,580 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:18,582 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-18 13:34:18,582 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-18 13:34:18,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:18,629 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:34:18,630 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:18,730 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-18 13:34:18,730 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:34:18,730 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:18,731 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [743787003] [2024-11-18 13:34:18,734 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:34:18,734 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [978221613] [2024-11-18 13:34:18,734 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [978221613] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:18,734 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:34:18,734 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:34:18,734 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2069824464] [2024-11-18 13:34:18,735 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:18,735 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:34:18,735 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:18,735 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:34:18,735 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:34:18,736 INFO L87 Difference]: Start difference. First operand 28 states and 37 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 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), 1 states have call successors, (2) [2024-11-18 13:34:18,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:18,792 INFO L93 Difference]: Finished difference Result 45 states and 62 transitions. [2024-11-18 13:34:18,793 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:34:18,793 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 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), 1 states have call successors, (2) Word has length 19 [2024-11-18 13:34:18,793 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:18,794 INFO L225 Difference]: With dead ends: 45 [2024-11-18 13:34:18,795 INFO L226 Difference]: Without dead ends: 43 [2024-11-18 13:34:18,796 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 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-18 13:34:18,797 INFO L432 NwaCegarLoop]: 32 mSDtfsCounter, 6 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:18,798 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 118 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:18,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2024-11-18 13:34:18,809 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2024-11-18 13:34:18,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 25 states have internal predecessors, (30), 15 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-18 13:34:18,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 59 transitions. [2024-11-18 13:34:18,814 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 59 transitions. Word has length 19 [2024-11-18 13:34:18,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:18,814 INFO L471 AbstractCegarLoop]: Abstraction has 42 states and 59 transitions. [2024-11-18 13:34:18,814 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 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), 1 states have call successors, (2) [2024-11-18 13:34:18,814 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 59 transitions. [2024-11-18 13:34:18,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-18 13:34:18,815 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:18,815 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:18,831 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-18 13:34:19,015 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-18 13:34:19,016 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:19,016 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:19,016 INFO L85 PathProgramCache]: Analyzing trace with hash -276555716, now seen corresponding path program 1 times [2024-11-18 13:34:19,016 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:19,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1787744443] [2024-11-18 13:34:19,017 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:19,017 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:19,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:34:19,033 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1951691403] [2024-11-18 13:34:19,033 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:19,034 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:19,034 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:19,035 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-18 13:34:19,037 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-18 13:34:19,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:19,077 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-18 13:34:19,082 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:19,140 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-18 13:34:19,140 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:34:19,140 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:19,141 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1787744443] [2024-11-18 13:34:19,141 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:34:19,141 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1951691403] [2024-11-18 13:34:19,141 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1951691403] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:19,141 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:34:19,141 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:34:19,141 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1994584190] [2024-11-18 13:34:19,141 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:19,142 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:34:19,142 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:19,142 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:34:19,142 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:34:19,142 INFO L87 Difference]: Start difference. First operand 42 states and 59 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-18 13:34:19,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:19,202 INFO L93 Difference]: Finished difference Result 49 states and 65 transitions. [2024-11-18 13:34:19,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:34:19,203 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2024-11-18 13:34:19,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:19,204 INFO L225 Difference]: With dead ends: 49 [2024-11-18 13:34:19,206 INFO L226 Difference]: Without dead ends: 47 [2024-11-18 13:34:19,206 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 20 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-18 13:34:19,207 INFO L432 NwaCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:19,207 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 126 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:19,208 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2024-11-18 13:34:19,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2024-11-18 13:34:19,217 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 26 states have (on average 1.2692307692307692) internal successors, (33), 28 states have internal predecessors, (33), 15 states have call successors, (15), 4 states have call predecessors, (15), 4 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-18 13:34:19,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 62 transitions. [2024-11-18 13:34:19,220 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 62 transitions. Word has length 24 [2024-11-18 13:34:19,220 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:19,220 INFO L471 AbstractCegarLoop]: Abstraction has 46 states and 62 transitions. [2024-11-18 13:34:19,220 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-18 13:34:19,220 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 62 transitions. [2024-11-18 13:34:19,221 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-18 13:34:19,221 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:19,221 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-18 13:34:19,235 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-18 13:34:19,421 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:19,422 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:19,422 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:19,423 INFO L85 PathProgramCache]: Analyzing trace with hash -1836785898, now seen corresponding path program 1 times [2024-11-18 13:34:19,423 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:19,423 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1438860028] [2024-11-18 13:34:19,423 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:19,423 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:19,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:34:19,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [21448658] [2024-11-18 13:34:19,449 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:19,449 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:19,449 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:19,451 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-18 13:34:19,452 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-18 13:34:19,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:19,488 INFO L255 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-18 13:34:19,489 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:19,547 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-18 13:34:19,547 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:34:19,548 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:19,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1438860028] [2024-11-18 13:34:19,548 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:34:19,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [21448658] [2024-11-18 13:34:19,548 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [21448658] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:19,548 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:34:19,548 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:34:19,548 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1872943954] [2024-11-18 13:34:19,549 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:19,549 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:34:19,549 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:19,549 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:34:19,550 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:34:19,550 INFO L87 Difference]: Start difference. First operand 46 states and 62 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), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:34:19,594 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:19,594 INFO L93 Difference]: Finished difference Result 71 states and 103 transitions. [2024-11-18 13:34:19,594 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:34:19,594 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), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 29 [2024-11-18 13:34:19,595 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:19,596 INFO L225 Difference]: With dead ends: 71 [2024-11-18 13:34:19,597 INFO L226 Difference]: Without dead ends: 67 [2024-11-18 13:34:19,597 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-18 13:34:19,598 INFO L432 NwaCegarLoop]: 31 mSDtfsCounter, 7 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:19,598 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 111 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:19,598 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-18 13:34:19,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2024-11-18 13:34:19,607 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 35 states have (on average 1.3428571428571427) internal successors, (47), 39 states have internal predecessors, (47), 26 states have call successors, (26), 5 states have call predecessors, (26), 5 states have return successors, (23), 22 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-18 13:34:19,607 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 96 transitions. [2024-11-18 13:34:19,608 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 96 transitions. Word has length 29 [2024-11-18 13:34:19,608 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:19,608 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 96 transitions. [2024-11-18 13:34:19,608 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), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-18 13:34:19,608 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 96 transitions. [2024-11-18 13:34:19,609 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-18 13:34:19,609 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:19,609 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:19,621 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-18 13:34:19,813 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:19,814 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:19,814 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:19,814 INFO L85 PathProgramCache]: Analyzing trace with hash 1071030291, now seen corresponding path program 1 times [2024-11-18 13:34:19,814 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:19,814 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1846009314] [2024-11-18 13:34:19,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:19,814 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:19,828 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:19,938 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-18 13:34:19,938 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:19,938 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1846009314] [2024-11-18 13:34:19,938 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1846009314] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:19,938 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:34:19,939 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:34:19,939 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [347510100] [2024-11-18 13:34:19,939 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:19,939 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:34:19,939 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:19,940 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:34:19,940 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:34:19,940 INFO L87 Difference]: Start difference. First operand 67 states and 96 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-18 13:34:19,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:19,982 INFO L93 Difference]: Finished difference Result 83 states and 119 transitions. [2024-11-18 13:34:19,982 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:34:19,983 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 35 [2024-11-18 13:34:19,983 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:19,984 INFO L225 Difference]: With dead ends: 83 [2024-11-18 13:34:19,984 INFO L226 Difference]: Without dead ends: 81 [2024-11-18 13:34:19,984 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 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-18 13:34:19,985 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 3 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:19,985 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 135 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:19,985 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-11-18 13:34:19,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 74. [2024-11-18 13:34:19,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 38 states have (on average 1.3157894736842106) internal successors, (50), 45 states have internal predecessors, (50), 29 states have call successors, (29), 6 states have call predecessors, (29), 6 states have return successors, (26), 22 states have call predecessors, (26), 26 states have call successors, (26) [2024-11-18 13:34:20,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 105 transitions. [2024-11-18 13:34:20,001 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 105 transitions. Word has length 35 [2024-11-18 13:34:20,002 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:20,002 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 105 transitions. [2024-11-18 13:34:20,002 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-11-18 13:34:20,003 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 105 transitions. [2024-11-18 13:34:20,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-18 13:34:20,003 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:20,003 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:20,004 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-18 13:34:20,004 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:20,004 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:20,004 INFO L85 PathProgramCache]: Analyzing trace with hash 1689492770, now seen corresponding path program 1 times [2024-11-18 13:34:20,004 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:20,004 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1011723592] [2024-11-18 13:34:20,004 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:20,004 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:20,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:20,090 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-18 13:34:20,090 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:20,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1011723592] [2024-11-18 13:34:20,090 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1011723592] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:34:20,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [801880676] [2024-11-18 13:34:20,091 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:20,091 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:20,091 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:20,092 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-18 13:34:20,093 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-18 13:34:20,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:20,134 INFO L255 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-18 13:34:20,136 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:20,189 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-18 13:34:20,189 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:34:20,268 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-18 13:34:20,269 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [801880676] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:34:20,269 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:34:20,269 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4, 5] total 8 [2024-11-18 13:34:20,269 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [534206066] [2024-11-18 13:34:20,269 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:34:20,270 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-18 13:34:20,270 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:20,270 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-18 13:34:20,271 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2024-11-18 13:34:20,271 INFO L87 Difference]: Start difference. First operand 74 states and 105 transitions. Second operand has 8 states, 8 states have (on average 4.125) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-18 13:34:20,397 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:20,397 INFO L93 Difference]: Finished difference Result 218 states and 286 transitions. [2024-11-18 13:34:20,398 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-18 13:34:20,398 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.125) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) Word has length 38 [2024-11-18 13:34:20,398 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:20,401 INFO L225 Difference]: With dead ends: 218 [2024-11-18 13:34:20,402 INFO L226 Difference]: Without dead ends: 196 [2024-11-18 13:34:20,403 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2024-11-18 13:34:20,404 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 49 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:20,404 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 152 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:34:20,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 196 states. [2024-11-18 13:34:20,430 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 196 to 190. [2024-11-18 13:34:20,433 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 108 states have (on average 1.2222222222222223) internal successors, (132), 119 states have internal predecessors, (132), 61 states have call successors, (61), 21 states have call predecessors, (61), 20 states have return successors, (54), 49 states have call predecessors, (54), 54 states have call successors, (54) [2024-11-18 13:34:20,434 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 247 transitions. [2024-11-18 13:34:20,436 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 247 transitions. Word has length 38 [2024-11-18 13:34:20,436 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:20,436 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 247 transitions. [2024-11-18 13:34:20,437 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.125) internal successors, (33), 8 states have internal predecessors, (33), 5 states have call successors, (16), 4 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-18 13:34:20,437 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 247 transitions. [2024-11-18 13:34:20,438 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-18 13:34:20,438 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:20,441 INFO L215 NwaCegarLoop]: trace histogram [4, 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-18 13:34:20,453 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-18 13:34:20,641 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-18 13:34:20,642 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:20,642 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:20,642 INFO L85 PathProgramCache]: Analyzing trace with hash 1691161066, now seen corresponding path program 1 times [2024-11-18 13:34:20,642 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:20,643 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1552854277] [2024-11-18 13:34:20,643 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:20,643 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:20,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:34:20,656 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [385110007] [2024-11-18 13:34:20,656 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:20,656 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:20,656 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:20,658 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-18 13:34:20,659 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-18 13:34:20,707 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:20,708 INFO L255 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:34:20,709 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:20,776 INFO L134 CoverageAnalysis]: Checked inductivity of 25 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-18 13:34:20,777 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:34:20,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:20,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1552854277] [2024-11-18 13:34:20,777 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:34:20,777 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [385110007] [2024-11-18 13:34:20,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [385110007] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:20,777 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-18 13:34:20,778 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-18 13:34:20,778 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [808269950] [2024-11-18 13:34:20,778 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:20,778 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-18 13:34:20,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:20,779 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-18 13:34:20,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-18 13:34:20,779 INFO L87 Difference]: Start difference. First operand 190 states and 247 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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-18 13:34:20,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:20,816 INFO L93 Difference]: Finished difference Result 204 states and 260 transitions. [2024-11-18 13:34:20,817 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-18 13:34:20,817 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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 38 [2024-11-18 13:34:20,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:20,818 INFO L225 Difference]: With dead ends: 204 [2024-11-18 13:34:20,818 INFO L226 Difference]: Without dead ends: 199 [2024-11-18 13:34:20,819 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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-18 13:34:20,819 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 5 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:20,819 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 112 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:20,820 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 199 states. [2024-11-18 13:34:20,845 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 199 to 199. [2024-11-18 13:34:20,847 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 199 states, 117 states have (on average 1.205128205128205) internal successors, (141), 128 states have internal predecessors, (141), 58 states have call successors, (58), 24 states have call predecessors, (58), 23 states have return successors, (51), 46 states have call predecessors, (51), 51 states have call successors, (51) [2024-11-18 13:34:20,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 250 transitions. [2024-11-18 13:34:20,849 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 250 transitions. Word has length 38 [2024-11-18 13:34:20,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:20,849 INFO L471 AbstractCegarLoop]: Abstraction has 199 states and 250 transitions. [2024-11-18 13:34:20,849 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 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-18 13:34:20,849 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 250 transitions. [2024-11-18 13:34:20,850 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-18 13:34:20,850 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:20,850 INFO L215 NwaCegarLoop]: trace histogram [5, 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-18 13:34:20,862 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-18 13:34:21,054 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:21,055 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:21,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:21,056 INFO L85 PathProgramCache]: Analyzing trace with hash 1925895455, now seen corresponding path program 1 times [2024-11-18 13:34:21,057 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:21,057 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [34618362] [2024-11-18 13:34:21,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:21,057 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:21,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:21,238 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-18 13:34:21,238 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:21,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [34618362] [2024-11-18 13:34:21,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [34618362] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:34:21,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1257960870] [2024-11-18 13:34:21,239 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:21,239 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:21,239 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:21,240 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:34:21,241 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-18 13:34:21,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:21,283 INFO L255 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:34:21,284 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:21,389 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-18 13:34:21,390 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-18 13:34:21,390 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1257960870] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-18 13:34:21,390 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-18 13:34:21,390 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [8] total 12 [2024-11-18 13:34:21,390 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [535740484] [2024-11-18 13:34:21,390 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-18 13:34:21,391 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-18 13:34:21,391 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:21,391 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-18 13:34:21,391 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-18 13:34:21,392 INFO L87 Difference]: Start difference. First operand 199 states and 250 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-18 13:34:21,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:21,466 INFO L93 Difference]: Finished difference Result 230 states and 279 transitions. [2024-11-18 13:34:21,467 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-18 13:34:21,467 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 40 [2024-11-18 13:34:21,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:21,469 INFO L225 Difference]: With dead ends: 230 [2024-11-18 13:34:21,470 INFO L226 Difference]: Without dead ends: 220 [2024-11-18 13:34:21,470 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:34:21,471 INFO L432 NwaCegarLoop]: 30 mSDtfsCounter, 7 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:21,472 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 136 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-18 13:34:21,472 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states. [2024-11-18 13:34:21,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 216. [2024-11-18 13:34:21,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 130 states have (on average 1.176923076923077) internal successors, (153), 141 states have internal predecessors, (153), 57 states have call successors, (57), 28 states have call predecessors, (57), 28 states have return successors, (51), 46 states have call predecessors, (51), 51 states have call successors, (51) [2024-11-18 13:34:21,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 261 transitions. [2024-11-18 13:34:21,491 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 261 transitions. Word has length 40 [2024-11-18 13:34:21,491 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:21,491 INFO L471 AbstractCegarLoop]: Abstraction has 216 states and 261 transitions. [2024-11-18 13:34:21,491 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-11-18 13:34:21,491 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 261 transitions. [2024-11-18 13:34:21,492 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2024-11-18 13:34:21,492 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:21,492 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:21,505 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-18 13:34:21,692 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:21,693 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:21,693 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:21,693 INFO L85 PathProgramCache]: Analyzing trace with hash 968731240, now seen corresponding path program 2 times [2024-11-18 13:34:21,693 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:21,694 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1883384008] [2024-11-18 13:34:21,694 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:34:21,694 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:21,713 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:34:21,713 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:34:21,713 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1470945885] [2024-11-18 13:34:21,713 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:34:21,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:21,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:21,716 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:34:21,719 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-18 13:34:21,755 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:34:21,755 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:34:21,756 INFO L255 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-18 13:34:21,758 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:21,997 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 19 proven. 5 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-18 13:34:21,998 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:34:22,460 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-18 13:34:22,460 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:22,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1883384008] [2024-11-18 13:34:22,461 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:34:22,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1470945885] [2024-11-18 13:34:22,461 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1470945885] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:34:22,461 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:34:22,461 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 17 [2024-11-18 13:34:22,461 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [905278262] [2024-11-18 13:34:22,461 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:34:22,464 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-18 13:34:22,464 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:22,465 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-18 13:34:22,465 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:34:22,465 INFO L87 Difference]: Start difference. First operand 216 states and 261 transitions. Second operand has 17 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-18 13:34:23,086 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:23,087 INFO L93 Difference]: Finished difference Result 266 states and 335 transitions. [2024-11-18 13:34:23,087 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-18 13:34:23,087 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) Word has length 43 [2024-11-18 13:34:23,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:23,089 INFO L225 Difference]: With dead ends: 266 [2024-11-18 13:34:23,089 INFO L226 Difference]: Without dead ends: 264 [2024-11-18 13:34:23,090 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 68 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=101, Invalid=405, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:34:23,090 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 47 mSDsluCounter, 224 mSDsCounter, 0 mSdLazyCounter, 269 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 251 SdHoareTripleChecker+Invalid, 331 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 269 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:23,090 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 251 Invalid, 331 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 269 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 13:34:23,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2024-11-18 13:34:23,118 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 228. [2024-11-18 13:34:23,119 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 228 states, 139 states have (on average 1.1654676258992807) internal successors, (162), 150 states have internal predecessors, (162), 57 states have call successors, (57), 31 states have call predecessors, (57), 31 states have return successors, (51), 46 states have call predecessors, (51), 51 states have call successors, (51) [2024-11-18 13:34:23,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 228 states to 228 states and 270 transitions. [2024-11-18 13:34:23,120 INFO L78 Accepts]: Start accepts. Automaton has 228 states and 270 transitions. Word has length 43 [2024-11-18 13:34:23,120 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:23,120 INFO L471 AbstractCegarLoop]: Abstraction has 228 states and 270 transitions. [2024-11-18 13:34:23,121 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (12), 3 states have call predecessors, (12), 3 states have return successors, (11), 6 states have call predecessors, (11), 5 states have call successors, (11) [2024-11-18 13:34:23,121 INFO L276 IsEmpty]: Start isEmpty. Operand 228 states and 270 transitions. [2024-11-18 13:34:23,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-18 13:34:23,121 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:23,121 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:23,134 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-18 13:34:23,325 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-18 13:34:23,326 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:23,326 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:23,326 INFO L85 PathProgramCache]: Analyzing trace with hash -740326292, now seen corresponding path program 1 times [2024-11-18 13:34:23,326 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:23,327 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [13333224] [2024-11-18 13:34:23,327 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:23,327 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:23,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:34:23,336 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1549754948] [2024-11-18 13:34:23,336 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:23,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:23,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:23,338 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:34:23,338 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-18 13:34:23,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:23,374 INFO L255 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-18 13:34:23,375 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:23,610 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 9 proven. 21 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-18 13:34:23,610 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:34:23,844 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 9 proven. 18 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-18 13:34:23,845 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:23,845 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [13333224] [2024-11-18 13:34:23,845 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:34:23,845 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1549754948] [2024-11-18 13:34:23,845 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1549754948] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:34:23,845 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:34:23,845 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 17 [2024-11-18 13:34:23,845 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [38869907] [2024-11-18 13:34:23,846 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:34:23,846 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-18 13:34:23,846 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:23,846 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-18 13:34:23,847 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=221, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:34:23,847 INFO L87 Difference]: Start difference. First operand 228 states and 270 transitions. Second operand has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 6 states have call predecessors, (14), 7 states have call successors, (14) [2024-11-18 13:34:24,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:24,394 INFO L93 Difference]: Finished difference Result 277 states and 342 transitions. [2024-11-18 13:34:24,395 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-18 13:34:24,395 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 6 states have call predecessors, (14), 7 states have call successors, (14) Word has length 48 [2024-11-18 13:34:24,395 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:24,396 INFO L225 Difference]: With dead ends: 277 [2024-11-18 13:34:24,396 INFO L226 Difference]: Without dead ends: 235 [2024-11-18 13:34:24,397 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 77 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=106, Invalid=400, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:34:24,397 INFO L432 NwaCegarLoop]: 27 mSDtfsCounter, 27 mSDsluCounter, 242 mSDsCounter, 0 mSdLazyCounter, 285 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 333 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 285 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:24,397 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 269 Invalid, 333 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 285 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-18 13:34:24,398 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2024-11-18 13:34:24,428 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 200. [2024-11-18 13:34:24,429 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 200 states, 129 states have (on average 1.1472868217054264) internal successors, (148), 135 states have internal predecessors, (148), 43 states have call successors, (43), 28 states have call predecessors, (43), 27 states have return successors, (38), 36 states have call predecessors, (38), 38 states have call successors, (38) [2024-11-18 13:34:24,430 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 200 states to 200 states and 229 transitions. [2024-11-18 13:34:24,430 INFO L78 Accepts]: Start accepts. Automaton has 200 states and 229 transitions. Word has length 48 [2024-11-18 13:34:24,430 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:24,430 INFO L471 AbstractCegarLoop]: Abstraction has 200 states and 229 transitions. [2024-11-18 13:34:24,430 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.9411764705882353) internal successors, (33), 14 states have internal predecessors, (33), 7 states have call successors, (15), 2 states have call predecessors, (15), 3 states have return successors, (14), 6 states have call predecessors, (14), 7 states have call successors, (14) [2024-11-18 13:34:24,431 INFO L276 IsEmpty]: Start isEmpty. Operand 200 states and 229 transitions. [2024-11-18 13:34:24,433 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-18 13:34:24,433 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:24,433 INFO L215 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:24,449 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-18 13:34:24,637 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:24,638 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:24,638 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:24,638 INFO L85 PathProgramCache]: Analyzing trace with hash -715006568, now seen corresponding path program 1 times [2024-11-18 13:34:24,638 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:24,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [29334901] [2024-11-18 13:34:24,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:24,638 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:24,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-18 13:34:24,653 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1004593184] [2024-11-18 13:34:24,653 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:24,653 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:24,653 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:24,654 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:34:24,655 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-18 13:34:24,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:24,697 INFO L255 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-18 13:34:24,699 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:24,867 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 12 proven. 16 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2024-11-18 13:34:24,868 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:34:25,049 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 18 proven. 7 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-11-18 13:34:25,049 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:25,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [29334901] [2024-11-18 13:34:25,049 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-18 13:34:25,049 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1004593184] [2024-11-18 13:34:25,050 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1004593184] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:34:25,050 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-18 13:34:25,050 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2024-11-18 13:34:25,050 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1196204038] [2024-11-18 13:34:25,050 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-18 13:34:25,050 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-18 13:34:25,050 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:25,051 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-18 13:34:25,051 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2024-11-18 13:34:25,051 INFO L87 Difference]: Start difference. First operand 200 states and 229 transitions. Second operand has 17 states, 17 states have (on average 2.235294117647059) internal successors, (38), 14 states have internal predecessors, (38), 8 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-18 13:34:25,310 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:25,311 INFO L93 Difference]: Finished difference Result 220 states and 255 transitions. [2024-11-18 13:34:25,311 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-18 13:34:25,311 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.235294117647059) internal successors, (38), 14 states have internal predecessors, (38), 8 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 57 [2024-11-18 13:34:25,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:25,312 INFO L225 Difference]: With dead ends: 220 [2024-11-18 13:34:25,312 INFO L226 Difference]: Without dead ends: 213 [2024-11-18 13:34:25,313 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 97 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=105, Invalid=401, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:34:25,313 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 30 mSDsluCounter, 369 mSDsCounter, 0 mSdLazyCounter, 234 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 411 SdHoareTripleChecker+Invalid, 270 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 234 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:25,313 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 411 Invalid, 270 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 234 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-18 13:34:25,314 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2024-11-18 13:34:25,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 191. [2024-11-18 13:34:25,337 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 129 states have (on average 1.1395348837209303) internal successors, (147), 131 states have internal predecessors, (147), 34 states have call successors, (34), 28 states have call predecessors, (34), 27 states have return successors, (32), 31 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-18 13:34:25,338 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 213 transitions. [2024-11-18 13:34:25,338 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 213 transitions. Word has length 57 [2024-11-18 13:34:25,339 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:25,339 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 213 transitions. [2024-11-18 13:34:25,339 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.235294117647059) internal successors, (38), 14 states have internal predecessors, (38), 8 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-18 13:34:25,339 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 213 transitions. [2024-11-18 13:34:25,340 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-11-18 13:34:25,340 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:25,340 INFO L215 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:25,353 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-18 13:34:25,540 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-11-18 13:34:25,541 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:25,541 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:25,541 INFO L85 PathProgramCache]: Analyzing trace with hash -388853941, now seen corresponding path program 1 times [2024-11-18 13:34:25,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:25,541 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1353917717] [2024-11-18 13:34:25,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:25,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:25,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:25,656 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-11-18 13:34:25,656 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:25,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1353917717] [2024-11-18 13:34:25,656 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1353917717] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:34:25,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [682610369] [2024-11-18 13:34:25,656 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-18 13:34:25,656 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:25,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:25,657 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:34:25,658 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-18 13:34:25,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-18 13:34:25,694 INFO L255 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-18 13:34:25,695 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:25,743 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 41 proven. 5 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2024-11-18 13:34:25,743 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:34:25,811 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 41 proven. 5 refuted. 0 times theorem prover too weak. 62 trivial. 0 not checked. [2024-11-18 13:34:25,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [682610369] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:34:25,811 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:34:25,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9, 8] total 13 [2024-11-18 13:34:25,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [213303342] [2024-11-18 13:34:25,811 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:34:25,811 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-18 13:34:25,812 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:25,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-18 13:34:25,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2024-11-18 13:34:25,812 INFO L87 Difference]: Start difference. First operand 191 states and 213 transitions. Second operand has 13 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-18 13:34:25,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:25,951 INFO L93 Difference]: Finished difference Result 217 states and 242 transitions. [2024-11-18 13:34:25,951 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-18 13:34:25,951 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) Word has length 59 [2024-11-18 13:34:25,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:25,952 INFO L225 Difference]: With dead ends: 217 [2024-11-18 13:34:25,953 INFO L226 Difference]: Without dead ends: 197 [2024-11-18 13:34:25,953 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 114 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2024-11-18 13:34:25,953 INFO L432 NwaCegarLoop]: 23 mSDtfsCounter, 8 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:25,954 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 156 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:34:25,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 197 states. [2024-11-18 13:34:25,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 197 to 98. [2024-11-18 13:34:25,967 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 66 states have (on average 1.106060606060606) internal successors, (73), 68 states have internal predecessors, (73), 17 states have call successors, (17), 14 states have call predecessors, (17), 14 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2024-11-18 13:34:25,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 105 transitions. [2024-11-18 13:34:25,967 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 105 transitions. Word has length 59 [2024-11-18 13:34:25,968 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:25,968 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 105 transitions. [2024-11-18 13:34:25,968 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 10 states have (on average 2.6) internal successors, (26), 10 states have internal predecessors, (26), 6 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (12), 4 states have call predecessors, (12), 6 states have call successors, (12) [2024-11-18 13:34:25,968 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 105 transitions. [2024-11-18 13:34:25,968 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 96 [2024-11-18 13:34:25,969 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:25,969 INFO L215 NwaCegarLoop]: trace histogram [13, 12, 12, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:25,981 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-18 13:34:26,169 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-18 13:34:26,169 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:26,170 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:26,170 INFO L85 PathProgramCache]: Analyzing trace with hash 985491918, now seen corresponding path program 2 times [2024-11-18 13:34:26,170 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:26,170 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1395136356] [2024-11-18 13:34:26,170 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:34:26,170 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:26,180 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:34:26,180 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:34:26,316 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 24 proven. 50 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2024-11-18 13:34:26,316 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-18 13:34:26,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1395136356] [2024-11-18 13:34:26,317 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1395136356] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-18 13:34:26,317 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1008786270] [2024-11-18 13:34:26,317 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-18 13:34:26,317 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:26,317 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:26,319 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:34:26,320 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-18 13:34:26,366 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-18 13:34:26,366 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-18 13:34:26,367 INFO L255 TraceCheckSpWp]: Trace formula consists of 231 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-18 13:34:26,369 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-18 13:34:26,445 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 24 proven. 266 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-18 13:34:26,445 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-18 13:34:26,558 INFO L134 CoverageAnalysis]: Checked inductivity of 342 backedges. 24 proven. 50 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2024-11-18 13:34:26,558 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1008786270] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-18 13:34:26,558 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-18 13:34:26,558 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 15 [2024-11-18 13:34:26,558 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [304415194] [2024-11-18 13:34:26,558 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-18 13:34:26,559 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-18 13:34:26,559 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-18 13:34:26,559 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-18 13:34:26,559 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=129, Unknown=0, NotChecked=0, Total=210 [2024-11-18 13:34:26,560 INFO L87 Difference]: Start difference. First operand 98 states and 105 transitions. Second operand has 15 states, 15 states have (on average 4.533333333333333) internal successors, (68), 15 states have internal predecessors, (68), 11 states have call successors, (43), 7 states have call predecessors, (43), 6 states have return successors, (42), 10 states have call predecessors, (42), 10 states have call successors, (42) [2024-11-18 13:34:26,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-18 13:34:26,742 INFO L93 Difference]: Finished difference Result 233 states and 258 transitions. [2024-11-18 13:34:26,742 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-18 13:34:26,742 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 4.533333333333333) internal successors, (68), 15 states have internal predecessors, (68), 11 states have call successors, (43), 7 states have call predecessors, (43), 6 states have return successors, (42), 10 states have call predecessors, (42), 10 states have call successors, (42) Word has length 95 [2024-11-18 13:34:26,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-18 13:34:26,743 INFO L225 Difference]: With dead ends: 233 [2024-11-18 13:34:26,743 INFO L226 Difference]: Without dead ends: 224 [2024-11-18 13:34:26,744 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 184 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2024-11-18 13:34:26,744 INFO L432 NwaCegarLoop]: 28 mSDtfsCounter, 69 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 84 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 158 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 84 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-18 13:34:26,745 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 158 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 84 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-18 13:34:26,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 224 states. [2024-11-18 13:34:26,778 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 224 to 212. [2024-11-18 13:34:26,779 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 212 states, 144 states have (on average 1.0902777777777777) internal successors, (157), 146 states have internal predecessors, (157), 35 states have call successors, (35), 32 states have call predecessors, (35), 32 states have return successors, (33), 33 states have call predecessors, (33), 33 states have call successors, (33) [2024-11-18 13:34:26,779 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 212 states to 212 states and 225 transitions. [2024-11-18 13:34:26,779 INFO L78 Accepts]: Start accepts. Automaton has 212 states and 225 transitions. Word has length 95 [2024-11-18 13:34:26,780 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-18 13:34:26,780 INFO L471 AbstractCegarLoop]: Abstraction has 212 states and 225 transitions. [2024-11-18 13:34:26,780 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 4.533333333333333) internal successors, (68), 15 states have internal predecessors, (68), 11 states have call successors, (43), 7 states have call predecessors, (43), 6 states have return successors, (42), 10 states have call predecessors, (42), 10 states have call successors, (42) [2024-11-18 13:34:26,780 INFO L276 IsEmpty]: Start isEmpty. Operand 212 states and 225 transitions. [2024-11-18 13:34:26,781 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 210 [2024-11-18 13:34:26,783 INFO L207 NwaCegarLoop]: Found error trace [2024-11-18 13:34:26,783 INFO L215 NwaCegarLoop]: trace histogram [31, 30, 30, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:26,795 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-18 13:34:26,983 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-11-18 13:34:26,984 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-18 13:34:26,984 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-18 13:34:26,984 INFO L85 PathProgramCache]: Analyzing trace with hash 325062734, now seen corresponding path program 3 times [2024-11-18 13:34:26,984 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-18 13:34:26,984 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1401080978] [2024-11-18 13:34:26,984 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:34:26,984 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-18 13:34:27,073 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) [2024-11-18 13:34:27,073 INFO L228 tOrderPrioritization]: Conjunction of SSA is unknown [2024-11-18 13:34:27,075 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [200536683] [2024-11-18 13:34:27,075 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-18 13:34:27,075 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-18 13:34:27,075 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-18 13:34:27,076 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-18 13:34:27,077 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-18 13:34:27,172 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 22 check-sat command(s) [2024-11-18 13:34:27,172 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-18 13:34:27,173 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-18 13:34:27,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-18 13:34:27,257 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-18 13:34:27,257 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-18 13:34:27,258 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-18 13:34:27,272 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-18 13:34:27,459 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-11-18 13:34:27,462 INFO L407 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-18 13:34:27,513 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-18 13:34:27,514 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.11 01:34:27 BoogieIcfgContainer [2024-11-18 13:34:27,514 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-18 13:34:27,515 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-18 13:34:27,515 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-18 13:34:27,515 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-18 13:34:27,515 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.11 01:34:17" (3/4) ... [2024-11-18 13:34:27,516 INFO L136 WitnessPrinter]: Generating witness for reachability counterexample [2024-11-18 13:34:27,573 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/witness.graphml [2024-11-18 13:34:27,573 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-18 13:34:27,574 INFO L158 Benchmark]: Toolchain (without parser) took 10246.30ms. Allocated memory was 153.1MB in the beginning and 197.1MB in the end (delta: 44.0MB). Free memory was 103.0MB in the beginning and 80.2MB in the end (delta: 22.8MB). Peak memory consumption was 69.9MB. Max. memory is 16.1GB. [2024-11-18 13:34:27,574 INFO L158 Benchmark]: CDTParser took 0.14ms. Allocated memory is still 153.1MB. Free memory is still 117.7MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-18 13:34:27,574 INFO L158 Benchmark]: CACSL2BoogieTranslator took 211.83ms. Allocated memory is still 153.1MB. Free memory was 102.3MB in the beginning and 89.1MB in the end (delta: 13.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-18 13:34:27,574 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.19ms. Allocated memory is still 153.1MB. Free memory was 89.1MB in the beginning and 87.7MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 13:34:27,575 INFO L158 Benchmark]: Boogie Preprocessor took 29.83ms. Allocated memory is still 153.1MB. Free memory was 87.0MB in the beginning and 85.6MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-18 13:34:27,575 INFO L158 Benchmark]: RCFGBuilder took 260.12ms. Allocated memory is still 153.1MB. Free memory was 85.6MB in the beginning and 73.8MB in the end (delta: 11.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-18 13:34:27,575 INFO L158 Benchmark]: TraceAbstraction took 9656.14ms. Allocated memory was 153.1MB in the beginning and 197.1MB in the end (delta: 44.0MB). Free memory was 73.0MB in the beginning and 88.6MB in the end (delta: -15.6MB). Peak memory consumption was 30.1MB. Max. memory is 16.1GB. [2024-11-18 13:34:27,575 INFO L158 Benchmark]: Witness Printer took 58.66ms. Allocated memory is still 197.1MB. Free memory was 88.6MB in the beginning and 80.2MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-18 13:34:27,576 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.14ms. Allocated memory is still 153.1MB. Free memory is still 117.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 211.83ms. Allocated memory is still 153.1MB. Free memory was 102.3MB in the beginning and 89.1MB in the end (delta: 13.3MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.19ms. Allocated memory is still 153.1MB. Free memory was 89.1MB in the beginning and 87.7MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 29.83ms. Allocated memory is still 153.1MB. Free memory was 87.0MB in the beginning and 85.6MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 260.12ms. Allocated memory is still 153.1MB. Free memory was 85.6MB in the beginning and 73.8MB in the end (delta: 11.8MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 9656.14ms. Allocated memory was 153.1MB in the beginning and 197.1MB in the end (delta: 44.0MB). Free memory was 73.0MB in the beginning and 88.6MB in the end (delta: -15.6MB). Peak memory consumption was 30.1MB. Max. memory is 16.1GB. * Witness Printer took 58.66ms. Allocated memory is still 197.1MB. Free memory was 88.6MB in the beginning and 80.2MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 13]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L18] int counter = 0; VAL [counter=0] [L20] long long a, b, p, q, r, s; [L21] int x, y; [L22] x = __VERIFIER_nondet_int() [L23] y = __VERIFIER_nondet_int() [L24] CALL assume_abort_if_not(x >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L24] RET assume_abort_if_not(x >= 1) VAL [counter=0, x=12, y=1] [L25] CALL assume_abort_if_not(y >= 1) VAL [\old(cond)=1, counter=0] [L8] COND FALSE !(!cond) VAL [\old(cond)=1, counter=0] [L25] RET assume_abort_if_not(y >= 1) VAL [counter=0, x=12, y=1] [L27] a = x [L28] b = y [L29] p = 1 [L30] q = 0 [L31] r = 0 [L32] s = 1 VAL [a=12, b=1, counter=0, p=1, q=0, r=0, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=12, b=1, counter=1, p=1, q=0, r=0, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=1] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=12, b=1, counter=1, p=1, q=0, r=0, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=1] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=12, b=1, counter=1, p=1, q=0, r=0, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=1] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=1] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=12, b=1, counter=1, p=1, q=0, r=0, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=12, b=1, counter=1, p=1, q=0, r=0, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=11, b=1, counter=1, p=1, q=0, r=-1, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=11, b=1, counter=2, p=1, q=0, r=-1, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=11, b=1, counter=2, p=1, q=0, r=-1, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=11, b=1, counter=2, p=1, q=0, r=-1, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=2] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=2] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=11, b=1, counter=2, p=1, q=0, r=-1, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=11, b=1, counter=2, p=1, q=0, r=-1, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=10, b=1, counter=2, p=1, q=0, r=-2, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=10, b=1, counter=3, p=1, q=0, r=-2, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=3] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=10, b=1, counter=3, p=1, q=0, r=-2, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=3] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=10, b=1, counter=3, p=1, q=0, r=-2, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=3] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=3] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=10, b=1, counter=3, p=1, q=0, r=-2, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=10, b=1, counter=3, p=1, q=0, r=-2, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=9, b=1, counter=3, p=1, q=0, r=-3, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=9, b=1, counter=4, p=1, q=0, r=-3, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=9, b=1, counter=4, p=1, q=0, r=-3, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=9, b=1, counter=4, p=1, q=0, r=-3, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=4] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=4] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=9, b=1, counter=4, p=1, q=0, r=-3, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=9, b=1, counter=4, p=1, q=0, r=-3, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=8, b=1, counter=4, p=1, q=0, r=-4, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=8, b=1, counter=5, p=1, q=0, r=-4, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=8, b=1, counter=5, p=1, q=0, r=-4, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=8, b=1, counter=5, p=1, q=0, r=-4, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=5] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=5] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=8, b=1, counter=5, p=1, q=0, r=-4, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=8, b=1, counter=5, p=1, q=0, r=-4, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=7, b=1, counter=5, p=1, q=0, r=-5, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=7, b=1, counter=6, p=1, q=0, r=-5, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=6] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=6] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=7, b=1, counter=6, p=1, q=0, r=-5, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=6] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=6] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=7, b=1, counter=6, p=1, q=0, r=-5, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=6] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=6] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=7, b=1, counter=6, p=1, q=0, r=-5, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=7, b=1, counter=6, p=1, q=0, r=-5, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=6, b=1, counter=6, p=1, q=0, r=-6, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=6, b=1, counter=7, p=1, q=0, r=-6, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=7] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=7] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=6, b=1, counter=7, p=1, q=0, r=-6, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=7] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=7] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=6, b=1, counter=7, p=1, q=0, r=-6, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=7] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=7] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=6, b=1, counter=7, p=1, q=0, r=-6, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=6, b=1, counter=7, p=1, q=0, r=-6, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=5, b=1, counter=7, p=1, q=0, r=-7, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=5, b=1, counter=8, p=1, q=0, r=-7, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=8] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=8] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=5, b=1, counter=8, p=1, q=0, r=-7, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=8] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=8] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=5, b=1, counter=8, p=1, q=0, r=-7, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=8] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=8] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=5, b=1, counter=8, p=1, q=0, r=-7, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=5, b=1, counter=8, p=1, q=0, r=-7, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=4, b=1, counter=8, p=1, q=0, r=-8, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=4, b=1, counter=9, p=1, q=0, r=-8, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=9] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=9] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=4, b=1, counter=9, p=1, q=0, r=-8, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=9] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=9] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=4, b=1, counter=9, p=1, q=0, r=-8, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=9] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=9] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=4, b=1, counter=9, p=1, q=0, r=-8, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=4, b=1, counter=9, p=1, q=0, r=-8, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=3, b=1, counter=9, p=1, q=0, r=-9, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=3, b=1, counter=10, p=1, q=0, r=-9, s=1, x=12, y=1] [L34] COND TRUE counter++<10 [L35] CALL __VERIFIER_assert(1 == p * s - r * q) VAL [\old(cond)=1, counter=10] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=10] [L35] RET __VERIFIER_assert(1 == p * s - r * q) VAL [a=3, b=1, counter=10, p=1, q=0, r=-9, s=1, x=12, y=1] [L36] CALL __VERIFIER_assert(a == y * r + x * p) VAL [\old(cond)=1, counter=10] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=10] [L36] RET __VERIFIER_assert(a == y * r + x * p) VAL [a=3, b=1, counter=10, p=1, q=0, r=-9, s=1, x=12, y=1] [L37] CALL __VERIFIER_assert(b == x * q + y * s) VAL [\old(cond)=1, counter=10] [L11] COND FALSE !(!(cond)) VAL [\old(cond)=1, counter=10] [L37] RET __VERIFIER_assert(b == x * q + y * s) VAL [a=3, b=1, counter=10, p=1, q=0, r=-9, s=1, x=12, y=1] [L39] COND FALSE !(!(a != b)) VAL [a=3, b=1, counter=10, p=1, q=0, r=-9, s=1, x=12, y=1] [L42] COND TRUE a > b [L43] a = a - b [L44] p = p - q [L45] r = r - s VAL [a=2, b=1, counter=10, p=1, q=0, r=-10, s=1, x=12, y=1] [L34] EXPR counter++ VAL [a=2, b=1, counter=11, p=1, q=0, r=-10, s=1, x=12, y=1] [L34] COND FALSE !(counter++<10) [L53] CALL __VERIFIER_assert(a - b == 0) VAL [\old(cond)=0, counter=11] [L11] COND TRUE !(cond) VAL [\old(cond)=0, counter=11] [L13] reach_error() VAL [\old(cond)=0, counter=11] - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 30 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 9.5s, OverallIterations: 15, TraceHistogramMax: 31, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 2.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 301 SdHoareTripleChecker+Valid, 1.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 270 mSDsluCounter, 2261 SdHoareTripleChecker+Invalid, 1.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1809 mSDsCounter, 179 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1256 IncrementalHoareTripleChecker+Invalid, 1435 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 179 mSolverCounterUnsat, 452 mSDtfsCounter, 1256 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 912 GetRequests, 771 SyntacticMatches, 2 SemanticMatches, 139 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 307 ImplicationChecksByTransitivity, 1.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=228occurred in iteration=10, InterpolantAutomatonStates: 122, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 14 MinimizatonAttempts, 223 StatesRemovedByMinimization, 10 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 3.1s InterpolantComputationTime, 1488 NumberOfCodeBlocks, 1488 NumberOfCodeBlocksAsserted, 74 NumberOfCheckSat, 1127 ConstructedInterpolants, 0 QuantifiedInterpolants, 3769 SizeOfPredicates, 26 NumberOfNonLiveVariables, 1418 ConjunctsInSsa, 187 ConjunctsInUnsatCore, 25 InterpolantComputations, 8 PerfectInterpolantSequences, 1481/1951 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-18 13:34:27,598 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Writing human readable error path to file UltimateCounterExample.errorpath Result: FALSE