./Ultimate.py --spec ../sv-benchmarks/c/properties/valid-memsafety.prp --file ../sv-benchmarks/c/weaver/popl20-queue-add-2.wvr.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version 3289d67d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerMemDerefMemtrack.xml -i ../sv-benchmarks/c/weaver/popl20-queue-add-2.wvr.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-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 valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 8c3fe688d0e9a9929009fc24c8ef56c8fc1bfa15613131b287e178eb7d2f1f1e --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-17 03:40:57,238 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-17 03:40:57,327 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-32bit-Automizer_Default.epf [2024-11-17 03:40:57,331 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-17 03:40:57,332 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-17 03:40:57,363 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-17 03:40:57,364 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-17 03:40:57,364 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-17 03:40:57,365 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-17 03:40:57,365 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-17 03:40:57,366 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-17 03:40:57,366 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-17 03:40:57,368 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-17 03:40:57,369 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-17 03:40:57,370 INFO L153 SettingsManager]: * Use SBE=true [2024-11-17 03:40:57,370 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-17 03:40:57,371 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-17 03:40:57,371 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-17 03:40:57,371 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-17 03:40:57,374 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-17 03:40:57,374 INFO L153 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2024-11-17 03:40:57,375 INFO L153 SettingsManager]: * Bitprecise bitfields=true [2024-11-17 03:40:57,375 INFO L153 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2024-11-17 03:40:57,375 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-17 03:40:57,376 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-17 03:40:57,376 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-17 03:40:57,376 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-17 03:40:57,376 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-17 03:40:57,377 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-17 03:40:57,377 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-17 03:40:57,377 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-17 03:40:57,378 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-17 03:40:57,378 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-17 03:40:57,378 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-17 03:40:57,379 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-17 03:40:57,379 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-17 03:40:57,379 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-17 03:40:57,379 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-17 03:40:57,380 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-17 03:40:57,380 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-17 03:40:57,380 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-17 03:40:57,381 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-17 03:40:57,381 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 valid-free) ) CHECK( init(main()), LTL(G valid-deref) ) CHECK( init(main()), LTL(G valid-memtrack) ) 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 -> 8c3fe688d0e9a9929009fc24c8ef56c8fc1bfa15613131b287e178eb7d2f1f1e [2024-11-17 03:40:57,675 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-17 03:40:57,702 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-17 03:40:57,706 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-17 03:40:57,707 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-17 03:40:57,708 INFO L274 PluginConnector]: CDTParser initialized [2024-11-17 03:40:57,709 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/weaver/popl20-queue-add-2.wvr.c [2024-11-17 03:40:59,233 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-17 03:40:59,435 INFO L384 CDTParser]: Found 1 translation units. [2024-11-17 03:40:59,436 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/weaver/popl20-queue-add-2.wvr.c [2024-11-17 03:40:59,444 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4f97da661/a1e1d4e71dbe477fa947e584a8874487/FLAGb0e1c9c2b [2024-11-17 03:40:59,457 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4f97da661/a1e1d4e71dbe477fa947e584a8874487 [2024-11-17 03:40:59,460 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-17 03:40:59,461 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-17 03:40:59,463 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-17 03:40:59,464 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-17 03:40:59,471 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-17 03:40:59,472 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,473 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@20cb7e17 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59, skipping insertion in model container [2024-11-17 03:40:59,473 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,501 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-17 03:40:59,765 WARN L1072 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-17 03:40:59,767 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 03:40:59,778 INFO L200 MainTranslator]: Completed pre-run [2024-11-17 03:40:59,801 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 03:40:59,823 INFO L204 MainTranslator]: Completed translation [2024-11-17 03:40:59,824 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59 WrapperNode [2024-11-17 03:40:59,824 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-17 03:40:59,825 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-17 03:40:59,825 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-17 03:40:59,825 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-17 03:40:59,833 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,841 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,875 INFO L138 Inliner]: procedures = 23, calls = 30, calls flagged for inlining = 13, calls inlined = 13, statements flattened = 148 [2024-11-17 03:40:59,876 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-17 03:40:59,877 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-17 03:40:59,877 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-17 03:40:59,877 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-17 03:40:59,887 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,888 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,890 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,904 INFO L175 MemorySlicer]: Split 6 memory accesses to 2 slices as follows [2, 4]. 67 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0]. The 1 writes are split as follows [0, 1]. [2024-11-17 03:40:59,905 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,905 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,911 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,912 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,914 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,915 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,918 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-17 03:40:59,919 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-17 03:40:59,920 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-17 03:40:59,920 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-17 03:40:59,921 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (1/1) ... [2024-11-17 03:40:59,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-17 03:40:59,937 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:40:59,953 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-17 03:40:59,957 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-17 03:40:59,999 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-17 03:40:59,999 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2024-11-17 03:40:59,999 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2024-11-17 03:40:59,999 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2024-11-17 03:40:59,999 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2024-11-17 03:41:00,000 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-17 03:41:00,000 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-17 03:41:00,000 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-17 03:41:00,000 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-17 03:41:00,000 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_atomic_end [2024-11-17 03:41:00,001 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_atomic_begin [2024-11-17 03:41:00,001 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-17 03:41:00,001 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-17 03:41:00,001 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-17 03:41:00,001 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-17 03:41:00,001 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-17 03:41:00,003 WARN L225 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to OneNontrivialStatement. [2024-11-17 03:41:00,103 INFO L256 CfgBuilder]: Building ICFG [2024-11-17 03:41:00,105 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-17 03:41:00,457 INFO L303 CfgBuilder]: Omitted future-live optimization because the input is a concurrent program. [2024-11-17 03:41:00,457 INFO L307 CfgBuilder]: Performing block encoding [2024-11-17 03:41:00,719 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-17 03:41:00,719 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-17 03:41:00,720 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 03:41:00 BoogieIcfgContainer [2024-11-17 03:41:00,721 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-17 03:41:00,724 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-17 03:41:00,725 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-17 03:41:00,729 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-17 03:41:00,729 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.11 03:40:59" (1/3) ... [2024-11-17 03:41:00,730 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@60dcbb37 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.11 03:41:00, skipping insertion in model container [2024-11-17 03:41:00,730 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 03:40:59" (2/3) ... [2024-11-17 03:41:00,730 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@60dcbb37 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.11 03:41:00, skipping insertion in model container [2024-11-17 03:41:00,731 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 03:41:00" (3/3) ... [2024-11-17 03:41:00,734 INFO L112 eAbstractionObserver]: Analyzing ICFG popl20-queue-add-2.wvr.c [2024-11-17 03:41:00,753 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:None NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-17 03:41:00,754 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 10 error locations. [2024-11-17 03:41:00,754 INFO L489 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2024-11-17 03:41:00,821 INFO L143 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2024-11-17 03:41:00,863 INFO L73 FinitePrefix]: Start finitePrefix. Operand has 48 places, 48 transitions, 110 flow [2024-11-17 03:41:00,899 INFO L124 PetriNetUnfolderBase]: 7/46 cut-off events. [2024-11-17 03:41:00,899 INFO L125 PetriNetUnfolderBase]: For 2/2 co-relation queries the response was YES. [2024-11-17 03:41:00,905 INFO L83 FinitePrefix]: Finished finitePrefix Result has 55 conditions, 46 events. 7/46 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 8. Compared 89 event pairs, 0 based on Foata normal form. 0/29 useless extension candidates. Maximal degree in co-relation 31. Up to 3 conditions per place. [2024-11-17 03:41:00,906 INFO L82 GeneralOperation]: Start removeDead. Operand has 48 places, 48 transitions, 110 flow [2024-11-17 03:41:00,909 INFO L88 GeneralOperation]: Finished RemoveDead, result has has 45 places, 45 transitions, 102 flow [2024-11-17 03:41:00,918 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-17 03:41:00,927 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=None, 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;@2409624e, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-17 03:41:00,928 INFO L334 AbstractCegarLoop]: Starting to check reachability of 18 error locations. [2024-11-17 03:41:00,932 INFO L185 PetriNetUnfolderBase]: Found word, exiting Unfolder. [2024-11-17 03:41:00,932 INFO L124 PetriNetUnfolderBase]: 2/7 cut-off events. [2024-11-17 03:41:00,933 INFO L125 PetriNetUnfolderBase]: For 0/0 co-relation queries the response was YES. [2024-11-17 03:41:00,933 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:00,934 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1] [2024-11-17 03:41:00,934 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:00,939 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:00,940 INFO L85 PathProgramCache]: Analyzing trace with hash 13169199, now seen corresponding path program 1 times [2024-11-17 03:41:00,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:00,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [633288106] [2024-11-17 03:41:00,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:00,950 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:01,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:01,234 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:01,235 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:01,235 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [633288106] [2024-11-17 03:41:01,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [633288106] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:01,237 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:01,237 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2024-11-17 03:41:01,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [45889927] [2024-11-17 03:41:01,239 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:01,248 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-17 03:41:01,253 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:01,277 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-17 03:41:01,278 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-17 03:41:01,288 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 16 out of 48 [2024-11-17 03:41:01,291 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 45 places, 45 transitions, 102 flow. Second operand has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:01,291 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:01,292 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 16 of 48 [2024-11-17 03:41:01,293 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:01,523 INFO L124 PetriNetUnfolderBase]: 177/358 cut-off events. [2024-11-17 03:41:01,524 INFO L125 PetriNetUnfolderBase]: For 15/15 co-relation queries the response was YES. [2024-11-17 03:41:01,529 INFO L83 FinitePrefix]: Finished finitePrefix Result has 695 conditions, 358 events. 177/358 cut-off events. For 15/15 co-relation queries the response was YES. Maximal size of possible extension queue 50. Compared 2000 event pairs, 154 based on Foata normal form. 46/273 useless extension candidates. Maximal degree in co-relation 642. Up to 304 conditions per place. [2024-11-17 03:41:01,537 INFO L140 encePairwiseOnDemand]: 40/48 looper letters, 23 selfloop transitions, 2 changer transitions 0/38 dead transitions. [2024-11-17 03:41:01,540 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 44 places, 38 transitions, 138 flow [2024-11-17 03:41:01,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-17 03:41:01,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-11-17 03:41:01,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 79 transitions. [2024-11-17 03:41:01,556 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5486111111111112 [2024-11-17 03:41:01,557 INFO L175 Difference]: Start difference. First operand has 45 places, 45 transitions, 102 flow. Second operand 3 states and 79 transitions. [2024-11-17 03:41:01,558 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 44 places, 38 transitions, 138 flow [2024-11-17 03:41:01,560 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 40 places, 38 transitions, 130 flow, removed 0 selfloop flow, removed 4 redundant places. [2024-11-17 03:41:01,562 INFO L231 Difference]: Finished difference. Result has 40 places, 38 transitions, 84 flow [2024-11-17 03:41:01,565 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=80, PETRI_DIFFERENCE_MINUEND_PLACES=38, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=38, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=36, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=84, PETRI_PLACES=40, PETRI_TRANSITIONS=38} [2024-11-17 03:41:01,570 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, -5 predicate places. [2024-11-17 03:41:01,570 INFO L471 AbstractCegarLoop]: Abstraction has has 40 places, 38 transitions, 84 flow [2024-11-17 03:41:01,570 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:01,571 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:01,571 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1] [2024-11-17 03:41:01,572 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-17 03:41:01,572 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:01,573 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:01,574 INFO L85 PathProgramCache]: Analyzing trace with hash 13169200, now seen corresponding path program 1 times [2024-11-17 03:41:01,574 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:01,574 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1989769441] [2024-11-17 03:41:01,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:01,575 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:01,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:01,920 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:01,920 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:01,921 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1989769441] [2024-11-17 03:41:01,921 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1989769441] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:01,921 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:01,921 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-17 03:41:01,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [600333914] [2024-11-17 03:41:01,922 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:01,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-17 03:41:01,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:01,924 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-17 03:41:01,924 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-17 03:41:01,932 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 16 out of 48 [2024-11-17 03:41:01,933 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 40 places, 38 transitions, 84 flow. Second operand has 4 states, 4 states have (on average 16.75) internal successors, (67), 4 states have internal predecessors, (67), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:01,933 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:01,933 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 16 of 48 [2024-11-17 03:41:01,933 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:02,134 INFO L124 PetriNetUnfolderBase]: 178/363 cut-off events. [2024-11-17 03:41:02,135 INFO L125 PetriNetUnfolderBase]: For 2/2 co-relation queries the response was YES. [2024-11-17 03:41:02,136 INFO L83 FinitePrefix]: Finished finitePrefix Result has 689 conditions, 363 events. 178/363 cut-off events. For 2/2 co-relation queries the response was YES. Maximal size of possible extension queue 50. Compared 2019 event pairs, 154 based on Foata normal form. 0/231 useless extension candidates. Maximal degree in co-relation 663. Up to 309 conditions per place. [2024-11-17 03:41:02,141 INFO L140 encePairwiseOnDemand]: 43/48 looper letters, 25 selfloop transitions, 4 changer transitions 0/41 dead transitions. [2024-11-17 03:41:02,141 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 43 places, 41 transitions, 150 flow [2024-11-17 03:41:02,142 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-17 03:41:02,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-11-17 03:41:02,143 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 94 transitions. [2024-11-17 03:41:02,145 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.4895833333333333 [2024-11-17 03:41:02,145 INFO L175 Difference]: Start difference. First operand has 40 places, 38 transitions, 84 flow. Second operand 4 states and 94 transitions. [2024-11-17 03:41:02,145 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 43 places, 41 transitions, 150 flow [2024-11-17 03:41:02,146 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 41 places, 41 transitions, 144 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-11-17 03:41:02,148 INFO L231 Difference]: Finished difference. Result has 43 places, 41 transitions, 107 flow [2024-11-17 03:41:02,151 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=80, PETRI_DIFFERENCE_MINUEND_PLACES=38, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=38, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=34, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=107, PETRI_PLACES=43, PETRI_TRANSITIONS=41} [2024-11-17 03:41:02,152 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, -2 predicate places. [2024-11-17 03:41:02,152 INFO L471 AbstractCegarLoop]: Abstraction has has 43 places, 41 transitions, 107 flow [2024-11-17 03:41:02,152 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 16.75) internal successors, (67), 4 states have internal predecessors, (67), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:02,152 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:02,153 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 1, 1, 1] [2024-11-17 03:41:02,153 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-17 03:41:02,153 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:02,153 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:02,154 INFO L85 PathProgramCache]: Analyzing trace with hash 1482031916, now seen corresponding path program 1 times [2024-11-17 03:41:02,154 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:02,154 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1705956598] [2024-11-17 03:41:02,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:02,154 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:02,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:02,576 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:02,577 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:02,577 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1705956598] [2024-11-17 03:41:02,577 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1705956598] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:02,577 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1854576098] [2024-11-17 03:41:02,578 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:02,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:02,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:02,580 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-17 03:41:02,582 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-17 03:41:02,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:02,657 INFO L255 TraceCheckSpWp]: Trace formula consists of 71 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-17 03:41:02,662 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:02,754 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2024-11-17 03:41:03,045 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:03,046 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:03,203 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:03,203 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1854576098] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:03,203 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:03,204 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3, 3] total 9 [2024-11-17 03:41:03,204 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1100934700] [2024-11-17 03:41:03,204 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:03,204 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-17 03:41:03,205 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:03,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-17 03:41:03,207 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2024-11-17 03:41:03,275 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 15 out of 48 [2024-11-17 03:41:03,276 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 43 places, 41 transitions, 107 flow. Second operand has 11 states, 11 states have (on average 16.363636363636363) internal successors, (180), 11 states have internal predecessors, (180), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:03,276 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:03,276 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 15 of 48 [2024-11-17 03:41:03,276 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:03,616 INFO L124 PetriNetUnfolderBase]: 179/367 cut-off events. [2024-11-17 03:41:03,616 INFO L125 PetriNetUnfolderBase]: For 5/5 co-relation queries the response was YES. [2024-11-17 03:41:03,618 INFO L83 FinitePrefix]: Finished finitePrefix Result has 710 conditions, 367 events. 179/367 cut-off events. For 5/5 co-relation queries the response was YES. Maximal size of possible extension queue 50. Compared 2068 event pairs, 154 based on Foata normal form. 0/236 useless extension candidates. Maximal degree in co-relation 673. Up to 306 conditions per place. [2024-11-17 03:41:03,622 INFO L140 encePairwiseOnDemand]: 43/48 looper letters, 24 selfloop transitions, 10 changer transitions 0/45 dead transitions. [2024-11-17 03:41:03,622 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 49 places, 45 transitions, 187 flow [2024-11-17 03:41:03,623 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-17 03:41:03,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2024-11-17 03:41:03,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 156 transitions. [2024-11-17 03:41:03,628 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.40625 [2024-11-17 03:41:03,628 INFO L175 Difference]: Start difference. First operand has 43 places, 41 transitions, 107 flow. Second operand 8 states and 156 transitions. [2024-11-17 03:41:03,629 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 49 places, 45 transitions, 187 flow [2024-11-17 03:41:03,630 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 48 places, 45 transitions, 184 flow, removed 0 selfloop flow, removed 1 redundant places. [2024-11-17 03:41:03,631 INFO L231 Difference]: Finished difference. Result has 48 places, 43 transitions, 132 flow [2024-11-17 03:41:03,632 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=100, PETRI_DIFFERENCE_MINUEND_PLACES=41, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=40, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=7, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=33, PETRI_DIFFERENCE_SUBTRAHEND_STATES=8, PETRI_FLOW=132, PETRI_PLACES=48, PETRI_TRANSITIONS=43} [2024-11-17 03:41:03,633 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 3 predicate places. [2024-11-17 03:41:03,633 INFO L471 AbstractCegarLoop]: Abstraction has has 48 places, 43 transitions, 132 flow [2024-11-17 03:41:03,634 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 16.363636363636363) internal successors, (180), 11 states have internal predecessors, (180), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:03,634 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:03,634 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:03,654 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-17 03:41:03,838 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:03,839 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:03,840 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:03,840 INFO L85 PathProgramCache]: Analyzing trace with hash 1820238190, now seen corresponding path program 1 times [2024-11-17 03:41:03,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:03,841 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [430446777] [2024-11-17 03:41:03,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:03,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:03,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:03,921 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:03,921 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:03,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [430446777] [2024-11-17 03:41:03,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [430446777] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:03,922 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:03,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-17 03:41:03,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [123523938] [2024-11-17 03:41:03,923 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:03,923 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-17 03:41:03,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:03,924 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-17 03:41:03,924 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-17 03:41:03,934 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 16 out of 48 [2024-11-17 03:41:03,934 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 48 places, 43 transitions, 132 flow. Second operand has 4 states, 4 states have (on average 17.25) internal successors, (69), 4 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:03,935 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:03,935 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 16 of 48 [2024-11-17 03:41:03,935 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:04,008 INFO L124 PetriNetUnfolderBase]: 119/256 cut-off events. [2024-11-17 03:41:04,008 INFO L125 PetriNetUnfolderBase]: For 21/21 co-relation queries the response was YES. [2024-11-17 03:41:04,009 INFO L83 FinitePrefix]: Finished finitePrefix Result has 501 conditions, 256 events. 119/256 cut-off events. For 21/21 co-relation queries the response was YES. Maximal size of possible extension queue 27. Compared 1187 event pairs, 98 based on Foata normal form. 0/186 useless extension candidates. Maximal degree in co-relation 459. Up to 204 conditions per place. [2024-11-17 03:41:04,010 INFO L140 encePairwiseOnDemand]: 43/48 looper letters, 24 selfloop transitions, 4 changer transitions 0/40 dead transitions. [2024-11-17 03:41:04,011 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 48 places, 40 transitions, 182 flow [2024-11-17 03:41:04,011 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-17 03:41:04,011 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-11-17 03:41:04,012 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 89 transitions. [2024-11-17 03:41:04,012 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.4635416666666667 [2024-11-17 03:41:04,012 INFO L175 Difference]: Start difference. First operand has 48 places, 43 transitions, 132 flow. Second operand 4 states and 89 transitions. [2024-11-17 03:41:04,013 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 48 places, 40 transitions, 182 flow [2024-11-17 03:41:04,014 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 42 places, 40 transitions, 150 flow, removed 6 selfloop flow, removed 6 redundant places. [2024-11-17 03:41:04,014 INFO L231 Difference]: Finished difference. Result has 42 places, 40 transitions, 102 flow [2024-11-17 03:41:04,015 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=94, PETRI_DIFFERENCE_MINUEND_PLACES=39, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=40, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=36, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=102, PETRI_PLACES=42, PETRI_TRANSITIONS=40} [2024-11-17 03:41:04,015 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, -3 predicate places. [2024-11-17 03:41:04,015 INFO L471 AbstractCegarLoop]: Abstraction has has 42 places, 40 transitions, 102 flow [2024-11-17 03:41:04,016 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 17.25) internal successors, (69), 4 states have internal predecessors, (69), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:04,016 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:04,016 INFO L204 CegarLoopForPetriNet]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:04,016 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-17 03:41:04,016 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:04,017 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:04,017 INFO L85 PathProgramCache]: Analyzing trace with hash 1820238191, now seen corresponding path program 1 times [2024-11-17 03:41:04,017 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:04,017 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1874454859] [2024-11-17 03:41:04,018 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:04,018 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:04,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:04,085 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:04,085 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:04,085 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1874454859] [2024-11-17 03:41:04,085 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1874454859] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:04,085 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:04,085 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-17 03:41:04,085 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [544814737] [2024-11-17 03:41:04,086 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:04,086 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-17 03:41:04,086 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:04,086 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-17 03:41:04,087 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-17 03:41:04,096 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 16 out of 48 [2024-11-17 03:41:04,096 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 42 places, 40 transitions, 102 flow. Second operand has 4 states, 4 states have (on average 17.5) internal successors, (70), 4 states have internal predecessors, (70), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:04,096 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:04,097 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 16 of 48 [2024-11-17 03:41:04,097 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:04,201 INFO L124 PetriNetUnfolderBase]: 125/287 cut-off events. [2024-11-17 03:41:04,202 INFO L125 PetriNetUnfolderBase]: For 6/6 co-relation queries the response was YES. [2024-11-17 03:41:04,203 INFO L83 FinitePrefix]: Finished finitePrefix Result has 542 conditions, 287 events. 125/287 cut-off events. For 6/6 co-relation queries the response was YES. Maximal size of possible extension queue 27. Compared 1325 event pairs, 105 based on Foata normal form. 7/226 useless extension candidates. Maximal degree in co-relation 449. Up to 211 conditions per place. [2024-11-17 03:41:04,204 INFO L140 encePairwiseOnDemand]: 38/48 looper letters, 26 selfloop transitions, 2 changer transitions 8/47 dead transitions. [2024-11-17 03:41:04,204 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 46 places, 47 transitions, 190 flow [2024-11-17 03:41:04,207 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-17 03:41:04,207 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-11-17 03:41:04,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 119 transitions. [2024-11-17 03:41:04,208 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.49583333333333335 [2024-11-17 03:41:04,208 INFO L175 Difference]: Start difference. First operand has 42 places, 40 transitions, 102 flow. Second operand 5 states and 119 transitions. [2024-11-17 03:41:04,209 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 46 places, 47 transitions, 190 flow [2024-11-17 03:41:04,209 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 44 places, 47 transitions, 185 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-11-17 03:41:04,212 INFO L231 Difference]: Finished difference. Result has 46 places, 39 transitions, 113 flow [2024-11-17 03:41:04,212 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=97, PETRI_DIFFERENCE_MINUEND_PLACES=40, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=40, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=2, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=38, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=113, PETRI_PLACES=46, PETRI_TRANSITIONS=39} [2024-11-17 03:41:04,213 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 1 predicate places. [2024-11-17 03:41:04,213 INFO L471 AbstractCegarLoop]: Abstraction has has 46 places, 39 transitions, 113 flow [2024-11-17 03:41:04,214 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 17.5) internal successors, (70), 4 states have internal predecessors, (70), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:04,217 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:04,217 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:04,217 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-17 03:41:04,217 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:04,218 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:04,218 INFO L85 PathProgramCache]: Analyzing trace with hash -1063203341, now seen corresponding path program 1 times [2024-11-17 03:41:04,218 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:04,218 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [55918149] [2024-11-17 03:41:04,218 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:04,218 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:04,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:04,413 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:04,414 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:04,414 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [55918149] [2024-11-17 03:41:04,414 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [55918149] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:04,414 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:04,414 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-17 03:41:04,415 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [584577499] [2024-11-17 03:41:04,415 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:04,415 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-17 03:41:04,415 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:04,416 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-17 03:41:04,416 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-17 03:41:04,432 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 16 out of 48 [2024-11-17 03:41:04,432 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 46 places, 39 transitions, 113 flow. Second operand has 6 states, 6 states have (on average 17.333333333333332) internal successors, (104), 6 states have internal predecessors, (104), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:04,432 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:04,433 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 16 of 48 [2024-11-17 03:41:04,433 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:04,520 INFO L124 PetriNetUnfolderBase]: 70/163 cut-off events. [2024-11-17 03:41:04,520 INFO L125 PetriNetUnfolderBase]: For 34/34 co-relation queries the response was YES. [2024-11-17 03:41:04,521 INFO L83 FinitePrefix]: Finished finitePrefix Result has 347 conditions, 163 events. 70/163 cut-off events. For 34/34 co-relation queries the response was YES. Maximal size of possible extension queue 13. Compared 560 event pairs, 54 based on Foata normal form. 0/138 useless extension candidates. Maximal degree in co-relation 330. Up to 122 conditions per place. [2024-11-17 03:41:04,522 INFO L140 encePairwiseOnDemand]: 43/48 looper letters, 22 selfloop transitions, 3 changer transitions 0/36 dead transitions. [2024-11-17 03:41:04,522 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 44 places, 36 transitions, 151 flow [2024-11-17 03:41:04,522 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-17 03:41:04,522 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-11-17 03:41:04,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 87 transitions. [2024-11-17 03:41:04,523 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.453125 [2024-11-17 03:41:04,523 INFO L175 Difference]: Start difference. First operand has 46 places, 39 transitions, 113 flow. Second operand 4 states and 87 transitions. [2024-11-17 03:41:04,523 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 44 places, 36 transitions, 151 flow [2024-11-17 03:41:04,524 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 42 places, 36 transitions, 147 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-11-17 03:41:04,525 INFO L231 Difference]: Finished difference. Result has 42 places, 36 transitions, 103 flow [2024-11-17 03:41:04,525 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=97, PETRI_DIFFERENCE_MINUEND_PLACES=39, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=36, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=3, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=33, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=103, PETRI_PLACES=42, PETRI_TRANSITIONS=36} [2024-11-17 03:41:04,526 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, -3 predicate places. [2024-11-17 03:41:04,526 INFO L471 AbstractCegarLoop]: Abstraction has has 42 places, 36 transitions, 103 flow [2024-11-17 03:41:04,526 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 17.333333333333332) internal successors, (104), 6 states have internal predecessors, (104), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:04,526 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:04,527 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:04,527 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-17 03:41:04,527 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:04,527 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:04,527 INFO L85 PathProgramCache]: Analyzing trace with hash -2054360843, now seen corresponding path program 1 times [2024-11-17 03:41:04,527 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:04,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1273244246] [2024-11-17 03:41:04,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:04,528 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:04,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:04,746 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 03:41:04,747 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:04,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1273244246] [2024-11-17 03:41:04,747 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1273244246] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:04,747 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:04,747 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-17 03:41:04,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [622719091] [2024-11-17 03:41:04,748 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:04,748 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-17 03:41:04,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:04,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-17 03:41:04,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2024-11-17 03:41:04,768 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 13 out of 48 [2024-11-17 03:41:04,769 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 42 places, 36 transitions, 103 flow. Second operand has 8 states, 8 states have (on average 15.625) internal successors, (125), 8 states have internal predecessors, (125), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:04,769 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:04,769 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 13 of 48 [2024-11-17 03:41:04,769 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:04,966 INFO L124 PetriNetUnfolderBase]: 273/557 cut-off events. [2024-11-17 03:41:04,968 INFO L125 PetriNetUnfolderBase]: For 83/83 co-relation queries the response was YES. [2024-11-17 03:41:04,969 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1174 conditions, 557 events. 273/557 cut-off events. For 83/83 co-relation queries the response was YES. Maximal size of possible extension queue 43. Compared 2670 event pairs, 67 based on Foata normal form. 1/542 useless extension candidates. Maximal degree in co-relation 1138. Up to 179 conditions per place. [2024-11-17 03:41:04,972 INFO L140 encePairwiseOnDemand]: 38/48 looper letters, 58 selfloop transitions, 12 changer transitions 8/86 dead transitions. [2024-11-17 03:41:04,972 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 50 places, 86 transitions, 389 flow [2024-11-17 03:41:04,973 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-17 03:41:04,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2024-11-17 03:41:04,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 191 transitions. [2024-11-17 03:41:04,974 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.44212962962962965 [2024-11-17 03:41:04,975 INFO L175 Difference]: Start difference. First operand has 42 places, 36 transitions, 103 flow. Second operand 9 states and 191 transitions. [2024-11-17 03:41:04,975 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 50 places, 86 transitions, 389 flow [2024-11-17 03:41:04,976 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 48 places, 86 transitions, 385 flow, removed 0 selfloop flow, removed 2 redundant places. [2024-11-17 03:41:04,979 INFO L231 Difference]: Finished difference. Result has 53 places, 45 transitions, 174 flow [2024-11-17 03:41:04,979 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=99, PETRI_DIFFERENCE_MINUEND_PLACES=40, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=36, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=27, PETRI_DIFFERENCE_SUBTRAHEND_STATES=9, PETRI_FLOW=174, PETRI_PLACES=53, PETRI_TRANSITIONS=45} [2024-11-17 03:41:04,980 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 8 predicate places. [2024-11-17 03:41:04,982 INFO L471 AbstractCegarLoop]: Abstraction has has 53 places, 45 transitions, 174 flow [2024-11-17 03:41:04,982 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 15.625) internal successors, (125), 8 states have internal predecessors, (125), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:04,982 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:04,982 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:04,982 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-17 03:41:04,983 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:04,983 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:04,983 INFO L85 PathProgramCache]: Analyzing trace with hash -678594013, now seen corresponding path program 2 times [2024-11-17 03:41:04,983 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:04,983 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [289674849] [2024-11-17 03:41:04,983 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:04,983 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:04,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:05,060 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 03:41:05,061 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:05,061 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [289674849] [2024-11-17 03:41:05,061 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [289674849] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:05,061 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:05,062 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-17 03:41:05,062 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1084224327] [2024-11-17 03:41:05,062 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:05,062 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-17 03:41:05,062 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:05,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-17 03:41:05,063 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-17 03:41:05,064 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 17 out of 48 [2024-11-17 03:41:05,064 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 53 places, 45 transitions, 174 flow. Second operand has 3 states, 3 states have (on average 22.666666666666668) internal successors, (68), 3 states have internal predecessors, (68), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:05,064 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:05,064 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 17 of 48 [2024-11-17 03:41:05,064 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:05,135 INFO L124 PetriNetUnfolderBase]: 126/316 cut-off events. [2024-11-17 03:41:05,136 INFO L125 PetriNetUnfolderBase]: For 181/188 co-relation queries the response was YES. [2024-11-17 03:41:05,138 INFO L83 FinitePrefix]: Finished finitePrefix Result has 769 conditions, 316 events. 126/316 cut-off events. For 181/188 co-relation queries the response was YES. Maximal size of possible extension queue 21. Compared 1304 event pairs, 27 based on Foata normal form. 2/304 useless extension candidates. Maximal degree in co-relation 755. Up to 193 conditions per place. [2024-11-17 03:41:05,139 INFO L140 encePairwiseOnDemand]: 44/48 looper letters, 29 selfloop transitions, 3 changer transitions 0/49 dead transitions. [2024-11-17 03:41:05,139 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 54 places, 49 transitions, 245 flow [2024-11-17 03:41:05,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-17 03:41:05,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3 states. [2024-11-17 03:41:05,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3 states to 3 states and 77 transitions. [2024-11-17 03:41:05,143 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5347222222222222 [2024-11-17 03:41:05,143 INFO L175 Difference]: Start difference. First operand has 53 places, 45 transitions, 174 flow. Second operand 3 states and 77 transitions. [2024-11-17 03:41:05,144 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 54 places, 49 transitions, 245 flow [2024-11-17 03:41:05,146 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 51 places, 49 transitions, 233 flow, removed 2 selfloop flow, removed 3 redundant places. [2024-11-17 03:41:05,147 INFO L231 Difference]: Finished difference. Result has 52 places, 45 transitions, 175 flow [2024-11-17 03:41:05,147 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=152, PETRI_DIFFERENCE_MINUEND_PLACES=49, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=43, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=1, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=40, PETRI_DIFFERENCE_SUBTRAHEND_STATES=3, PETRI_FLOW=175, PETRI_PLACES=52, PETRI_TRANSITIONS=45} [2024-11-17 03:41:05,148 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 7 predicate places. [2024-11-17 03:41:05,149 INFO L471 AbstractCegarLoop]: Abstraction has has 52 places, 45 transitions, 175 flow [2024-11-17 03:41:05,149 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 22.666666666666668) internal successors, (68), 3 states have internal predecessors, (68), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:05,149 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:05,149 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:05,149 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-17 03:41:05,150 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:05,150 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:05,150 INFO L85 PathProgramCache]: Analyzing trace with hash -1075183226, now seen corresponding path program 1 times [2024-11-17 03:41:05,151 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:05,151 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [367881205] [2024-11-17 03:41:05,151 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:05,151 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:05,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:05,306 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:05,307 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:05,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [367881205] [2024-11-17 03:41:05,307 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [367881205] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:05,307 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [822954031] [2024-11-17 03:41:05,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:05,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:05,308 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:05,309 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-17 03:41:05,311 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-17 03:41:05,383 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:05,384 INFO L255 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-17 03:41:05,386 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:05,473 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:05,473 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:05,588 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:05,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [822954031] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:05,589 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:05,589 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5] total 11 [2024-11-17 03:41:05,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1198059344] [2024-11-17 03:41:05,590 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:05,590 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-17 03:41:05,590 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:05,591 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-17 03:41:05,591 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2024-11-17 03:41:05,606 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 16 out of 48 [2024-11-17 03:41:05,607 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 52 places, 45 transitions, 175 flow. Second operand has 12 states, 12 states have (on average 18.833333333333332) internal successors, (226), 12 states have internal predecessors, (226), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:05,607 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:05,607 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 16 of 48 [2024-11-17 03:41:05,607 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:05,793 INFO L124 PetriNetUnfolderBase]: 199/526 cut-off events. [2024-11-17 03:41:05,794 INFO L125 PetriNetUnfolderBase]: For 526/553 co-relation queries the response was YES. [2024-11-17 03:41:05,801 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1358 conditions, 526 events. 199/526 cut-off events. For 526/553 co-relation queries the response was YES. Maximal size of possible extension queue 31. Compared 2750 event pairs, 104 based on Foata normal form. 24/513 useless extension candidates. Maximal degree in co-relation 784. Up to 224 conditions per place. [2024-11-17 03:41:05,803 INFO L140 encePairwiseOnDemand]: 41/48 looper letters, 40 selfloop transitions, 8 changer transitions 3/67 dead transitions. [2024-11-17 03:41:05,804 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 59 places, 67 transitions, 355 flow [2024-11-17 03:41:05,804 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-17 03:41:05,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2024-11-17 03:41:05,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 175 transitions. [2024-11-17 03:41:05,805 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.4557291666666667 [2024-11-17 03:41:05,805 INFO L175 Difference]: Start difference. First operand has 52 places, 45 transitions, 175 flow. Second operand 8 states and 175 transitions. [2024-11-17 03:41:05,806 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 59 places, 67 transitions, 355 flow [2024-11-17 03:41:05,807 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 57 places, 67 transitions, 334 flow, removed 8 selfloop flow, removed 2 redundant places. [2024-11-17 03:41:05,808 INFO L231 Difference]: Finished difference. Result has 60 places, 47 transitions, 202 flow [2024-11-17 03:41:05,809 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=162, PETRI_DIFFERENCE_MINUEND_PLACES=50, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=45, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=6, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=37, PETRI_DIFFERENCE_SUBTRAHEND_STATES=8, PETRI_FLOW=202, PETRI_PLACES=60, PETRI_TRANSITIONS=47} [2024-11-17 03:41:05,809 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 15 predicate places. [2024-11-17 03:41:05,809 INFO L471 AbstractCegarLoop]: Abstraction has has 60 places, 47 transitions, 202 flow [2024-11-17 03:41:05,810 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 18.833333333333332) internal successors, (226), 12 states have internal predecessors, (226), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:05,810 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:05,810 INFO L204 CegarLoopForPetriNet]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:05,827 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-17 03:41:06,010 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,SelfDestructingSolverStorable8 [2024-11-17 03:41:06,011 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:06,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:06,012 INFO L85 PathProgramCache]: Analyzing trace with hash -1386588244, now seen corresponding path program 1 times [2024-11-17 03:41:06,012 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:06,012 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2146300911] [2024-11-17 03:41:06,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:06,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:06,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:06,074 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 03:41:06,075 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:06,075 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2146300911] [2024-11-17 03:41:06,075 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2146300911] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 03:41:06,075 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 03:41:06,075 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-17 03:41:06,075 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [724811552] [2024-11-17 03:41:06,075 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 03:41:06,076 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-17 03:41:06,076 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:06,076 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-17 03:41:06,077 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-17 03:41:06,077 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 17 out of 48 [2024-11-17 03:41:06,077 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 60 places, 47 transitions, 202 flow. Second operand has 4 states, 4 states have (on average 21.5) internal successors, (86), 4 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:06,077 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:06,077 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 17 of 48 [2024-11-17 03:41:06,077 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:06,200 INFO L124 PetriNetUnfolderBase]: 206/625 cut-off events. [2024-11-17 03:41:06,200 INFO L125 PetriNetUnfolderBase]: For 438/457 co-relation queries the response was YES. [2024-11-17 03:41:06,203 INFO L83 FinitePrefix]: Finished finitePrefix Result has 1463 conditions, 625 events. 206/625 cut-off events. For 438/457 co-relation queries the response was YES. Maximal size of possible extension queue 36. Compared 3434 event pairs, 43 based on Foata normal form. 19/628 useless extension candidates. Maximal degree in co-relation 1225. Up to 144 conditions per place. [2024-11-17 03:41:06,205 INFO L140 encePairwiseOnDemand]: 44/48 looper letters, 44 selfloop transitions, 7 changer transitions 5/72 dead transitions. [2024-11-17 03:41:06,206 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 63 places, 72 transitions, 390 flow [2024-11-17 03:41:06,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-17 03:41:06,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4 states. [2024-11-17 03:41:06,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 113 transitions. [2024-11-17 03:41:06,207 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5885416666666666 [2024-11-17 03:41:06,207 INFO L175 Difference]: Start difference. First operand has 60 places, 47 transitions, 202 flow. Second operand 4 states and 113 transitions. [2024-11-17 03:41:06,208 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 63 places, 72 transitions, 390 flow [2024-11-17 03:41:06,210 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 59 places, 72 transitions, 367 flow, removed 7 selfloop flow, removed 4 redundant places. [2024-11-17 03:41:06,212 INFO L231 Difference]: Finished difference. Result has 61 places, 46 transitions, 205 flow [2024-11-17 03:41:06,213 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=182, PETRI_DIFFERENCE_MINUEND_PLACES=56, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=46, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=4, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=41, PETRI_DIFFERENCE_SUBTRAHEND_STATES=4, PETRI_FLOW=205, PETRI_PLACES=61, PETRI_TRANSITIONS=46} [2024-11-17 03:41:06,215 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 16 predicate places. [2024-11-17 03:41:06,215 INFO L471 AbstractCegarLoop]: Abstraction has has 61 places, 46 transitions, 205 flow [2024-11-17 03:41:06,215 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 21.5) internal successors, (86), 4 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:06,215 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:06,215 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:06,215 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9 [2024-11-17 03:41:06,216 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:06,216 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:06,216 INFO L85 PathProgramCache]: Analyzing trace with hash -1166415260, now seen corresponding path program 2 times [2024-11-17 03:41:06,216 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:06,216 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2021094048] [2024-11-17 03:41:06,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:06,216 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:06,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:06,717 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:06,718 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:06,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2021094048] [2024-11-17 03:41:06,718 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2021094048] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:06,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [952133512] [2024-11-17 03:41:06,718 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-17 03:41:06,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:06,719 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:06,720 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-17 03:41:06,722 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-17 03:41:06,802 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-17 03:41:06,802 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:06,804 INFO L255 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-17 03:41:06,806 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:07,029 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 3 [2024-11-17 03:41:07,066 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:07,066 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:07,204 INFO L349 Elim1Store]: treesize reduction 5, result has 37.5 percent of original size [2024-11-17 03:41:07,205 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 11 [2024-11-17 03:41:07,541 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:07,541 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [952133512] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:07,542 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:07,543 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 8] total 22 [2024-11-17 03:41:07,543 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1935783237] [2024-11-17 03:41:07,543 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:07,544 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-17 03:41:07,544 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:07,545 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-17 03:41:07,545 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=407, Unknown=0, NotChecked=0, Total=506 [2024-11-17 03:41:07,671 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 14 out of 48 [2024-11-17 03:41:07,672 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 61 places, 46 transitions, 205 flow. Second operand has 23 states, 23 states have (on average 16.652173913043477) internal successors, (383), 23 states have internal predecessors, (383), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:07,672 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:07,673 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 14 of 48 [2024-11-17 03:41:07,673 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:08,552 INFO L124 PetriNetUnfolderBase]: 479/1234 cut-off events. [2024-11-17 03:41:08,553 INFO L125 PetriNetUnfolderBase]: For 1543/1543 co-relation queries the response was YES. [2024-11-17 03:41:08,558 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3191 conditions, 1234 events. 479/1234 cut-off events. For 1543/1543 co-relation queries the response was YES. Maximal size of possible extension queue 59. Compared 7477 event pairs, 84 based on Foata normal form. 89/1307 useless extension candidates. Maximal degree in co-relation 2058. Up to 280 conditions per place. [2024-11-17 03:41:08,563 INFO L140 encePairwiseOnDemand]: 40/48 looper letters, 91 selfloop transitions, 17 changer transitions 11/132 dead transitions. [2024-11-17 03:41:08,563 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 73 places, 132 transitions, 809 flow [2024-11-17 03:41:08,564 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-17 03:41:08,564 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2024-11-17 03:41:08,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 353 transitions. [2024-11-17 03:41:08,566 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.4325980392156863 [2024-11-17 03:41:08,566 INFO L175 Difference]: Start difference. First operand has 61 places, 46 transitions, 205 flow. Second operand 17 states and 353 transitions. [2024-11-17 03:41:08,566 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 73 places, 132 transitions, 809 flow [2024-11-17 03:41:08,569 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 70 places, 132 transitions, 749 flow, removed 29 selfloop flow, removed 3 redundant places. [2024-11-17 03:41:08,571 INFO L231 Difference]: Finished difference. Result has 81 places, 59 transitions, 378 flow [2024-11-17 03:41:08,572 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=189, PETRI_DIFFERENCE_MINUEND_PLACES=54, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=46, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=5, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=34, PETRI_DIFFERENCE_SUBTRAHEND_STATES=17, PETRI_FLOW=378, PETRI_PLACES=81, PETRI_TRANSITIONS=59} [2024-11-17 03:41:08,572 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 36 predicate places. [2024-11-17 03:41:08,573 INFO L471 AbstractCegarLoop]: Abstraction has has 81 places, 59 transitions, 378 flow [2024-11-17 03:41:08,573 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 16.652173913043477) internal successors, (383), 23 states have internal predecessors, (383), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:08,573 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:08,573 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:08,593 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-17 03:41:08,777 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:08,777 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:08,778 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:08,778 INFO L85 PathProgramCache]: Analyzing trace with hash -2011973222, now seen corresponding path program 3 times [2024-11-17 03:41:08,778 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:08,778 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [427158560] [2024-11-17 03:41:08,778 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:08,778 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:08,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:09,208 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:09,209 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:09,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [427158560] [2024-11-17 03:41:09,209 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [427158560] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:09,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [342829837] [2024-11-17 03:41:09,209 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-17 03:41:09,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:09,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:09,211 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-17 03:41:09,212 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-17 03:41:09,308 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-17 03:41:09,309 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:09,310 INFO L255 TraceCheckSpWp]: Trace formula consists of 176 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 03:41:09,312 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:09,407 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-17 03:41:09,407 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:09,449 INFO L349 Elim1Store]: treesize reduction 5, result has 37.5 percent of original size [2024-11-17 03:41:09,449 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 25 treesize of output 12 [2024-11-17 03:41:09,476 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-17 03:41:09,477 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [342829837] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:09,477 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:09,477 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 4, 4] total 13 [2024-11-17 03:41:09,477 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [506114945] [2024-11-17 03:41:09,477 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:09,478 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-17 03:41:09,480 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:09,481 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-17 03:41:09,481 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2024-11-17 03:41:09,538 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 14 out of 48 [2024-11-17 03:41:09,539 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 81 places, 59 transitions, 378 flow. Second operand has 14 states, 14 states have (on average 17.214285714285715) internal successors, (241), 14 states have internal predecessors, (241), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:09,539 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:09,539 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 14 of 48 [2024-11-17 03:41:09,539 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:09,967 INFO L124 PetriNetUnfolderBase]: 389/1032 cut-off events. [2024-11-17 03:41:09,967 INFO L125 PetriNetUnfolderBase]: For 2825/2825 co-relation queries the response was YES. [2024-11-17 03:41:09,972 INFO L83 FinitePrefix]: Finished finitePrefix Result has 3099 conditions, 1032 events. 389/1032 cut-off events. For 2825/2825 co-relation queries the response was YES. Maximal size of possible extension queue 50. Compared 5843 event pairs, 46 based on Foata normal form. 27/1052 useless extension candidates. Maximal degree in co-relation 2355. Up to 283 conditions per place. [2024-11-17 03:41:09,977 INFO L140 encePairwiseOnDemand]: 39/48 looper letters, 79 selfloop transitions, 20 changer transitions 0/112 dead transitions. [2024-11-17 03:41:09,978 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 90 places, 112 transitions, 873 flow [2024-11-17 03:41:09,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-17 03:41:09,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2024-11-17 03:41:09,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 260 transitions. [2024-11-17 03:41:09,979 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.4166666666666667 [2024-11-17 03:41:09,979 INFO L175 Difference]: Start difference. First operand has 81 places, 59 transitions, 378 flow. Second operand 13 states and 260 transitions. [2024-11-17 03:41:09,979 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 90 places, 112 transitions, 873 flow [2024-11-17 03:41:09,986 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 84 places, 112 transitions, 782 flow, removed 41 selfloop flow, removed 6 redundant places. [2024-11-17 03:41:09,988 INFO L231 Difference]: Finished difference. Result has 86 places, 61 transitions, 419 flow [2024-11-17 03:41:09,988 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=333, PETRI_DIFFERENCE_MINUEND_PLACES=72, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=58, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=17, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=40, PETRI_DIFFERENCE_SUBTRAHEND_STATES=13, PETRI_FLOW=419, PETRI_PLACES=86, PETRI_TRANSITIONS=61} [2024-11-17 03:41:09,989 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 41 predicate places. [2024-11-17 03:41:09,989 INFO L471 AbstractCegarLoop]: Abstraction has has 86 places, 61 transitions, 419 flow [2024-11-17 03:41:09,989 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 17.214285714285715) internal successors, (241), 14 states have internal predecessors, (241), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:09,989 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:09,989 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:10,009 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-17 03:41:10,193 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:10,194 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:10,194 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:10,194 INFO L85 PathProgramCache]: Analyzing trace with hash -32067111, now seen corresponding path program 1 times [2024-11-17 03:41:10,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:10,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [660455400] [2024-11-17 03:41:10,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:10,195 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:10,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:11,037 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:11,037 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:11,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [660455400] [2024-11-17 03:41:11,037 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [660455400] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:11,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1995933781] [2024-11-17 03:41:11,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:11,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:11,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:11,040 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-17 03:41:11,041 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-17 03:41:11,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:11,118 INFO L255 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-17 03:41:11,121 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:11,527 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2024-11-17 03:41:11,728 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:11,729 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:12,005 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:12,006 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 18 [2024-11-17 03:41:12,502 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:12,503 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1995933781] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:12,503 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:12,503 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 14] total 40 [2024-11-17 03:41:12,503 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1759188940] [2024-11-17 03:41:12,503 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:12,503 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 41 states [2024-11-17 03:41:12,504 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:12,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2024-11-17 03:41:12,505 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=206, Invalid=1434, Unknown=0, NotChecked=0, Total=1640 [2024-11-17 03:41:12,684 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:12,685 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 86 places, 61 transitions, 419 flow. Second operand has 41 states, 41 states have (on average 12.048780487804878) internal successors, (494), 41 states have internal predecessors, (494), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:12,685 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:12,686 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:12,686 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:16,054 INFO L124 PetriNetUnfolderBase]: 1122/2459 cut-off events. [2024-11-17 03:41:16,054 INFO L125 PetriNetUnfolderBase]: For 5437/5437 co-relation queries the response was YES. [2024-11-17 03:41:16,060 INFO L83 FinitePrefix]: Finished finitePrefix Result has 7455 conditions, 2459 events. 1122/2459 cut-off events. For 5437/5437 co-relation queries the response was YES. Maximal size of possible extension queue 94. Compared 15368 event pairs, 128 based on Foata normal form. 2/2461 useless extension candidates. Maximal degree in co-relation 5436. Up to 867 conditions per place. [2024-11-17 03:41:16,070 INFO L140 encePairwiseOnDemand]: 30/48 looper letters, 134 selfloop transitions, 100 changer transitions 87/326 dead transitions. [2024-11-17 03:41:16,070 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 138 places, 326 transitions, 2245 flow [2024-11-17 03:41:16,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2024-11-17 03:41:16,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 53 states. [2024-11-17 03:41:16,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 814 transitions. [2024-11-17 03:41:16,074 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.3199685534591195 [2024-11-17 03:41:16,074 INFO L175 Difference]: Start difference. First operand has 86 places, 61 transitions, 419 flow. Second operand 53 states and 814 transitions. [2024-11-17 03:41:16,074 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 138 places, 326 transitions, 2245 flow [2024-11-17 03:41:16,085 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 128 places, 326 transitions, 2156 flow, removed 18 selfloop flow, removed 10 redundant places. [2024-11-17 03:41:16,088 INFO L231 Difference]: Finished difference. Result has 146 places, 143 transitions, 1306 flow [2024-11-17 03:41:16,089 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=377, PETRI_DIFFERENCE_MINUEND_PLACES=76, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=61, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=30, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=23, PETRI_DIFFERENCE_SUBTRAHEND_STATES=53, PETRI_FLOW=1306, PETRI_PLACES=146, PETRI_TRANSITIONS=143} [2024-11-17 03:41:16,090 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 101 predicate places. [2024-11-17 03:41:16,090 INFO L471 AbstractCegarLoop]: Abstraction has has 146 places, 143 transitions, 1306 flow [2024-11-17 03:41:16,091 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 41 states, 41 states have (on average 12.048780487804878) internal successors, (494), 41 states have internal predecessors, (494), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:16,092 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:16,092 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:16,108 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-17 03:41:16,292 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-11-17 03:41:16,293 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:16,293 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:16,294 INFO L85 PathProgramCache]: Analyzing trace with hash -1465099235, now seen corresponding path program 2 times [2024-11-17 03:41:16,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:16,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1477838543] [2024-11-17 03:41:16,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:16,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:16,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:16,970 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:16,971 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:16,971 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1477838543] [2024-11-17 03:41:16,971 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1477838543] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:16,971 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1403938829] [2024-11-17 03:41:16,971 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-17 03:41:16,972 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:16,972 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:16,974 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-17 03:41:16,976 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-17 03:41:17,060 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-17 03:41:17,061 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:17,062 INFO L255 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-11-17 03:41:17,064 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:17,675 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:17,675 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:17,985 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:17,986 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 18 [2024-11-17 03:41:18,447 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:18,447 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1403938829] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:18,447 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:18,447 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 14] total 41 [2024-11-17 03:41:18,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [61700538] [2024-11-17 03:41:18,448 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:18,448 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2024-11-17 03:41:18,449 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:18,449 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2024-11-17 03:41:18,450 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=205, Invalid=1517, Unknown=0, NotChecked=0, Total=1722 [2024-11-17 03:41:18,575 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:18,576 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 146 places, 143 transitions, 1306 flow. Second operand has 42 states, 42 states have (on average 12.047619047619047) internal successors, (506), 42 states have internal predecessors, (506), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:18,576 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:18,576 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:18,576 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:20,291 INFO L124 PetriNetUnfolderBase]: 1086/2309 cut-off events. [2024-11-17 03:41:20,291 INFO L125 PetriNetUnfolderBase]: For 10887/10887 co-relation queries the response was YES. [2024-11-17 03:41:20,302 INFO L83 FinitePrefix]: Finished finitePrefix Result has 9466 conditions, 2309 events. 1086/2309 cut-off events. For 10887/10887 co-relation queries the response was YES. Maximal size of possible extension queue 90. Compared 13846 event pairs, 135 based on Foata normal form. 3/2299 useless extension candidates. Maximal degree in co-relation 9403. Up to 879 conditions per place. [2024-11-17 03:41:20,315 INFO L140 encePairwiseOnDemand]: 32/48 looper letters, 171 selfloop transitions, 76 changer transitions 33/285 dead transitions. [2024-11-17 03:41:20,315 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 164 places, 285 transitions, 2747 flow [2024-11-17 03:41:20,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-11-17 03:41:20,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 38 states. [2024-11-17 03:41:20,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 591 transitions. [2024-11-17 03:41:20,320 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.32401315789473684 [2024-11-17 03:41:20,320 INFO L175 Difference]: Start difference. First operand has 146 places, 143 transitions, 1306 flow. Second operand 38 states and 591 transitions. [2024-11-17 03:41:20,320 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 164 places, 285 transitions, 2747 flow [2024-11-17 03:41:20,350 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 150 places, 285 transitions, 2559 flow, removed 84 selfloop flow, removed 14 redundant places. [2024-11-17 03:41:20,354 INFO L231 Difference]: Finished difference. Result has 159 places, 149 transitions, 1523 flow [2024-11-17 03:41:20,354 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=1200, PETRI_DIFFERENCE_MINUEND_PLACES=113, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=143, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=62, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=73, PETRI_DIFFERENCE_SUBTRAHEND_STATES=38, PETRI_FLOW=1523, PETRI_PLACES=159, PETRI_TRANSITIONS=149} [2024-11-17 03:41:20,355 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 114 predicate places. [2024-11-17 03:41:20,355 INFO L471 AbstractCegarLoop]: Abstraction has has 159 places, 149 transitions, 1523 flow [2024-11-17 03:41:20,355 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 42 states have (on average 12.047619047619047) internal successors, (506), 42 states have internal predecessors, (506), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:20,356 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:20,356 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:20,370 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-17 03:41:20,556 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:20,557 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:20,557 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:20,557 INFO L85 PathProgramCache]: Analyzing trace with hash -1714258131, now seen corresponding path program 3 times [2024-11-17 03:41:20,557 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:20,557 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1112868581] [2024-11-17 03:41:20,557 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:20,558 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:20,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:21,248 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:21,249 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:21,249 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1112868581] [2024-11-17 03:41:21,249 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1112868581] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:21,249 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [52446579] [2024-11-17 03:41:21,249 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-17 03:41:21,249 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:21,249 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:21,250 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-17 03:41:21,252 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-17 03:41:21,321 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-17 03:41:21,321 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:21,323 INFO L255 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-17 03:41:21,325 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:21,644 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-17 03:41:21,644 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:21,839 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:21,839 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 21 [2024-11-17 03:41:21,946 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-17 03:41:21,946 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [52446579] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:21,946 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:21,947 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 11, 11] total 34 [2024-11-17 03:41:21,947 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1080354436] [2024-11-17 03:41:21,947 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:21,947 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-11-17 03:41:21,948 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:21,948 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-17 03:41:21,949 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=1064, Unknown=0, NotChecked=0, Total=1190 [2024-11-17 03:41:22,066 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:22,068 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 159 places, 149 transitions, 1523 flow. Second operand has 35 states, 35 states have (on average 12.0) internal successors, (420), 35 states have internal predecessors, (420), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:22,068 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:22,069 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:22,069 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:23,667 INFO L124 PetriNetUnfolderBase]: 1343/2851 cut-off events. [2024-11-17 03:41:23,667 INFO L125 PetriNetUnfolderBase]: For 15422/15440 co-relation queries the response was YES. [2024-11-17 03:41:23,682 INFO L83 FinitePrefix]: Finished finitePrefix Result has 12419 conditions, 2851 events. 1343/2851 cut-off events. For 15422/15440 co-relation queries the response was YES. Maximal size of possible extension queue 113. Compared 18228 event pairs, 101 based on Foata normal form. 8/2859 useless extension candidates. Maximal degree in co-relation 12346. Up to 599 conditions per place. [2024-11-17 03:41:23,694 INFO L140 encePairwiseOnDemand]: 31/48 looper letters, 198 selfloop transitions, 137 changer transitions 35/375 dead transitions. [2024-11-17 03:41:23,695 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 190 places, 375 transitions, 4105 flow [2024-11-17 03:41:23,695 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2024-11-17 03:41:23,695 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 40 states. [2024-11-17 03:41:23,696 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 635 transitions. [2024-11-17 03:41:23,696 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.3307291666666667 [2024-11-17 03:41:23,696 INFO L175 Difference]: Start difference. First operand has 159 places, 149 transitions, 1523 flow. Second operand 40 states and 635 transitions. [2024-11-17 03:41:23,697 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 190 places, 375 transitions, 4105 flow [2024-11-17 03:41:23,737 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 166 places, 375 transitions, 3903 flow, removed 35 selfloop flow, removed 24 redundant places. [2024-11-17 03:41:23,742 INFO L231 Difference]: Finished difference. Result has 178 places, 209 transitions, 2403 flow [2024-11-17 03:41:23,743 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=1370, PETRI_DIFFERENCE_MINUEND_PLACES=127, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=149, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=74, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=64, PETRI_DIFFERENCE_SUBTRAHEND_STATES=40, PETRI_FLOW=2403, PETRI_PLACES=178, PETRI_TRANSITIONS=209} [2024-11-17 03:41:23,743 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 133 predicate places. [2024-11-17 03:41:23,743 INFO L471 AbstractCegarLoop]: Abstraction has has 178 places, 209 transitions, 2403 flow [2024-11-17 03:41:23,744 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 12.0) internal successors, (420), 35 states have internal predecessors, (420), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:23,744 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:23,744 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:23,762 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-17 03:41:23,944 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:23,945 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:23,945 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:23,945 INFO L85 PathProgramCache]: Analyzing trace with hash -874897409, now seen corresponding path program 4 times [2024-11-17 03:41:23,945 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:23,946 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1120148524] [2024-11-17 03:41:23,946 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:23,946 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:23,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:24,614 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:24,615 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:24,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1120148524] [2024-11-17 03:41:24,615 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1120148524] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:24,615 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [765002024] [2024-11-17 03:41:24,615 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-17 03:41:24,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:24,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:24,617 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-17 03:41:24,618 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-17 03:41:24,700 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-17 03:41:24,700 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:24,702 INFO L255 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-17 03:41:24,703 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:25,131 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:25,132 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 23 treesize of output 15 [2024-11-17 03:41:25,438 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:25,438 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:25,679 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:25,679 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 18 [2024-11-17 03:41:26,129 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:26,130 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [765002024] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:26,130 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:26,130 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14, 14] total 41 [2024-11-17 03:41:26,130 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1635861351] [2024-11-17 03:41:26,130 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:26,130 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2024-11-17 03:41:26,131 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:26,131 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2024-11-17 03:41:26,132 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=214, Invalid=1508, Unknown=0, NotChecked=0, Total=1722 [2024-11-17 03:41:26,244 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:26,245 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 178 places, 209 transitions, 2403 flow. Second operand has 42 states, 42 states have (on average 12.0) internal successors, (504), 42 states have internal predecessors, (504), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:26,245 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:26,245 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:26,245 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:28,423 INFO L124 PetriNetUnfolderBase]: 1296/2734 cut-off events. [2024-11-17 03:41:28,424 INFO L125 PetriNetUnfolderBase]: For 19886/19902 co-relation queries the response was YES. [2024-11-17 03:41:28,437 INFO L83 FinitePrefix]: Finished finitePrefix Result has 13468 conditions, 2734 events. 1296/2734 cut-off events. For 19886/19902 co-relation queries the response was YES. Maximal size of possible extension queue 111. Compared 17165 event pairs, 173 based on Foata normal form. 11/2744 useless extension candidates. Maximal degree in co-relation 13399. Up to 1264 conditions per place. [2024-11-17 03:41:28,449 INFO L140 encePairwiseOnDemand]: 32/48 looper letters, 167 selfloop transitions, 107 changer transitions 64/343 dead transitions. [2024-11-17 03:41:28,449 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 209 places, 343 transitions, 4007 flow [2024-11-17 03:41:28,450 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2024-11-17 03:41:28,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 40 states. [2024-11-17 03:41:28,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 594 transitions. [2024-11-17 03:41:28,452 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.309375 [2024-11-17 03:41:28,452 INFO L175 Difference]: Start difference. First operand has 178 places, 209 transitions, 2403 flow. Second operand 40 states and 594 transitions. [2024-11-17 03:41:28,452 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 209 places, 343 transitions, 4007 flow [2024-11-17 03:41:28,519 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 189 places, 343 transitions, 3820 flow, removed 72 selfloop flow, removed 20 redundant places. [2024-11-17 03:41:28,525 INFO L231 Difference]: Finished difference. Result has 205 places, 213 transitions, 2737 flow [2024-11-17 03:41:28,526 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=2262, PETRI_DIFFERENCE_MINUEND_PLACES=150, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=209, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=96, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=104, PETRI_DIFFERENCE_SUBTRAHEND_STATES=40, PETRI_FLOW=2737, PETRI_PLACES=205, PETRI_TRANSITIONS=213} [2024-11-17 03:41:28,526 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 160 predicate places. [2024-11-17 03:41:28,526 INFO L471 AbstractCegarLoop]: Abstraction has has 205 places, 213 transitions, 2737 flow [2024-11-17 03:41:28,527 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 42 states have (on average 12.0) internal successors, (504), 42 states have internal predecessors, (504), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:28,527 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:28,527 INFO L204 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:28,546 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-17 03:41:28,731 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,SelfDestructingSolverStorable15 [2024-11-17 03:41:28,732 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:28,732 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:28,732 INFO L85 PathProgramCache]: Analyzing trace with hash 1797798277, now seen corresponding path program 5 times [2024-11-17 03:41:28,732 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:28,732 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [45179792] [2024-11-17 03:41:28,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:28,732 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:28,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:29,707 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:29,707 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:29,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [45179792] [2024-11-17 03:41:29,708 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [45179792] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:29,708 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1079529134] [2024-11-17 03:41:29,708 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-17 03:41:29,708 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:29,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:29,710 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-17 03:41:29,712 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-17 03:41:29,788 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2024-11-17 03:41:29,788 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:29,789 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-17 03:41:29,791 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:30,160 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 03:41:30,160 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:30,352 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:30,353 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 21 [2024-11-17 03:41:30,451 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:30,452 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1079529134] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:30,452 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:30,452 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 13, 11] total 38 [2024-11-17 03:41:30,452 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1621629814] [2024-11-17 03:41:30,452 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:30,452 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 39 states [2024-11-17 03:41:30,453 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:30,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2024-11-17 03:41:30,454 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=1346, Unknown=0, NotChecked=0, Total=1482 [2024-11-17 03:41:30,587 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:30,588 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 205 places, 213 transitions, 2737 flow. Second operand has 39 states, 39 states have (on average 12.051282051282051) internal successors, (470), 39 states have internal predecessors, (470), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:30,588 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:30,588 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:30,588 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:32,198 INFO L124 PetriNetUnfolderBase]: 1427/3011 cut-off events. [2024-11-17 03:41:32,199 INFO L125 PetriNetUnfolderBase]: For 31488/31542 co-relation queries the response was YES. [2024-11-17 03:41:32,210 INFO L83 FinitePrefix]: Finished finitePrefix Result has 16131 conditions, 3011 events. 1427/3011 cut-off events. For 31488/31542 co-relation queries the response was YES. Maximal size of possible extension queue 115. Compared 19230 event pairs, 98 based on Foata normal form. 21/3032 useless extension candidates. Maximal degree in co-relation 16047. Up to 583 conditions per place. [2024-11-17 03:41:32,221 INFO L140 encePairwiseOnDemand]: 33/48 looper letters, 230 selfloop transitions, 130 changer transitions 33/398 dead transitions. [2024-11-17 03:41:32,221 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 218 places, 398 transitions, 5080 flow [2024-11-17 03:41:32,221 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2024-11-17 03:41:32,222 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2024-11-17 03:41:32,223 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 563 transitions. [2024-11-17 03:41:32,223 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.3351190476190476 [2024-11-17 03:41:32,223 INFO L175 Difference]: Start difference. First operand has 205 places, 213 transitions, 2737 flow. Second operand 35 states and 563 transitions. [2024-11-17 03:41:32,224 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 218 places, 398 transitions, 5080 flow [2024-11-17 03:41:32,314 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 190 places, 398 transitions, 4821 flow, removed 44 selfloop flow, removed 28 redundant places. [2024-11-17 03:41:32,320 INFO L231 Difference]: Finished difference. Result has 196 places, 234 transitions, 3121 flow [2024-11-17 03:41:32,320 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=2556, PETRI_DIFFERENCE_MINUEND_PLACES=156, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=213, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=106, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=106, PETRI_DIFFERENCE_SUBTRAHEND_STATES=35, PETRI_FLOW=3121, PETRI_PLACES=196, PETRI_TRANSITIONS=234} [2024-11-17 03:41:32,320 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 151 predicate places. [2024-11-17 03:41:32,321 INFO L471 AbstractCegarLoop]: Abstraction has has 196 places, 234 transitions, 3121 flow [2024-11-17 03:41:32,321 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 39 states, 39 states have (on average 12.051282051282051) internal successors, (470), 39 states have internal predecessors, (470), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:32,321 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:32,321 INFO L204 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:32,338 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-17 03:41:32,522 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2024-11-17 03:41:32,522 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:32,522 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:32,522 INFO L85 PathProgramCache]: Analyzing trace with hash 2143976115, now seen corresponding path program 6 times [2024-11-17 03:41:32,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:32,523 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [124200596] [2024-11-17 03:41:32,523 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:32,523 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:32,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:33,530 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:33,531 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:33,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [124200596] [2024-11-17 03:41:33,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [124200596] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:33,531 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [527393933] [2024-11-17 03:41:33,531 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-17 03:41:33,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:33,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:33,533 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-17 03:41:33,534 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-17 03:41:33,604 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2024-11-17 03:41:33,604 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:33,605 INFO L255 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-17 03:41:33,607 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:33,902 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:33,902 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:34,074 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:34,075 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 18 [2024-11-17 03:41:34,184 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:34,184 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [527393933] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:34,184 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:34,184 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 10, 10] total 34 [2024-11-17 03:41:34,184 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1271442579] [2024-11-17 03:41:34,184 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:34,184 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-11-17 03:41:34,185 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:34,185 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-17 03:41:34,186 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=1075, Unknown=0, NotChecked=0, Total=1190 [2024-11-17 03:41:34,348 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:34,349 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 196 places, 234 transitions, 3121 flow. Second operand has 35 states, 35 states have (on average 12.085714285714285) internal successors, (423), 35 states have internal predecessors, (423), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:34,349 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:34,349 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:34,349 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:35,979 INFO L124 PetriNetUnfolderBase]: 1398/2940 cut-off events. [2024-11-17 03:41:35,979 INFO L125 PetriNetUnfolderBase]: For 30810/30882 co-relation queries the response was YES. [2024-11-17 03:41:35,991 INFO L83 FinitePrefix]: Finished finitePrefix Result has 15972 conditions, 2940 events. 1398/2940 cut-off events. For 30810/30882 co-relation queries the response was YES. Maximal size of possible extension queue 114. Compared 18630 event pairs, 198 based on Foata normal form. 25/2965 useless extension candidates. Maximal degree in co-relation 15895. Up to 1166 conditions per place. [2024-11-17 03:41:36,004 INFO L140 encePairwiseOnDemand]: 31/48 looper letters, 175 selfloop transitions, 161 changer transitions 43/384 dead transitions. [2024-11-17 03:41:36,005 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 234 places, 384 transitions, 5051 flow [2024-11-17 03:41:36,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2024-11-17 03:41:36,005 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 40 states. [2024-11-17 03:41:36,006 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 620 transitions. [2024-11-17 03:41:36,007 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.3229166666666667 [2024-11-17 03:41:36,007 INFO L175 Difference]: Start difference. First operand has 196 places, 234 transitions, 3121 flow. Second operand 40 states and 620 transitions. [2024-11-17 03:41:36,007 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 234 places, 384 transitions, 5051 flow [2024-11-17 03:41:36,107 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 220 places, 384 transitions, 4919 flow, removed 32 selfloop flow, removed 14 redundant places. [2024-11-17 03:41:36,113 INFO L231 Difference]: Finished difference. Result has 224 places, 249 transitions, 3578 flow [2024-11-17 03:41:36,114 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=3011, PETRI_DIFFERENCE_MINUEND_PLACES=181, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=234, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=142, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=92, PETRI_DIFFERENCE_SUBTRAHEND_STATES=40, PETRI_FLOW=3578, PETRI_PLACES=224, PETRI_TRANSITIONS=249} [2024-11-17 03:41:36,114 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 179 predicate places. [2024-11-17 03:41:36,114 INFO L471 AbstractCegarLoop]: Abstraction has has 224 places, 249 transitions, 3578 flow [2024-11-17 03:41:36,115 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 12.085714285714285) internal successors, (423), 35 states have internal predecessors, (423), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:36,115 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:36,115 INFO L204 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:36,133 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-17 03:41:36,315 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,SelfDestructingSolverStorable17 [2024-11-17 03:41:36,316 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:36,316 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:36,316 INFO L85 PathProgramCache]: Analyzing trace with hash -462364603, now seen corresponding path program 7 times [2024-11-17 03:41:36,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:36,316 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484772627] [2024-11-17 03:41:36,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:36,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:36,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:37,268 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:37,268 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:37,268 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484772627] [2024-11-17 03:41:37,268 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1484772627] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:37,269 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [899710553] [2024-11-17 03:41:37,269 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-17 03:41:37,269 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:37,269 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:37,271 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-17 03:41:37,272 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-17 03:41:37,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:37,351 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-17 03:41:37,353 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:37,724 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-17 03:41:37,725 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:37,883 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-17 03:41:37,884 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 18 [2024-11-17 03:41:38,010 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:38,011 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [899710553] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:38,011 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:38,011 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 11, 10] total 34 [2024-11-17 03:41:38,011 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1998338365] [2024-11-17 03:41:38,011 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:38,012 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-11-17 03:41:38,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:38,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-17 03:41:38,013 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=1072, Unknown=0, NotChecked=0, Total=1190 [2024-11-17 03:41:38,290 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:38,291 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 224 places, 249 transitions, 3578 flow. Second operand has 35 states, 35 states have (on average 12.142857142857142) internal successors, (425), 35 states have internal predecessors, (425), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:38,291 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:38,291 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:38,291 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:39,537 INFO L124 PetriNetUnfolderBase]: 1441/2991 cut-off events. [2024-11-17 03:41:39,538 INFO L125 PetriNetUnfolderBase]: For 32031/32052 co-relation queries the response was YES. [2024-11-17 03:41:39,549 INFO L83 FinitePrefix]: Finished finitePrefix Result has 16841 conditions, 2991 events. 1441/2991 cut-off events. For 32031/32052 co-relation queries the response was YES. Maximal size of possible extension queue 103. Compared 18497 event pairs, 247 based on Foata normal form. 13/3003 useless extension candidates. Maximal degree in co-relation 16766. Up to 1505 conditions per place. [2024-11-17 03:41:39,566 INFO L140 encePairwiseOnDemand]: 31/48 looper letters, 173 selfloop transitions, 138 changer transitions 31/347 dead transitions. [2024-11-17 03:41:39,566 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 240 places, 347 transitions, 5032 flow [2024-11-17 03:41:39,566 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-17 03:41:39,566 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2024-11-17 03:41:39,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 418 transitions. [2024-11-17 03:41:39,567 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.32253086419753085 [2024-11-17 03:41:39,568 INFO L175 Difference]: Start difference. First operand has 224 places, 249 transitions, 3578 flow. Second operand 27 states and 418 transitions. [2024-11-17 03:41:39,568 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 240 places, 347 transitions, 5032 flow [2024-11-17 03:41:39,667 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 213 places, 347 transitions, 4842 flow, removed 19 selfloop flow, removed 27 redundant places. [2024-11-17 03:41:39,672 INFO L231 Difference]: Finished difference. Result has 220 places, 255 transitions, 3985 flow [2024-11-17 03:41:39,673 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=3410, PETRI_DIFFERENCE_MINUEND_PLACES=187, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=249, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=129, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=117, PETRI_DIFFERENCE_SUBTRAHEND_STATES=27, PETRI_FLOW=3985, PETRI_PLACES=220, PETRI_TRANSITIONS=255} [2024-11-17 03:41:39,673 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 175 predicate places. [2024-11-17 03:41:39,673 INFO L471 AbstractCegarLoop]: Abstraction has has 220 places, 255 transitions, 3985 flow [2024-11-17 03:41:39,674 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 35 states have (on average 12.142857142857142) internal successors, (425), 35 states have internal predecessors, (425), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:39,674 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:39,674 INFO L204 CegarLoopForPetriNet]: trace histogram [3, 3, 3, 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, 1, 1] [2024-11-17 03:41:39,690 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-17 03:41:39,878 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:39,879 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:39,879 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:39,879 INFO L85 PathProgramCache]: Analyzing trace with hash 1754670732, now seen corresponding path program 8 times [2024-11-17 03:41:39,879 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:39,879 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [323065724] [2024-11-17 03:41:39,879 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:39,879 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:39,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:40,043 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 13 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-17 03:41:40,043 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:40,043 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [323065724] [2024-11-17 03:41:40,043 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [323065724] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:40,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2030883256] [2024-11-17 03:41:40,044 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-17 03:41:40,044 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:40,044 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:40,046 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-17 03:41:40,047 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-17 03:41:40,127 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-17 03:41:40,127 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:40,128 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-17 03:41:40,130 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:40,359 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 15 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:40,359 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:40,646 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:40,646 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2030883256] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:40,646 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:40,647 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 22 [2024-11-17 03:41:40,647 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1505134026] [2024-11-17 03:41:40,647 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:40,647 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-11-17 03:41:40,647 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:40,648 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-17 03:41:40,648 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=397, Unknown=0, NotChecked=0, Total=506 [2024-11-17 03:41:40,695 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 16 out of 48 [2024-11-17 03:41:40,696 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 220 places, 255 transitions, 3985 flow. Second operand has 23 states, 23 states have (on average 18.869565217391305) internal successors, (434), 23 states have internal predecessors, (434), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:40,696 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:40,696 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 16 of 48 [2024-11-17 03:41:40,696 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:41,325 INFO L124 PetriNetUnfolderBase]: 890/2213 cut-off events. [2024-11-17 03:41:41,325 INFO L125 PetriNetUnfolderBase]: For 31840/31998 co-relation queries the response was YES. [2024-11-17 03:41:41,334 INFO L83 FinitePrefix]: Finished finitePrefix Result has 13413 conditions, 2213 events. 890/2213 cut-off events. For 31840/31998 co-relation queries the response was YES. Maximal size of possible extension queue 90. Compared 14855 event pairs, 117 based on Foata normal form. 62/2227 useless extension candidates. Maximal degree in co-relation 13342. Up to 633 conditions per place. [2024-11-17 03:41:41,343 INFO L140 encePairwiseOnDemand]: 40/48 looper letters, 152 selfloop transitions, 41 changer transitions 34/316 dead transitions. [2024-11-17 03:41:41,343 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 227 places, 316 transitions, 4832 flow [2024-11-17 03:41:41,344 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-17 03:41:41,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2024-11-17 03:41:41,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 305 transitions. [2024-11-17 03:41:41,345 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.4538690476190476 [2024-11-17 03:41:41,345 INFO L175 Difference]: Start difference. First operand has 220 places, 255 transitions, 3985 flow. Second operand 14 states and 305 transitions. [2024-11-17 03:41:41,345 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 227 places, 316 transitions, 4832 flow [2024-11-17 03:41:41,441 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 208 places, 316 transitions, 4744 flow, removed 15 selfloop flow, removed 19 redundant places. [2024-11-17 03:41:41,447 INFO L231 Difference]: Finished difference. Result has 209 places, 242 transitions, 3868 flow [2024-11-17 03:41:41,447 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=3882, PETRI_DIFFERENCE_MINUEND_PLACES=195, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=254, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=40, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=213, PETRI_DIFFERENCE_SUBTRAHEND_STATES=14, PETRI_FLOW=3868, PETRI_PLACES=209, PETRI_TRANSITIONS=242} [2024-11-17 03:41:41,448 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 164 predicate places. [2024-11-17 03:41:41,448 INFO L471 AbstractCegarLoop]: Abstraction has has 209 places, 242 transitions, 3868 flow [2024-11-17 03:41:41,448 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 18.869565217391305) internal successors, (434), 23 states have internal predecessors, (434), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:41,448 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:41,449 INFO L204 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 3, 2, 2, 2, 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-17 03:41:41,467 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-17 03:41:41,652 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:41,653 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:41,653 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:41,653 INFO L85 PathProgramCache]: Analyzing trace with hash -1775491332, now seen corresponding path program 9 times [2024-11-17 03:41:41,653 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:41,653 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1613895447] [2024-11-17 03:41:41,653 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:41,653 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:41,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:42,254 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 3 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:42,254 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:42,254 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1613895447] [2024-11-17 03:41:42,254 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1613895447] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:42,255 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [468200550] [2024-11-17 03:41:42,255 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-17 03:41:42,255 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:42,255 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:42,257 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-17 03:41:42,258 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-17 03:41:42,342 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2024-11-17 03:41:42,342 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:42,344 INFO L255 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-17 03:41:42,345 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:42,463 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:42,464 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:42,515 INFO L349 Elim1Store]: treesize reduction 5, result has 50.0 percent of original size [2024-11-17 03:41:42,515 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 14 [2024-11-17 03:41:42,536 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:42,536 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [468200550] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:42,536 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:42,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 6, 6] total 19 [2024-11-17 03:41:42,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1036342207] [2024-11-17 03:41:42,536 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:42,537 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-17 03:41:42,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:42,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-17 03:41:42,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=332, Unknown=0, NotChecked=0, Total=380 [2024-11-17 03:41:42,587 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 14 out of 48 [2024-11-17 03:41:42,588 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 209 places, 242 transitions, 3868 flow. Second operand has 20 states, 20 states have (on average 16.85) internal successors, (337), 20 states have internal predecessors, (337), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:42,588 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:42,588 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 14 of 48 [2024-11-17 03:41:42,588 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:45,765 INFO L124 PetriNetUnfolderBase]: 3840/8455 cut-off events. [2024-11-17 03:41:45,765 INFO L125 PetriNetUnfolderBase]: For 162514/163027 co-relation queries the response was YES. [2024-11-17 03:41:45,803 INFO L83 FinitePrefix]: Finished finitePrefix Result has 55266 conditions, 8455 events. 3840/8455 cut-off events. For 162514/163027 co-relation queries the response was YES. Maximal size of possible extension queue 236. Compared 65914 event pairs, 188 based on Foata normal form. 595/8979 useless extension candidates. Maximal degree in co-relation 55132. Up to 2110 conditions per place. [2024-11-17 03:41:45,937 INFO L140 encePairwiseOnDemand]: 39/48 looper letters, 752 selfloop transitions, 310 changer transitions 8/1135 dead transitions. [2024-11-17 03:41:45,938 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 242 places, 1135 transitions, 19172 flow [2024-11-17 03:41:45,938 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2024-11-17 03:41:45,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2024-11-17 03:41:45,940 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 1174 transitions. [2024-11-17 03:41:45,940 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.4529320987654321 [2024-11-17 03:41:45,941 INFO L175 Difference]: Start difference. First operand has 209 places, 242 transitions, 3868 flow. Second operand 54 states and 1174 transitions. [2024-11-17 03:41:45,943 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 242 places, 1135 transitions, 19172 flow [2024-11-17 03:41:46,273 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 226 places, 1135 transitions, 18949 flow, removed 25 selfloop flow, removed 16 redundant places. [2024-11-17 03:41:46,285 INFO L231 Difference]: Finished difference. Result has 265 places, 520 transitions, 10661 flow [2024-11-17 03:41:46,285 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=3730, PETRI_DIFFERENCE_MINUEND_PLACES=173, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=242, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=69, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=166, PETRI_DIFFERENCE_SUBTRAHEND_STATES=54, PETRI_FLOW=10661, PETRI_PLACES=265, PETRI_TRANSITIONS=520} [2024-11-17 03:41:46,286 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 220 predicate places. [2024-11-17 03:41:46,286 INFO L471 AbstractCegarLoop]: Abstraction has has 265 places, 520 transitions, 10661 flow [2024-11-17 03:41:46,286 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 16.85) internal successors, (337), 20 states have internal predecessors, (337), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:46,286 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:46,286 INFO L204 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 03:41:46,301 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-17 03:41:46,490 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,SelfDestructingSolverStorable20 [2024-11-17 03:41:46,491 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:46,491 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:46,491 INFO L85 PathProgramCache]: Analyzing trace with hash 1266135854, now seen corresponding path program 10 times [2024-11-17 03:41:46,491 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:46,492 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1593143659] [2024-11-17 03:41:46,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:46,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:46,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:46,571 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 15 proven. 2 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:46,572 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:46,572 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1593143659] [2024-11-17 03:41:46,572 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1593143659] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:46,572 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [798530578] [2024-11-17 03:41:46,572 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-17 03:41:46,572 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:46,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:46,574 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 03:41:46,576 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-17 03:41:46,646 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-17 03:41:46,646 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:46,647 INFO L255 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-17 03:41:46,649 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:46,699 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 15 proven. 2 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:46,699 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:46,842 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-17 03:41:46,842 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [798530578] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:46,842 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:46,843 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4, 6] total 9 [2024-11-17 03:41:46,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [302513311] [2024-11-17 03:41:46,843 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:46,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-17 03:41:46,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:46,844 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-17 03:41:46,844 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=54, Unknown=0, NotChecked=0, Total=90 [2024-11-17 03:41:46,844 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 17 out of 48 [2024-11-17 03:41:46,844 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 265 places, 520 transitions, 10661 flow. Second operand has 10 states, 10 states have (on average 20.9) internal successors, (209), 10 states have internal predecessors, (209), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:46,844 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:46,844 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 17 of 48 [2024-11-17 03:41:46,844 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand [2024-11-17 03:41:49,552 INFO L124 PetriNetUnfolderBase]: 4637/11191 cut-off events. [2024-11-17 03:41:49,552 INFO L125 PetriNetUnfolderBase]: For 436138/437635 co-relation queries the response was YES. [2024-11-17 03:41:49,655 INFO L83 FinitePrefix]: Finished finitePrefix Result has 88369 conditions, 11191 events. 4637/11191 cut-off events. For 436138/437635 co-relation queries the response was YES. Maximal size of possible extension queue 395. Compared 101183 event pairs, 557 based on Foata normal form. 398/11357 useless extension candidates. Maximal degree in co-relation 88195. Up to 3147 conditions per place. [2024-11-17 03:41:49,714 INFO L140 encePairwiseOnDemand]: 44/48 looper letters, 369 selfloop transitions, 233 changer transitions 13/736 dead transitions. [2024-11-17 03:41:49,715 INFO L145 encePairwiseOnDemand]: Finished differencePairwiseOnDemand. Result has 267 places, 736 transitions, 15819 flow [2024-11-17 03:41:49,715 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-17 03:41:49,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2024-11-17 03:41:49,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 143 transitions. [2024-11-17 03:41:49,716 INFO L512 CegarLoopForPetriNet]: DFA transition density 0.5958333333333333 [2024-11-17 03:41:49,716 INFO L175 Difference]: Start difference. First operand has 265 places, 520 transitions, 10661 flow. Second operand 5 states and 143 transitions. [2024-11-17 03:41:49,716 INFO L82 GeneralOperation]: Start removeRedundantFlow. Operand has 267 places, 736 transitions, 15819 flow [2024-11-17 03:41:51,673 INFO L88 GeneralOperation]: Finished removeRedundantFlow, result has has 250 places, 736 transitions, 14475 flow, removed 527 selfloop flow, removed 17 redundant places. [2024-11-17 03:41:51,683 INFO L231 Difference]: Finished difference. Result has 253 places, 655 transitions, 13616 flow [2024-11-17 03:41:51,684 INFO L260 CegarLoopForPetriNet]: {PETRI_ALPHABET=48, PETRI_DIFFERENCE_MINUEND_FLOW=9655, PETRI_DIFFERENCE_MINUEND_PLACES=246, PETRI_DIFFERENCE_MINUEND_TRANSITIONS=518, PETRI_DIFFERENCE_SUBTRAHEND_LETTERS_WITH_MORE_CHANGERS_THAN_LOOPERS=113, PETRI_DIFFERENCE_SUBTRAHEND_LOOPER_ONLY_LETTERS=323, PETRI_DIFFERENCE_SUBTRAHEND_STATES=5, PETRI_FLOW=13616, PETRI_PLACES=253, PETRI_TRANSITIONS=655} [2024-11-17 03:41:51,684 INFO L277 CegarLoopForPetriNet]: 45 programPoint places, 208 predicate places. [2024-11-17 03:41:51,684 INFO L471 AbstractCegarLoop]: Abstraction has has 253 places, 655 transitions, 13616 flow [2024-11-17 03:41:51,684 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 20.9) internal successors, (209), 10 states have internal predecessors, (209), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:51,684 INFO L196 CegarLoopForPetriNet]: Found error trace [2024-11-17 03:41:51,685 INFO L204 CegarLoopForPetriNet]: trace histogram [4, 3, 3, 3, 3, 3, 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] [2024-11-17 03:41:51,697 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-17 03:41:51,885 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:51,885 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONMEMORY_LEAK === [thread1Err2REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err3REQUIRES_VIOLATIONMEMORY_DEREFERENCE, thread1Err0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 15 more)] === [2024-11-17 03:41:51,885 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 03:41:51,886 INFO L85 PathProgramCache]: Analyzing trace with hash -1776692781, now seen corresponding path program 11 times [2024-11-17 03:41:51,886 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 03:41:51,886 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1913709890] [2024-11-17 03:41:51,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 03:41:51,886 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 03:41:51,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 03:41:53,053 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 3 proven. 35 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:53,053 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 03:41:53,053 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1913709890] [2024-11-17 03:41:53,053 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1913709890] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 03:41:53,053 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [266627565] [2024-11-17 03:41:53,053 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-17 03:41:53,053 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 03:41:53,053 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 03:41:53,055 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 03:41:53,056 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-17 03:41:53,130 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2024-11-17 03:41:53,130 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 03:41:53,131 INFO L255 TraceCheckSpWp]: Trace formula consists of 244 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-17 03:41:53,133 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 03:41:53,966 INFO L349 Elim1Store]: treesize reduction 16, result has 15.8 percent of original size [2024-11-17 03:41:53,967 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 35 treesize of output 13 [2024-11-17 03:41:54,061 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 38 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:54,061 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 03:41:54,634 INFO L349 Elim1Store]: treesize reduction 8, result has 82.2 percent of original size [2024-11-17 03:41:54,634 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 50 treesize of output 53 [2024-11-17 03:41:55,413 INFO L134 CoverageAnalysis]: Checked inductivity of 38 backedges. 0 proven. 38 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 03:41:55,413 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [266627565] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 03:41:55,413 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 03:41:55,413 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 19, 19] total 57 [2024-11-17 03:41:55,413 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2138653441] [2024-11-17 03:41:55,413 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 03:41:55,414 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 58 states [2024-11-17 03:41:55,414 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 03:41:55,414 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 58 interpolants. [2024-11-17 03:41:55,415 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=402, Invalid=2904, Unknown=0, NotChecked=0, Total=3306 [2024-11-17 03:41:55,571 INFO L467 CegarLoopForPetriNet]: Number of universal loopers: 10 out of 48 [2024-11-17 03:41:55,572 INFO L103 encePairwiseOnDemand]: Start differencePairwiseOnDemand. First operand has 253 places, 655 transitions, 13616 flow. Second operand has 58 states, 58 states have (on average 11.89655172413793) internal successors, (690), 58 states have internal predecessors, (690), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 03:41:55,572 INFO L112 encePairwiseOnDemand]: Universal subtrahend loopers provided by user. [2024-11-17 03:41:55,572 INFO L113 encePairwiseOnDemand]: Number of universal subtrahend loopers: 10 of 48 [2024-11-17 03:41:55,572 INFO L73 FinitePrefix]: Start finitePrefix. Operand will be constructed on-demand