./Ultimate.py --spec ../sv-benchmarks/c/properties/valid-memsafety.prp --file ../sv-benchmarks/c/memsafety-broom/sll-nested-sll-twice.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for memory safety (deref-memtrack) Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerMemDerefMemtrack.xml -i ../sv-benchmarks/c/memsafety-broom/sll-nested-sll-twice.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-64bit-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 64bit --witnessprinter.graph.data.programhash f6ffaa15235a1424658c74c69505398b6d7973f6f82933a9f22a2b097e3c0057 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-09 07:55:47,906 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 07:55:47,988 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-DerefFreeMemtrack-64bit-Automizer_Default.epf [2024-11-09 07:55:47,992 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 07:55:47,995 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 07:55:48,016 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 07:55:48,016 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 07:55:48,017 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 07:55:48,017 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 07:55:48,018 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 07:55:48,018 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 07:55:48,018 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 07:55:48,019 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 07:55:48,019 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 07:55:48,020 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 07:55:48,020 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 07:55:48,021 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 07:55:48,023 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 07:55:48,023 INFO L153 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2024-11-09 07:55:48,023 INFO L153 SettingsManager]: * Bitprecise bitfields=true [2024-11-09 07:55:48,024 INFO L153 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2024-11-09 07:55:48,028 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 07:55:48,029 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-09 07:55:48,029 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 07:55:48,029 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 07:55:48,029 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 07:55:48,030 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 07:55:48,030 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 07:55:48,030 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 07:55:48,030 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 07:55:48,031 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 07:55:48,031 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 07:55:48,032 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 07:55:48,032 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 07:55:48,036 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 07:55:48,036 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 07:55:48,036 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-09 07:55:48,037 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-09 07:55:48,037 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 07:55:48,037 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> f6ffaa15235a1424658c74c69505398b6d7973f6f82933a9f22a2b097e3c0057 [2024-11-09 07:55:48,328 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 07:55:48,360 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 07:55:48,364 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 07:55:48,366 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 07:55:48,367 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 07:55:48,368 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/memsafety-broom/sll-nested-sll-twice.i [2024-11-09 07:55:49,903 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 07:55:50,212 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 07:55:50,212 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/memsafety-broom/sll-nested-sll-twice.i [2024-11-09 07:55:50,238 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/57a6394c8/30fe79a7b5704741bdc8f30117e9882b/FLAG249840403 [2024-11-09 07:55:50,252 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/57a6394c8/30fe79a7b5704741bdc8f30117e9882b [2024-11-09 07:55:50,256 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 07:55:50,258 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 07:55:50,259 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 07:55:50,259 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 07:55:50,265 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 07:55:50,266 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,268 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@155c8ad5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50, skipping insertion in model container [2024-11-09 07:55:50,269 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,326 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 07:55:50,635 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 07:55:50,644 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 07:55:50,683 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 07:55:50,713 INFO L204 MainTranslator]: Completed translation [2024-11-09 07:55:50,713 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50 WrapperNode [2024-11-09 07:55:50,713 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 07:55:50,714 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 07:55:50,714 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 07:55:50,715 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 07:55:50,722 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,736 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,754 INFO L138 Inliner]: procedures = 122, calls = 43, calls flagged for inlining = 5, calls inlined = 5, statements flattened = 81 [2024-11-09 07:55:50,755 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 07:55:50,756 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 07:55:50,756 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 07:55:50,756 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 07:55:50,768 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,768 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,772 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,793 INFO L175 MemorySlicer]: Split 22 memory accesses to 1 slices as follows [22]. 100 percent of accesses are in the largest equivalence class. The 0 initializations are split as follows [0]. The 10 writes are split as follows [10]. [2024-11-09 07:55:50,793 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,793 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,802 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,806 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,810 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,811 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,814 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 07:55:50,816 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 07:55:50,816 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 07:55:50,816 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 07:55:50,819 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (1/1) ... [2024-11-09 07:55:50,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-09 07:55:50,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:55:50,857 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-09 07:55:50,864 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-09 07:55:50,916 INFO L130 BoogieDeclarations]: Found specification of procedure loop_internal [2024-11-09 07:55:50,916 INFO L138 BoogieDeclarations]: Found implementation of procedure loop_internal [2024-11-09 07:55:50,917 INFO L130 BoogieDeclarations]: Found specification of procedure alloc_and_zero_internal [2024-11-09 07:55:50,917 INFO L138 BoogieDeclarations]: Found implementation of procedure alloc_and_zero_internal [2024-11-09 07:55:50,917 INFO L130 BoogieDeclarations]: Found specification of procedure create_internal [2024-11-09 07:55:50,917 INFO L138 BoogieDeclarations]: Found implementation of procedure create_internal [2024-11-09 07:55:50,917 INFO L130 BoogieDeclarations]: Found specification of procedure alloc_and_zero [2024-11-09 07:55:50,918 INFO L138 BoogieDeclarations]: Found implementation of procedure alloc_and_zero [2024-11-09 07:55:50,918 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-09 07:55:50,918 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-09 07:55:50,918 INFO L130 BoogieDeclarations]: Found specification of procedure destroy_internal [2024-11-09 07:55:50,919 INFO L138 BoogieDeclarations]: Found implementation of procedure destroy_internal [2024-11-09 07:55:50,919 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-09 07:55:50,919 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-09 07:55:50,921 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 07:55:50,921 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 07:55:51,068 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 07:55:51,070 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 07:55:51,532 INFO L? ?]: Removed 126 outVars from TransFormulas that were not future-live. [2024-11-09 07:55:51,533 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 07:55:51,551 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 07:55:51,552 INFO L316 CfgBuilder]: Removed 6 assume(true) statements. [2024-11-09 07:55:51,552 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 07:55:51 BoogieIcfgContainer [2024-11-09 07:55:51,552 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 07:55:51,555 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 07:55:51,555 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 07:55:51,558 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 07:55:51,559 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 07:55:50" (1/3) ... [2024-11-09 07:55:51,559 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3920a58e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 07:55:51, skipping insertion in model container [2024-11-09 07:55:51,560 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 07:55:50" (2/3) ... [2024-11-09 07:55:51,560 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3920a58e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 07:55:51, skipping insertion in model container [2024-11-09 07:55:51,560 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 07:55:51" (3/3) ... [2024-11-09 07:55:51,561 INFO L112 eAbstractionObserver]: Analyzing ICFG sll-nested-sll-twice.i [2024-11-09 07:55:51,578 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:None NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 07:55:51,579 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 51 error locations. [2024-11-09 07:55:51,676 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 07:55:51,693 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;@9c05b8a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 07:55:51,694 INFO L334 AbstractCegarLoop]: Starting to check reachability of 51 error locations. [2024-11-09 07:55:51,713 INFO L276 IsEmpty]: Start isEmpty. Operand has 143 states, 74 states have (on average 1.8513513513513513) internal successors, (137), 125 states have internal predecessors, (137), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 07:55:51,723 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2024-11-09 07:55:51,725 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:51,726 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1] [2024-11-09 07:55:51,727 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:51,734 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:51,735 INFO L85 PathProgramCache]: Analyzing trace with hash 57486637, now seen corresponding path program 1 times [2024-11-09 07:55:51,745 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:51,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101328270] [2024-11-09 07:55:51,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:51,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:51,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:51,998 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-09 07:55:51,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:51,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101328270] [2024-11-09 07:55:52,000 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1101328270] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:55:52,002 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:55:52,002 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 07:55:52,004 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1215795302] [2024-11-09 07:55:52,005 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:55:52,008 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-09 07:55:52,009 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:52,036 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-09 07:55:52,037 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-09 07:55:52,040 INFO L87 Difference]: Start difference. First operand has 143 states, 74 states have (on average 1.8513513513513513) internal successors, (137), 125 states have internal predecessors, (137), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 07:55:52,203 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:52,203 INFO L93 Difference]: Finished difference Result 140 states and 152 transitions. [2024-11-09 07:55:52,205 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-09 07:55:52,206 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 5 [2024-11-09 07:55:52,206 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:52,214 INFO L225 Difference]: With dead ends: 140 [2024-11-09 07:55:52,214 INFO L226 Difference]: Without dead ends: 138 [2024-11-09 07:55:52,216 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-09 07:55:52,221 INFO L432 NwaCegarLoop]: 145 mSDtfsCounter, 3 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 242 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:52,223 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 242 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 07:55:52,241 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2024-11-09 07:55:52,267 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 138. [2024-11-09 07:55:52,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 73 states have (on average 1.726027397260274) internal successors, (126), 120 states have internal predecessors, (126), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 07:55:52,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 150 transitions. [2024-11-09 07:55:52,278 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 150 transitions. Word has length 5 [2024-11-09 07:55:52,278 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:52,278 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 150 transitions. [2024-11-09 07:55:52,279 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 07:55:52,279 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 150 transitions. [2024-11-09 07:55:52,279 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2024-11-09 07:55:52,279 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:52,279 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1] [2024-11-09 07:55:52,280 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 07:55:52,280 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting alloc_and_zeroErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:52,281 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:52,282 INFO L85 PathProgramCache]: Analyzing trace with hash 57486638, now seen corresponding path program 1 times [2024-11-09 07:55:52,282 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:52,283 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [876975676] [2024-11-09 07:55:52,283 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:52,283 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:52,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:52,419 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-09 07:55:52,420 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:52,420 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [876975676] [2024-11-09 07:55:52,420 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [876975676] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:55:52,421 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:55:52,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 07:55:52,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1159204235] [2024-11-09 07:55:52,421 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:55:52,422 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-09 07:55:52,423 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:52,424 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-09 07:55:52,425 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-09 07:55:52,425 INFO L87 Difference]: Start difference. First operand 138 states and 150 transitions. Second operand has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 07:55:52,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:52,506 INFO L93 Difference]: Finished difference Result 135 states and 147 transitions. [2024-11-09 07:55:52,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-09 07:55:52,506 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 5 [2024-11-09 07:55:52,506 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:52,508 INFO L225 Difference]: With dead ends: 135 [2024-11-09 07:55:52,508 INFO L226 Difference]: Without dead ends: 135 [2024-11-09 07:55:52,508 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-09 07:55:52,509 INFO L432 NwaCegarLoop]: 143 mSDtfsCounter, 3 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 246 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:52,510 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 246 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 07:55:52,512 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2024-11-09 07:55:52,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 135. [2024-11-09 07:55:52,524 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 73 states have (on average 1.6849315068493151) internal successors, (123), 117 states have internal predecessors, (123), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 07:55:52,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 147 transitions. [2024-11-09 07:55:52,530 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 147 transitions. Word has length 5 [2024-11-09 07:55:52,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:52,531 INFO L471 AbstractCegarLoop]: Abstraction has 135 states and 147 transitions. [2024-11-09 07:55:52,531 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 2 states have (on average 2.0) internal successors, (4), 3 states have internal predecessors, (4), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 07:55:52,531 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 147 transitions. [2024-11-09 07:55:52,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-09 07:55:52,532 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:52,532 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:55:52,532 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-09 07:55:52,532 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting alloc_and_zero_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:52,533 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:52,534 INFO L85 PathProgramCache]: Analyzing trace with hash 1628966071, now seen corresponding path program 1 times [2024-11-09 07:55:52,534 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:52,534 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [248298931] [2024-11-09 07:55:52,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:52,535 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:52,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:52,637 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:55:52,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:52,652 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-09 07:55:52,652 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:52,653 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [248298931] [2024-11-09 07:55:52,653 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [248298931] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:55:52,653 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:55:52,653 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 07:55:52,653 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1841171438] [2024-11-09 07:55:52,654 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:55:52,654 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 07:55:52,654 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:52,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 07:55:52,655 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 07:55:52,656 INFO L87 Difference]: Start difference. First operand 135 states and 147 transitions. Second operand has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 07:55:52,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:52,893 INFO L93 Difference]: Finished difference Result 147 states and 161 transitions. [2024-11-09 07:55:52,894 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 07:55:52,895 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-09 07:55:52,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:52,897 INFO L225 Difference]: With dead ends: 147 [2024-11-09 07:55:52,900 INFO L226 Difference]: Without dead ends: 147 [2024-11-09 07:55:52,901 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 07:55:52,902 INFO L432 NwaCegarLoop]: 119 mSDtfsCounter, 22 mSDsluCounter, 120 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 239 SdHoareTripleChecker+Invalid, 187 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:52,902 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 239 Invalid, 187 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 07:55:52,903 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2024-11-09 07:55:52,916 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 134. [2024-11-09 07:55:52,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 73 states have (on average 1.6712328767123288) internal successors, (122), 116 states have internal predecessors, (122), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 07:55:52,919 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 146 transitions. [2024-11-09 07:55:52,920 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 146 transitions. Word has length 15 [2024-11-09 07:55:52,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:52,920 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 146 transitions. [2024-11-09 07:55:52,920 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 07:55:52,921 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 146 transitions. [2024-11-09 07:55:52,921 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-09 07:55:52,921 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:52,921 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:55:52,922 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 07:55:52,922 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting alloc_and_zero_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:52,922 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:52,923 INFO L85 PathProgramCache]: Analyzing trace with hash 1628966072, now seen corresponding path program 1 times [2024-11-09 07:55:52,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:52,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [350235824] [2024-11-09 07:55:52,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:52,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:52,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:53,077 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:55:53,082 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:53,097 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-09 07:55:53,097 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:53,098 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [350235824] [2024-11-09 07:55:53,098 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [350235824] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:55:53,098 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:55:53,098 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 07:55:53,098 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1114791715] [2024-11-09 07:55:53,099 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:55:53,099 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-09 07:55:53,099 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:53,100 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-09 07:55:53,100 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 07:55:53,100 INFO L87 Difference]: Start difference. First operand 134 states and 146 transitions. Second operand has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 07:55:53,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:53,325 INFO L93 Difference]: Finished difference Result 146 states and 160 transitions. [2024-11-09 07:55:53,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-09 07:55:53,325 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2024-11-09 07:55:53,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:53,326 INFO L225 Difference]: With dead ends: 146 [2024-11-09 07:55:53,326 INFO L226 Difference]: Without dead ends: 146 [2024-11-09 07:55:53,327 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-09 07:55:53,328 INFO L432 NwaCegarLoop]: 119 mSDtfsCounter, 22 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 244 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:53,328 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 244 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 07:55:53,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-09 07:55:53,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 133. [2024-11-09 07:55:53,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 133 states, 73 states have (on average 1.6575342465753424) internal successors, (121), 115 states have internal predecessors, (121), 12 states have call successors, (12), 5 states have call predecessors, (12), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 07:55:53,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 133 states to 133 states and 145 transitions. [2024-11-09 07:55:53,346 INFO L78 Accepts]: Start accepts. Automaton has 133 states and 145 transitions. Word has length 15 [2024-11-09 07:55:53,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:53,347 INFO L471 AbstractCegarLoop]: Abstraction has 133 states and 145 transitions. [2024-11-09 07:55:53,348 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-09 07:55:53,348 INFO L276 IsEmpty]: Start isEmpty. Operand 133 states and 145 transitions. [2024-11-09 07:55:53,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-09 07:55:53,349 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:53,349 INFO L215 NwaCegarLoop]: trace histogram [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-09 07:55:53,349 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-09 07:55:53,349 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:53,350 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:53,350 INFO L85 PathProgramCache]: Analyzing trace with hash -614116727, now seen corresponding path program 1 times [2024-11-09 07:55:53,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:53,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [823791412] [2024-11-09 07:55:53,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:53,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:53,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:53,534 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:55:53,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:53,594 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:55:53,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:53,701 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:55:53,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:53,848 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-09 07:55:53,849 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:53,849 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [823791412] [2024-11-09 07:55:53,849 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [823791412] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:55:53,849 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:55:53,849 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2024-11-09 07:55:53,850 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [32149181] [2024-11-09 07:55:53,850 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:55:53,850 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 07:55:53,850 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:53,851 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 07:55:53,851 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-09 07:55:53,851 INFO L87 Difference]: Start difference. First operand 133 states and 145 transitions. Second operand has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 07:55:54,537 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:54,538 INFO L93 Difference]: Finished difference Result 169 states and 195 transitions. [2024-11-09 07:55:54,538 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 07:55:54,538 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 25 [2024-11-09 07:55:54,539 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:54,540 INFO L225 Difference]: With dead ends: 169 [2024-11-09 07:55:54,540 INFO L226 Difference]: Without dead ends: 169 [2024-11-09 07:55:54,540 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2024-11-09 07:55:54,541 INFO L432 NwaCegarLoop]: 93 mSDtfsCounter, 51 mSDsluCounter, 395 mSDsCounter, 0 mSdLazyCounter, 749 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 488 SdHoareTripleChecker+Invalid, 776 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 749 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:54,543 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 488 Invalid, 776 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 749 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-11-09 07:55:54,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2024-11-09 07:55:54,557 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 149. [2024-11-09 07:55:54,558 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 88 states have (on average 1.6590909090909092) internal successors, (146), 126 states have internal predecessors, (146), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (17), 17 states have call predecessors, (17), 13 states have call successors, (17) [2024-11-09 07:55:54,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 176 transitions. [2024-11-09 07:55:54,560 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 176 transitions. Word has length 25 [2024-11-09 07:55:54,560 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:54,560 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 176 transitions. [2024-11-09 07:55:54,560 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.111111111111111) internal successors, (19), 8 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 07:55:54,561 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 176 transitions. [2024-11-09 07:55:54,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-09 07:55:54,561 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:54,561 INFO L215 NwaCegarLoop]: trace histogram [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-09 07:55:54,562 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-09 07:55:54,562 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:54,562 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:54,563 INFO L85 PathProgramCache]: Analyzing trace with hash -614116726, now seen corresponding path program 1 times [2024-11-09 07:55:54,563 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:54,563 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [156553277] [2024-11-09 07:55:54,563 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:54,563 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:54,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:54,827 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:55:54,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:54,971 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:55:54,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:55,062 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:55:55,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:55,153 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-09 07:55:55,155 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:55,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [156553277] [2024-11-09 07:55:55,155 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [156553277] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:55:55,155 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:55:55,156 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2024-11-09 07:55:55,156 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1026945564] [2024-11-09 07:55:55,156 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:55:55,156 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-09 07:55:55,158 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:55,158 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 07:55:55,159 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-09 07:55:55,159 INFO L87 Difference]: Start difference. First operand 149 states and 176 transitions. Second operand has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 07:55:55,680 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:55,680 INFO L93 Difference]: Finished difference Result 187 states and 224 transitions. [2024-11-09 07:55:55,681 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 07:55:55,681 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 25 [2024-11-09 07:55:55,681 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:55,684 INFO L225 Difference]: With dead ends: 187 [2024-11-09 07:55:55,684 INFO L226 Difference]: Without dead ends: 187 [2024-11-09 07:55:55,684 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2024-11-09 07:55:55,686 INFO L432 NwaCegarLoop]: 123 mSDtfsCounter, 71 mSDsluCounter, 406 mSDsCounter, 0 mSdLazyCounter, 633 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 529 SdHoareTripleChecker+Invalid, 660 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 633 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:55,688 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 529 Invalid, 660 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 633 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-09 07:55:55,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 187 states. [2024-11-09 07:55:55,699 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 187 to 167. [2024-11-09 07:55:55,700 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 102 states have (on average 1.607843137254902) internal successors, (164), 140 states have internal predecessors, (164), 17 states have call successors, (17), 5 states have call predecessors, (17), 6 states have return successors, (24), 21 states have call predecessors, (24), 17 states have call successors, (24) [2024-11-09 07:55:55,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 205 transitions. [2024-11-09 07:55:55,702 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 205 transitions. Word has length 25 [2024-11-09 07:55:55,702 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:55,702 INFO L471 AbstractCegarLoop]: Abstraction has 167 states and 205 transitions. [2024-11-09 07:55:55,702 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 07:55:55,703 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 205 transitions. [2024-11-09 07:55:55,703 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-09 07:55:55,703 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:55,703 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:55:55,704 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-09 07:55:55,704 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting create_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:55,708 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:55,709 INFO L85 PathProgramCache]: Analyzing trace with hash -687002123, now seen corresponding path program 1 times [2024-11-09 07:55:55,709 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:55,709 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [691590669] [2024-11-09 07:55:55,709 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:55,709 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:55,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:55,848 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:55:55,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:55,861 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-09 07:55:55,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:55,904 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 07:55:55,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:55,968 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 07:55:55,968 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:55,968 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [691590669] [2024-11-09 07:55:55,969 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [691590669] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:55:55,969 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [144526870] [2024-11-09 07:55:55,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:55,969 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:55:55,970 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:55:55,971 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-09 07:55:55,976 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-09 07:55:56,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:56,081 INFO L255 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-09 07:55:56,090 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:55:56,145 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 6 treesize of output 5 [2024-11-09 07:55:56,194 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1))) is different from true [2024-11-09 07:55:56,229 INFO L349 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2024-11-09 07:55:56,229 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 14 [2024-11-09 07:55:56,240 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 4 not checked. [2024-11-09 07:55:56,240 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:55:56,404 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 07:55:56,405 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [144526870] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 07:55:56,405 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 07:55:56,405 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 6] total 11 [2024-11-09 07:55:56,406 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1168817802] [2024-11-09 07:55:56,406 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 07:55:56,406 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-09 07:55:56,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:56,407 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-09 07:55:56,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=84, Unknown=1, NotChecked=18, Total=132 [2024-11-09 07:55:56,407 INFO L87 Difference]: Start difference. First operand 167 states and 205 transitions. Second operand has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 9 states have internal predecessors, (32), 2 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 07:55:56,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:56,908 INFO L93 Difference]: Finished difference Result 181 states and 223 transitions. [2024-11-09 07:55:56,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 07:55:56,909 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 9 states have internal predecessors, (32), 2 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 28 [2024-11-09 07:55:56,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:56,910 INFO L225 Difference]: With dead ends: 181 [2024-11-09 07:55:56,910 INFO L226 Difference]: Without dead ends: 181 [2024-11-09 07:55:56,911 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 55 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=188, Unknown=1, NotChecked=28, Total=272 [2024-11-09 07:55:56,912 INFO L432 NwaCegarLoop]: 107 mSDtfsCounter, 93 mSDsluCounter, 370 mSDsCounter, 0 mSdLazyCounter, 509 mSolverCounterSat, 36 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 477 SdHoareTripleChecker+Invalid, 712 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 36 IncrementalHoareTripleChecker+Valid, 509 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 167 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:56,913 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 477 Invalid, 712 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [36 Valid, 509 Invalid, 0 Unknown, 167 Unchecked, 0.4s Time] [2024-11-09 07:55:56,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2024-11-09 07:55:56,922 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 168. [2024-11-09 07:55:56,926 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 168 states, 103 states have (on average 1.6019417475728155) internal successors, (165), 140 states have internal predecessors, (165), 18 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (25), 22 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-09 07:55:56,927 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 168 states to 168 states and 208 transitions. [2024-11-09 07:55:56,927 INFO L78 Accepts]: Start accepts. Automaton has 168 states and 208 transitions. Word has length 28 [2024-11-09 07:55:56,927 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:56,927 INFO L471 AbstractCegarLoop]: Abstraction has 168 states and 208 transitions. [2024-11-09 07:55:56,928 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.909090909090909) internal successors, (32), 9 states have internal predecessors, (32), 2 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-09 07:55:56,928 INFO L276 IsEmpty]: Start isEmpty. Operand 168 states and 208 transitions. [2024-11-09 07:55:56,928 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-09 07:55:56,928 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:56,929 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:55:56,948 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-09 07:55:57,132 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:55:57,133 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting create_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:57,133 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:57,133 INFO L85 PathProgramCache]: Analyzing trace with hash -687002122, now seen corresponding path program 1 times [2024-11-09 07:55:57,133 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:57,133 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2005739784] [2024-11-09 07:55:57,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:57,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:57,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:57,304 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:55:57,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:57,313 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-09 07:55:57,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:57,386 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 07:55:57,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:57,453 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 07:55:57,453 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:57,453 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2005739784] [2024-11-09 07:55:57,454 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2005739784] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:55:57,454 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [887421329] [2024-11-09 07:55:57,454 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:57,454 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:55:57,454 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:55:57,456 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-09 07:55:57,459 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-09 07:55:57,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:57,555 INFO L255 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-09 07:55:57,558 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:55:57,573 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 6 treesize of output 5 [2024-11-09 07:55:57,663 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= (store |c_old(#length)| alloc_and_zero_internal_~pi~1.base 8) |c_#length|)) is different from true [2024-11-09 07:55:57,683 INFO L349 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2024-11-09 07:55:57,684 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 14 [2024-11-09 07:55:57,696 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 4 not checked. [2024-11-09 07:55:57,696 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:55:57,785 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [887421329] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:55:57,785 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:55:57,785 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 14 [2024-11-09 07:55:57,785 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1960772000] [2024-11-09 07:55:57,785 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:55:57,786 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 07:55:57,786 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:55:57,786 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 07:55:57,787 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=199, Unknown=1, NotChecked=28, Total=272 [2024-11-09 07:55:57,787 INFO L87 Difference]: Start difference. First operand 168 states and 208 transitions. Second operand has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 11 states have internal predecessors, (33), 3 states have call successors, (7), 3 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 07:55:58,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:55:58,345 INFO L93 Difference]: Finished difference Result 183 states and 224 transitions. [2024-11-09 07:55:58,345 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 07:55:58,346 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 11 states have internal predecessors, (33), 3 states have call successors, (7), 3 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) Word has length 28 [2024-11-09 07:55:58,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:55:58,347 INFO L225 Difference]: With dead ends: 183 [2024-11-09 07:55:58,347 INFO L226 Difference]: Without dead ends: 183 [2024-11-09 07:55:58,347 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 26 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=67, Invalid=316, Unknown=1, NotChecked=36, Total=420 [2024-11-09 07:55:58,348 INFO L432 NwaCegarLoop]: 110 mSDtfsCounter, 76 mSDsluCounter, 489 mSDsCounter, 0 mSdLazyCounter, 622 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 599 SdHoareTripleChecker+Invalid, 815 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 622 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 168 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-09 07:55:58,348 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [76 Valid, 599 Invalid, 815 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 622 Invalid, 0 Unknown, 168 Unchecked, 0.4s Time] [2024-11-09 07:55:58,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2024-11-09 07:55:58,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 170. [2024-11-09 07:55:58,356 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 105 states have (on average 1.5809523809523809) internal successors, (166), 142 states have internal predecessors, (166), 18 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (25), 22 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-09 07:55:58,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 209 transitions. [2024-11-09 07:55:58,357 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 209 transitions. Word has length 28 [2024-11-09 07:55:58,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:55:58,358 INFO L471 AbstractCegarLoop]: Abstraction has 170 states and 209 transitions. [2024-11-09 07:55:58,358 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 2.357142857142857) internal successors, (33), 11 states have internal predecessors, (33), 3 states have call successors, (7), 3 states have call predecessors, (7), 5 states have return successors, (5), 4 states have call predecessors, (5), 3 states have call successors, (5) [2024-11-09 07:55:58,358 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 209 transitions. [2024-11-09 07:55:58,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-09 07:55:58,359 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:55:58,359 INFO L215 NwaCegarLoop]: 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, 1, 1, 1, 1] [2024-11-09 07:55:58,372 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-09 07:55:58,560 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,SelfDestructingSolverStorable7 [2024-11-09 07:55:58,560 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:55:58,560 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:55:58,561 INFO L85 PathProgramCache]: Analyzing trace with hash -742476013, now seen corresponding path program 1 times [2024-11-09 07:55:58,561 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:55:58,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [182317283] [2024-11-09 07:55:58,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:58,561 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:55:58,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:58,707 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:55:58,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:58,742 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:55:58,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:58,935 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:55:58,939 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:59,031 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 07:55:59,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:59,284 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 07:55:59,284 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:55:59,284 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [182317283] [2024-11-09 07:55:59,285 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [182317283] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:55:59,285 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [498596673] [2024-11-09 07:55:59,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:55:59,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:55:59,285 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:55:59,287 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-09 07:55:59,298 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-09 07:55:59,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:55:59,397 INFO L255 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-09 07:55:59,399 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:55:59,404 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 6 treesize of output 5 [2024-11-09 07:55:59,446 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base (select |c_#valid| alloc_and_zero_internal_~pi~1.base))) (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0))) is different from true [2024-11-09 07:55:59,497 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1))) is different from true [2024-11-09 07:55:59,793 INFO L349 Elim1Store]: treesize reduction 104, result has 34.2 percent of original size [2024-11-09 07:55:59,794 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 9 case distinctions, treesize of input 40 treesize of output 104 [2024-11-09 07:56:00,011 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-09 07:56:00,021 INFO L349 Elim1Store]: treesize reduction 25, result has 16.7 percent of original size [2024-11-09 07:56:00,021 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 22 treesize of output 12 [2024-11-09 07:56:00,058 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 07:56:00,093 INFO L349 Elim1Store]: treesize reduction 425, result has 0.2 percent of original size [2024-11-09 07:56:00,094 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 5 select indices, 5 select index equivalence classes, 2 disjoint index pairs (out of 10 index pairs), introduced 8 new quantified variables, introduced 19 case distinctions, treesize of input 75 treesize of output 1 [2024-11-09 07:56:00,257 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 6 not checked. [2024-11-09 07:56:00,258 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:00,335 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [498596673] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:00,335 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:56:00,335 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 9] total 17 [2024-11-09 07:56:00,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1354692685] [2024-11-09 07:56:00,336 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:00,336 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-09 07:56:00,336 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:00,337 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-09 07:56:00,337 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=222, Unknown=2, NotChecked=62, Total=342 [2024-11-09 07:56:00,337 INFO L87 Difference]: Start difference. First operand 170 states and 209 transitions. Second operand has 18 states, 17 states have (on average 2.9411764705882355) internal successors, (50), 15 states have internal predecessors, (50), 6 states have call successors, (8), 3 states have call predecessors, (8), 7 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-09 07:56:01,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:01,404 INFO L93 Difference]: Finished difference Result 204 states and 257 transitions. [2024-11-09 07:56:01,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 07:56:01,405 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 2.9411764705882355) internal successors, (50), 15 states have internal predecessors, (50), 6 states have call successors, (8), 3 states have call predecessors, (8), 7 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 37 [2024-11-09 07:56:01,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:01,407 INFO L225 Difference]: With dead ends: 204 [2024-11-09 07:56:01,407 INFO L226 Difference]: Without dead ends: 204 [2024-11-09 07:56:01,408 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 41 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=77, Invalid=309, Unknown=2, NotChecked=74, Total=462 [2024-11-09 07:56:01,410 INFO L432 NwaCegarLoop]: 87 mSDtfsCounter, 99 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 1004 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 99 SdHoareTripleChecker+Valid, 633 SdHoareTripleChecker+Invalid, 1451 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 1004 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 406 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:01,411 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [99 Valid, 633 Invalid, 1451 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 1004 Invalid, 0 Unknown, 406 Unchecked, 0.8s Time] [2024-11-09 07:56:01,411 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2024-11-09 07:56:01,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 177. [2024-11-09 07:56:01,444 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 177 states, 111 states have (on average 1.5675675675675675) internal successors, (174), 148 states have internal predecessors, (174), 18 states have call successors, (18), 5 states have call predecessors, (18), 7 states have return successors, (32), 23 states have call predecessors, (32), 18 states have call successors, (32) [2024-11-09 07:56:01,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 224 transitions. [2024-11-09 07:56:01,445 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 224 transitions. Word has length 37 [2024-11-09 07:56:01,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:01,446 INFO L471 AbstractCegarLoop]: Abstraction has 177 states and 224 transitions. [2024-11-09 07:56:01,446 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 2.9411764705882355) internal successors, (50), 15 states have internal predecessors, (50), 6 states have call successors, (8), 3 states have call predecessors, (8), 7 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-11-09 07:56:01,446 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 224 transitions. [2024-11-09 07:56:01,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-11-09 07:56:01,447 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:01,447 INFO L215 NwaCegarLoop]: 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, 1, 1, 1, 1] [2024-11-09 07:56:01,467 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-09 07:56:01,651 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:01,653 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:01,654 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:01,654 INFO L85 PathProgramCache]: Analyzing trace with hash -742476012, now seen corresponding path program 1 times [2024-11-09 07:56:01,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:01,655 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [985363880] [2024-11-09 07:56:01,655 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:01,655 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:01,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:01,900 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:01,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:01,975 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:01,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:02,198 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:02,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:02,324 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 07:56:02,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:02,524 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 07:56:02,525 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:02,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [985363880] [2024-11-09 07:56:02,525 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [985363880] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:02,525 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1074247805] [2024-11-09 07:56:02,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:02,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:02,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:02,527 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-09 07:56:02,546 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-09 07:56:02,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:02,649 INFO L255 TraceCheckSpWp]: Trace formula consists of 223 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-09 07:56:02,652 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:02,664 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 6 treesize of output 5 [2024-11-09 07:56:02,669 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 8 treesize of output 1 [2024-11-09 07:56:02,983 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= (store |c_old(#length)| alloc_and_zero_internal_~pi~1.base (select |c_#length| alloc_and_zero_internal_~pi~1.base)) |c_#length|) (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0))) is different from true [2024-11-09 07:56:03,129 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 07:56:03,131 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 07:56:03,133 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 9 [2024-11-09 07:56:03,149 INFO L349 Elim1Store]: treesize reduction 8, result has 52.9 percent of original size [2024-11-09 07:56:03,150 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 18 [2024-11-09 07:56:03,176 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 4 not checked. [2024-11-09 07:56:03,177 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:03,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1074247805] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:03,407 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:56:03,407 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 26 [2024-11-09 07:56:03,407 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1840802315] [2024-11-09 07:56:03,407 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:03,407 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-09 07:56:03,408 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:03,408 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-09 07:56:03,409 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=649, Unknown=1, NotChecked=52, Total=812 [2024-11-09 07:56:03,409 INFO L87 Difference]: Start difference. First operand 177 states and 224 transitions. Second operand has 27 states, 24 states have (on average 2.3333333333333335) internal successors, (56), 20 states have internal predecessors, (56), 7 states have call successors, (8), 3 states have call predecessors, (8), 8 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-09 07:56:04,407 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:04,407 INFO L93 Difference]: Finished difference Result 226 states and 286 transitions. [2024-11-09 07:56:04,408 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 07:56:04,408 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 24 states have (on average 2.3333333333333335) internal successors, (56), 20 states have internal predecessors, (56), 7 states have call successors, (8), 3 states have call predecessors, (8), 8 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) Word has length 37 [2024-11-09 07:56:04,408 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:04,409 INFO L225 Difference]: With dead ends: 226 [2024-11-09 07:56:04,409 INFO L226 Difference]: Without dead ends: 226 [2024-11-09 07:56:04,410 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 31 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 271 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=141, Invalid=854, Unknown=1, NotChecked=60, Total=1056 [2024-11-09 07:56:04,411 INFO L432 NwaCegarLoop]: 96 mSDtfsCounter, 191 mSDsluCounter, 550 mSDsCounter, 0 mSdLazyCounter, 1226 mSolverCounterSat, 69 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 191 SdHoareTripleChecker+Valid, 646 SdHoareTripleChecker+Invalid, 1523 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 69 IncrementalHoareTripleChecker+Valid, 1226 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 228 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:04,411 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [191 Valid, 646 Invalid, 1523 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [69 Valid, 1226 Invalid, 0 Unknown, 228 Unchecked, 0.8s Time] [2024-11-09 07:56:04,412 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2024-11-09 07:56:04,418 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 173. [2024-11-09 07:56:04,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 173 states, 108 states have (on average 1.5740740740740742) internal successors, (170), 145 states have internal predecessors, (170), 18 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (25), 22 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-09 07:56:04,419 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 173 states to 173 states and 213 transitions. [2024-11-09 07:56:04,420 INFO L78 Accepts]: Start accepts. Automaton has 173 states and 213 transitions. Word has length 37 [2024-11-09 07:56:04,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:04,420 INFO L471 AbstractCegarLoop]: Abstraction has 173 states and 213 transitions. [2024-11-09 07:56:04,420 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 24 states have (on average 2.3333333333333335) internal successors, (56), 20 states have internal predecessors, (56), 7 states have call successors, (8), 3 states have call predecessors, (8), 8 states have return successors, (8), 8 states have call predecessors, (8), 7 states have call successors, (8) [2024-11-09 07:56:04,420 INFO L276 IsEmpty]: Start isEmpty. Operand 173 states and 213 transitions. [2024-11-09 07:56:04,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-09 07:56:04,421 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:04,421 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-09 07:56:04,439 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-09 07:56:04,625 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:04,626 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting create_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:04,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:04,626 INFO L85 PathProgramCache]: Analyzing trace with hash -2117597909, now seen corresponding path program 1 times [2024-11-09 07:56:04,626 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:04,626 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1739970574] [2024-11-09 07:56:04,627 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:04,627 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:04,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:04,783 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:04,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:04,790 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-09 07:56:04,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:04,794 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 07:56:04,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:04,820 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-09 07:56:04,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:04,878 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 11 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 07:56:04,879 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:04,879 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1739970574] [2024-11-09 07:56:04,879 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1739970574] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:04,879 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [135211861] [2024-11-09 07:56:04,879 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:04,879 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:04,880 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:04,881 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-09 07:56:04,883 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-09 07:56:05,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:05,019 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 07:56:05,023 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:05,029 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 6 treesize of output 5 [2024-11-09 07:56:05,040 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 1 [2024-11-09 07:56:05,046 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 17 treesize of output 9 [2024-11-09 07:56:05,070 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1))) is different from true [2024-11-09 07:56:05,085 INFO L349 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2024-11-09 07:56:05,086 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 14 [2024-11-09 07:56:05,096 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 13 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 4 not checked. [2024-11-09 07:56:05,096 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:05,217 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 13 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 07:56:05,217 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [135211861] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 07:56:05,217 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 07:56:05,217 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9, 8] total 13 [2024-11-09 07:56:05,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1140321302] [2024-11-09 07:56:05,217 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:05,218 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-11-09 07:56:05,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:05,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-11-09 07:56:05,218 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=126, Unknown=1, NotChecked=22, Total=182 [2024-11-09 07:56:05,219 INFO L87 Difference]: Start difference. First operand 173 states and 213 transitions. Second operand has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 11 states have internal predecessors, (42), 2 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-09 07:56:05,743 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:05,743 INFO L93 Difference]: Finished difference Result 188 states and 236 transitions. [2024-11-09 07:56:05,743 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 07:56:05,743 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 11 states have internal predecessors, (42), 2 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 40 [2024-11-09 07:56:05,744 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:05,745 INFO L225 Difference]: With dead ends: 188 [2024-11-09 07:56:05,745 INFO L226 Difference]: Without dead ends: 188 [2024-11-09 07:56:05,745 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 81 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=69, Invalid=314, Unknown=1, NotChecked=36, Total=420 [2024-11-09 07:56:05,746 INFO L432 NwaCegarLoop]: 116 mSDtfsCounter, 101 mSDsluCounter, 478 mSDsCounter, 0 mSdLazyCounter, 672 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 594 SdHoareTripleChecker+Invalid, 871 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 672 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 165 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:05,746 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [101 Valid, 594 Invalid, 871 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 672 Invalid, 0 Unknown, 165 Unchecked, 0.4s Time] [2024-11-09 07:56:05,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2024-11-09 07:56:05,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 172. [2024-11-09 07:56:05,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 172 states, 108 states have (on average 1.5648148148148149) internal successors, (169), 144 states have internal predecessors, (169), 18 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (25), 22 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-09 07:56:05,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 212 transitions. [2024-11-09 07:56:05,753 INFO L78 Accepts]: Start accepts. Automaton has 172 states and 212 transitions. Word has length 40 [2024-11-09 07:56:05,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:05,753 INFO L471 AbstractCegarLoop]: Abstraction has 172 states and 212 transitions. [2024-11-09 07:56:05,753 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 13 states have (on average 3.230769230769231) internal successors, (42), 11 states have internal predecessors, (42), 2 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-09 07:56:05,754 INFO L276 IsEmpty]: Start isEmpty. Operand 172 states and 212 transitions. [2024-11-09 07:56:05,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-09 07:56:05,757 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:05,757 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-09 07:56:05,773 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-09 07:56:05,957 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,SelfDestructingSolverStorable10 [2024-11-09 07:56:05,958 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting create_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:05,958 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:05,958 INFO L85 PathProgramCache]: Analyzing trace with hash -2117597908, now seen corresponding path program 1 times [2024-11-09 07:56:05,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:05,959 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2038737455] [2024-11-09 07:56:05,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:05,959 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:05,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:06,233 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:06,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:06,240 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2024-11-09 07:56:06,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:06,244 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 07:56:06,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:06,344 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-11-09 07:56:06,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:06,422 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 11 proven. 5 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 07:56:06,423 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:06,423 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2038737455] [2024-11-09 07:56:06,423 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2038737455] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:06,423 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [662431395] [2024-11-09 07:56:06,423 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:06,423 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:06,423 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:06,425 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-09 07:56:06,426 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-09 07:56:06,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:06,543 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-09 07:56:06,546 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:06,550 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 6 treesize of output 5 [2024-11-09 07:56:06,619 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 1 [2024-11-09 07:56:06,624 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 11 treesize of output 7 [2024-11-09 07:56:06,653 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 17 treesize of output 9 [2024-11-09 07:56:06,724 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= (store |c_old(#length)| alloc_and_zero_internal_~pi~1.base 8) |c_#length|)) is different from true [2024-11-09 07:56:06,741 INFO L349 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2024-11-09 07:56:06,741 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 12 treesize of output 14 [2024-11-09 07:56:06,765 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 13 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 4 not checked. [2024-11-09 07:56:06,766 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:07,069 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 13 proven. 5 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-09 07:56:07,069 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [662431395] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 07:56:07,070 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 07:56:07,070 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9, 9] total 27 [2024-11-09 07:56:07,070 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1411705406] [2024-11-09 07:56:07,070 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:07,071 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-09 07:56:07,071 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:07,071 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-09 07:56:07,072 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=628, Unknown=1, NotChecked=50, Total=756 [2024-11-09 07:56:07,072 INFO L87 Difference]: Start difference. First operand 172 states and 212 transitions. Second operand has 28 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 22 states have internal predecessors, (63), 4 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-09 07:56:08,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:08,305 INFO L93 Difference]: Finished difference Result 186 states and 234 transitions. [2024-11-09 07:56:08,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-09 07:56:08,306 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 22 states have internal predecessors, (63), 4 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 4 states have call successors, (8) Word has length 40 [2024-11-09 07:56:08,306 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:08,307 INFO L225 Difference]: With dead ends: 186 [2024-11-09 07:56:08,307 INFO L226 Difference]: Without dead ends: 186 [2024-11-09 07:56:08,307 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 69 SyntacticMatches, 3 SemanticMatches, 35 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 185 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=149, Invalid=1114, Unknown=1, NotChecked=68, Total=1332 [2024-11-09 07:56:08,308 INFO L432 NwaCegarLoop]: 117 mSDtfsCounter, 137 mSDsluCounter, 764 mSDsCounter, 0 mSdLazyCounter, 892 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 137 SdHoareTripleChecker+Valid, 881 SdHoareTripleChecker+Invalid, 1094 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 892 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 165 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:08,308 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [137 Valid, 881 Invalid, 1094 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 892 Invalid, 0 Unknown, 165 Unchecked, 0.8s Time] [2024-11-09 07:56:08,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2024-11-09 07:56:08,313 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 170. [2024-11-09 07:56:08,314 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 170 states, 108 states have (on average 1.5462962962962963) internal successors, (167), 142 states have internal predecessors, (167), 18 states have call successors, (18), 5 states have call predecessors, (18), 6 states have return successors, (25), 22 states have call predecessors, (25), 18 states have call successors, (25) [2024-11-09 07:56:08,315 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 170 states to 170 states and 210 transitions. [2024-11-09 07:56:08,315 INFO L78 Accepts]: Start accepts. Automaton has 170 states and 210 transitions. Word has length 40 [2024-11-09 07:56:08,315 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:08,315 INFO L471 AbstractCegarLoop]: Abstraction has 170 states and 210 transitions. [2024-11-09 07:56:08,315 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 22 states have internal predecessors, (63), 4 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (8), 7 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-09 07:56:08,316 INFO L276 IsEmpty]: Start isEmpty. Operand 170 states and 210 transitions. [2024-11-09 07:56:08,316 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-09 07:56:08,316 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:08,317 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:08,332 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-09 07:56:08,520 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:08,521 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting ULTIMATE.startErr16REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:08,521 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:08,521 INFO L85 PathProgramCache]: Analyzing trace with hash 43201550, now seen corresponding path program 1 times [2024-11-09 07:56:08,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:08,521 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1182395128] [2024-11-09 07:56:08,521 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:08,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:08,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:08,620 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:08,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:08,628 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:08,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:08,638 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:08,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:08,643 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:08,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:08,657 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:08,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:08,664 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 07:56:08,665 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:08,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1182395128] [2024-11-09 07:56:08,665 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1182395128] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:56:08,665 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:56:08,665 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-09 07:56:08,665 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1410177346] [2024-11-09 07:56:08,666 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:56:08,666 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-09 07:56:08,666 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:08,666 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-09 07:56:08,666 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-09 07:56:08,667 INFO L87 Difference]: Start difference. First operand 170 states and 210 transitions. Second operand has 7 states, 6 states have (on average 4.666666666666667) internal successors, (28), 6 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 07:56:08,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:08,929 INFO L93 Difference]: Finished difference Result 211 states and 271 transitions. [2024-11-09 07:56:08,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 07:56:08,929 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.666666666666667) internal successors, (28), 6 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Word has length 47 [2024-11-09 07:56:08,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:08,930 INFO L225 Difference]: With dead ends: 211 [2024-11-09 07:56:08,931 INFO L226 Difference]: Without dead ends: 211 [2024-11-09 07:56:08,931 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-09 07:56:08,932 INFO L432 NwaCegarLoop]: 86 mSDtfsCounter, 49 mSDsluCounter, 269 mSDsCounter, 0 mSdLazyCounter, 435 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 355 SdHoareTripleChecker+Invalid, 457 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 435 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:08,932 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 355 Invalid, 457 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 435 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 07:56:08,933 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 211 states. [2024-11-09 07:56:08,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 211 to 191. [2024-11-09 07:56:08,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 191 states, 129 states have (on average 1.5813953488372092) internal successors, (204), 159 states have internal predecessors, (204), 20 states have call successors, (20), 5 states have call predecessors, (20), 6 states have return successors, (29), 26 states have call predecessors, (29), 20 states have call successors, (29) [2024-11-09 07:56:08,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 191 states to 191 states and 253 transitions. [2024-11-09 07:56:08,943 INFO L78 Accepts]: Start accepts. Automaton has 191 states and 253 transitions. Word has length 47 [2024-11-09 07:56:08,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:08,943 INFO L471 AbstractCegarLoop]: Abstraction has 191 states and 253 transitions. [2024-11-09 07:56:08,943 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.666666666666667) internal successors, (28), 6 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 1 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 07:56:08,944 INFO L276 IsEmpty]: Start isEmpty. Operand 191 states and 253 transitions. [2024-11-09 07:56:08,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-09 07:56:08,944 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:08,945 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:08,945 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable12 [2024-11-09 07:56:08,946 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting ULTIMATE.startErr17REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:08,946 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:08,946 INFO L85 PathProgramCache]: Analyzing trace with hash 43201551, now seen corresponding path program 1 times [2024-11-09 07:56:08,946 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:08,946 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1223153507] [2024-11-09 07:56:08,946 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:08,947 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:08,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,151 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:09,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,196 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:09,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,206 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:09,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,212 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:09,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,223 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:09,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,228 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 07:56:09,229 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:09,229 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1223153507] [2024-11-09 07:56:09,229 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1223153507] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:56:09,229 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:56:09,229 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2024-11-09 07:56:09,229 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [601604399] [2024-11-09 07:56:09,229 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:56:09,230 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-09 07:56:09,230 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:09,230 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-09 07:56:09,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2024-11-09 07:56:09,231 INFO L87 Difference]: Start difference. First operand 191 states and 253 transitions. Second operand has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 07:56:09,607 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:09,608 INFO L93 Difference]: Finished difference Result 218 states and 281 transitions. [2024-11-09 07:56:09,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-09 07:56:09,608 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 47 [2024-11-09 07:56:09,608 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:09,609 INFO L225 Difference]: With dead ends: 218 [2024-11-09 07:56:09,609 INFO L226 Difference]: Without dead ends: 218 [2024-11-09 07:56:09,610 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=89, Unknown=0, NotChecked=0, Total=110 [2024-11-09 07:56:09,610 INFO L432 NwaCegarLoop]: 84 mSDtfsCounter, 43 mSDsluCounter, 534 mSDsCounter, 0 mSdLazyCounter, 587 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 618 SdHoareTripleChecker+Invalid, 603 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 587 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:09,610 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 618 Invalid, 603 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 587 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-09 07:56:09,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 218 states. [2024-11-09 07:56:09,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 218 to 201. [2024-11-09 07:56:09,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 201 states, 137 states have (on average 1.5547445255474452) internal successors, (213), 167 states have internal predecessors, (213), 22 states have call successors, (22), 5 states have call predecessors, (22), 6 states have return successors, (31), 28 states have call predecessors, (31), 22 states have call successors, (31) [2024-11-09 07:56:09,621 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 201 states to 201 states and 266 transitions. [2024-11-09 07:56:09,621 INFO L78 Accepts]: Start accepts. Automaton has 201 states and 266 transitions. Word has length 47 [2024-11-09 07:56:09,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:09,622 INFO L471 AbstractCegarLoop]: Abstraction has 201 states and 266 transitions. [2024-11-09 07:56:09,622 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 3.111111111111111) internal successors, (28), 8 states have internal predecessors, (28), 3 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 07:56:09,622 INFO L276 IsEmpty]: Start isEmpty. Operand 201 states and 266 transitions. [2024-11-09 07:56:09,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-09 07:56:09,626 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:09,626 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:09,626 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13 [2024-11-09 07:56:09,627 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting ULTIMATE.startErr22REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:09,627 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:09,627 INFO L85 PathProgramCache]: Analyzing trace with hash -1433023742, now seen corresponding path program 1 times [2024-11-09 07:56:09,627 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:09,627 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1308191036] [2024-11-09 07:56:09,627 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:09,627 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:09,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,733 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:09,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,772 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:09,775 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,781 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:09,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,786 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:09,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,801 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:09,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:09,806 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-09 07:56:09,806 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:09,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1308191036] [2024-11-09 07:56:09,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1308191036] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:56:09,806 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:56:09,806 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2024-11-09 07:56:09,807 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [712255471] [2024-11-09 07:56:09,807 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:56:09,807 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-09 07:56:09,807 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:09,808 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-09 07:56:09,808 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2024-11-09 07:56:09,808 INFO L87 Difference]: Start difference. First operand 201 states and 266 transitions. Second operand has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 07:56:10,055 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:10,055 INFO L93 Difference]: Finished difference Result 222 states and 293 transitions. [2024-11-09 07:56:10,056 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-09 07:56:10,056 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 49 [2024-11-09 07:56:10,056 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:10,057 INFO L225 Difference]: With dead ends: 222 [2024-11-09 07:56:10,057 INFO L226 Difference]: Without dead ends: 222 [2024-11-09 07:56:10,058 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2024-11-09 07:56:10,058 INFO L432 NwaCegarLoop]: 103 mSDtfsCounter, 52 mSDsluCounter, 587 mSDsCounter, 0 mSdLazyCounter, 378 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 690 SdHoareTripleChecker+Invalid, 388 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 378 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:10,058 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 690 Invalid, 388 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 378 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 07:56:10,059 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 222 states. [2024-11-09 07:56:10,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 222 to 202. [2024-11-09 07:56:10,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 202 states, 138 states have (on average 1.536231884057971) internal successors, (212), 168 states have internal predecessors, (212), 22 states have call successors, (22), 5 states have call predecessors, (22), 6 states have return successors, (31), 28 states have call predecessors, (31), 22 states have call successors, (31) [2024-11-09 07:56:10,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 202 states to 202 states and 265 transitions. [2024-11-09 07:56:10,069 INFO L78 Accepts]: Start accepts. Automaton has 202 states and 265 transitions. Word has length 49 [2024-11-09 07:56:10,069 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:10,069 INFO L471 AbstractCegarLoop]: Abstraction has 202 states and 265 transitions. [2024-11-09 07:56:10,070 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.3333333333333335) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 07:56:10,070 INFO L276 IsEmpty]: Start isEmpty. Operand 202 states and 265 transitions. [2024-11-09 07:56:10,070 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-09 07:56:10,071 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:10,071 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:10,071 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14 [2024-11-09 07:56:10,071 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:10,072 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:10,072 INFO L85 PathProgramCache]: Analyzing trace with hash 1593016213, now seen corresponding path program 1 times [2024-11-09 07:56:10,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:10,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1615189508] [2024-11-09 07:56:10,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:10,072 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:10,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:10,676 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:10,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:10,742 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:10,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:10,810 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:10,812 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:10,865 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:10,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:10,977 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:10,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:11,164 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 9 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 07:56:11,164 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:11,164 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1615189508] [2024-11-09 07:56:11,165 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1615189508] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:11,165 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [128268504] [2024-11-09 07:56:11,165 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:11,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:11,165 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:11,167 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-09 07:56:11,169 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-09 07:56:11,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:11,296 INFO L255 TraceCheckSpWp]: Trace formula consists of 291 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-11-09 07:56:11,300 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:11,345 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 6 treesize of output 5 [2024-11-09 07:56:11,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 1 [2024-11-09 07:56:11,517 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base (select |c_#valid| alloc_and_zero_internal_~pi~1.base))) (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0) (= |c_#memory_$Pointer$#0.base| (store |c_old(#memory_$Pointer$#0.base)| alloc_and_zero_internal_~pi~1.base (select |c_#memory_$Pointer$#0.base| alloc_and_zero_internal_~pi~1.base))))) is different from true [2024-11-09 07:56:11,585 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 07:56:11,586 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 15 [2024-11-09 07:56:11,621 INFO L349 Elim1Store]: treesize reduction 72, result has 30.1 percent of original size [2024-11-09 07:56:11,622 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 30 treesize of output 40 [2024-11-09 07:56:11,639 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 31 treesize of output 15 [2024-11-09 07:56:11,770 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 21 treesize of output 9 [2024-11-09 07:56:11,789 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 9 not checked. [2024-11-09 07:56:11,790 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:12,531 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [128268504] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:12,531 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:56:12,531 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 18] total 32 [2024-11-09 07:56:12,531 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1702071729] [2024-11-09 07:56:12,532 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:12,532 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-09 07:56:12,532 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:12,533 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-09 07:56:12,533 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1226, Unknown=1, NotChecked=70, Total=1406 [2024-11-09 07:56:12,533 INFO L87 Difference]: Start difference. First operand 202 states and 265 transitions. Second operand has 33 states, 29 states have (on average 2.3448275862068964) internal successors, (68), 25 states have internal predecessors, (68), 8 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (10), 9 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-09 07:56:14,553 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:14,553 INFO L93 Difference]: Finished difference Result 253 states and 330 transitions. [2024-11-09 07:56:14,554 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-11-09 07:56:14,554 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 29 states have (on average 2.3448275862068964) internal successors, (68), 25 states have internal predecessors, (68), 8 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (10), 9 states have call predecessors, (10), 7 states have call successors, (10) Word has length 51 [2024-11-09 07:56:14,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:14,556 INFO L225 Difference]: With dead ends: 253 [2024-11-09 07:56:14,556 INFO L226 Difference]: Without dead ends: 253 [2024-11-09 07:56:14,558 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 107 GetRequests, 55 SyntacticMatches, 1 SemanticMatches, 51 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 485 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=203, Invalid=2452, Unknown=1, NotChecked=100, Total=2756 [2024-11-09 07:56:14,559 INFO L432 NwaCegarLoop]: 94 mSDtfsCounter, 101 mSDsluCounter, 1619 mSDsCounter, 0 mSdLazyCounter, 2767 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 106 SdHoareTripleChecker+Valid, 1713 SdHoareTripleChecker+Invalid, 3024 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 2767 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 218 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:14,559 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [106 Valid, 1713 Invalid, 3024 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 2767 Invalid, 0 Unknown, 218 Unchecked, 1.5s Time] [2024-11-09 07:56:14,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 253 states. [2024-11-09 07:56:14,571 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 253 to 226. [2024-11-09 07:56:14,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 226 states, 159 states have (on average 1.5157232704402517) internal successors, (241), 189 states have internal predecessors, (241), 23 states have call successors, (23), 6 states have call predecessors, (23), 8 states have return successors, (41), 30 states have call predecessors, (41), 23 states have call successors, (41) [2024-11-09 07:56:14,573 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 226 states to 226 states and 305 transitions. [2024-11-09 07:56:14,574 INFO L78 Accepts]: Start accepts. Automaton has 226 states and 305 transitions. Word has length 51 [2024-11-09 07:56:14,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:14,575 INFO L471 AbstractCegarLoop]: Abstraction has 226 states and 305 transitions. [2024-11-09 07:56:14,576 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 29 states have (on average 2.3448275862068964) internal successors, (68), 25 states have internal predecessors, (68), 8 states have call successors, (10), 4 states have call predecessors, (10), 7 states have return successors, (10), 9 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-09 07:56:14,576 INFO L276 IsEmpty]: Start isEmpty. Operand 226 states and 305 transitions. [2024-11-09 07:56:14,576 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-09 07:56:14,577 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:14,577 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:14,595 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-09 07:56:14,778 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:14,778 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:14,779 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:14,779 INFO L85 PathProgramCache]: Analyzing trace with hash 1593016214, now seen corresponding path program 1 times [2024-11-09 07:56:14,779 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:14,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [260052631] [2024-11-09 07:56:14,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:14,779 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:14,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:15,743 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:15,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:15,793 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:15,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:15,908 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:15,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:16,003 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:16,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:16,189 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:16,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:16,377 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 07:56:16,378 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:16,378 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [260052631] [2024-11-09 07:56:16,378 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [260052631] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:16,378 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [724454362] [2024-11-09 07:56:16,379 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:16,379 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:16,380 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:16,381 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-09 07:56:16,383 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-09 07:56:16,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:16,528 INFO L255 TraceCheckSpWp]: Trace formula consists of 291 conjuncts, 95 conjuncts are in the unsatisfiable core [2024-11-09 07:56:16,531 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:16,558 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 8 treesize of output 1 [2024-11-09 07:56:16,561 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 6 treesize of output 5 [2024-11-09 07:56:16,656 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 19 treesize of output 1 [2024-11-09 07:56:16,661 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 13 treesize of output 9 [2024-11-09 07:56:16,768 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= (store |c_old(#length)| alloc_and_zero_internal_~pi~1.base (select |c_#length| alloc_and_zero_internal_~pi~1.base)) |c_#length|) (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0) (= |c_#memory_$Pointer$#0.base| (store |c_old(#memory_$Pointer$#0.base)| alloc_and_zero_internal_~pi~1.base (select |c_#memory_$Pointer$#0.base| alloc_and_zero_internal_~pi~1.base))) (= (store |c_old(#memory_$Pointer$#0.offset)| alloc_and_zero_internal_~pi~1.base (select |c_#memory_$Pointer$#0.offset| alloc_and_zero_internal_~pi~1.base)) |c_#memory_$Pointer$#0.offset|))) is different from true [2024-11-09 07:56:16,858 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 07:56:16,859 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 24 [2024-11-09 07:56:16,865 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 07:56:16,867 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 15 [2024-11-09 07:56:16,889 INFO L349 Elim1Store]: treesize reduction 22, result has 40.5 percent of original size [2024-11-09 07:56:16,889 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 22 treesize of output 24 [2024-11-09 07:56:16,895 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 13 [2024-11-09 07:56:16,945 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 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 31 treesize of output 15 [2024-11-09 07:56:16,951 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-09 07:56:17,080 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 21 treesize of output 9 [2024-11-09 07:56:17,094 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 9 not checked. [2024-11-09 07:56:17,094 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:17,685 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [724454362] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:17,685 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:56:17,685 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 19] total 32 [2024-11-09 07:56:17,686 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2100338387] [2024-11-09 07:56:17,686 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:17,686 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-11-09 07:56:17,686 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:17,687 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-11-09 07:56:17,687 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1436, Unknown=1, NotChecked=76, Total=1640 [2024-11-09 07:56:17,688 INFO L87 Difference]: Start difference. First operand 226 states and 305 transitions. Second operand has 33 states, 29 states have (on average 2.310344827586207) internal successors, (67), 25 states have internal predecessors, (67), 7 states have call successors, (9), 3 states have call predecessors, (9), 6 states have return successors, (10), 9 states have call predecessors, (10), 6 states have call successors, (10) [2024-11-09 07:56:19,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:19,666 INFO L93 Difference]: Finished difference Result 271 states and 356 transitions. [2024-11-09 07:56:19,667 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-09 07:56:19,668 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 29 states have (on average 2.310344827586207) internal successors, (67), 25 states have internal predecessors, (67), 7 states have call successors, (9), 3 states have call predecessors, (9), 6 states have return successors, (10), 9 states have call predecessors, (10), 6 states have call successors, (10) Word has length 51 [2024-11-09 07:56:19,668 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:19,669 INFO L225 Difference]: With dead ends: 271 [2024-11-09 07:56:19,669 INFO L226 Difference]: Without dead ends: 271 [2024-11-09 07:56:19,670 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 515 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=207, Invalid=2552, Unknown=1, NotChecked=102, Total=2862 [2024-11-09 07:56:19,671 INFO L432 NwaCegarLoop]: 96 mSDtfsCounter, 100 mSDsluCounter, 1398 mSDsCounter, 0 mSdLazyCounter, 2127 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 1494 SdHoareTripleChecker+Invalid, 2381 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 2127 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 221 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:19,671 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 1494 Invalid, 2381 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 2127 Invalid, 0 Unknown, 221 Unchecked, 1.2s Time] [2024-11-09 07:56:19,673 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 271 states. [2024-11-09 07:56:19,680 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 271 to 246. [2024-11-09 07:56:19,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 246 states, 176 states have (on average 1.4943181818181819) internal successors, (263), 206 states have internal predecessors, (263), 25 states have call successors, (25), 7 states have call predecessors, (25), 9 states have return successors, (45), 32 states have call predecessors, (45), 25 states have call successors, (45) [2024-11-09 07:56:19,683 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 246 states to 246 states and 333 transitions. [2024-11-09 07:56:19,684 INFO L78 Accepts]: Start accepts. Automaton has 246 states and 333 transitions. Word has length 51 [2024-11-09 07:56:19,684 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:19,685 INFO L471 AbstractCegarLoop]: Abstraction has 246 states and 333 transitions. [2024-11-09 07:56:19,685 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 29 states have (on average 2.310344827586207) internal successors, (67), 25 states have internal predecessors, (67), 7 states have call successors, (9), 3 states have call predecessors, (9), 6 states have return successors, (10), 9 states have call predecessors, (10), 6 states have call successors, (10) [2024-11-09 07:56:19,685 INFO L276 IsEmpty]: Start isEmpty. Operand 246 states and 333 transitions. [2024-11-09 07:56:19,686 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2024-11-09 07:56:19,686 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:19,686 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:19,706 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-09 07:56:19,888 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,SelfDestructingSolverStorable16 [2024-11-09 07:56:19,888 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:19,890 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:19,890 INFO L85 PathProgramCache]: Analyzing trace with hash -1842636325, now seen corresponding path program 1 times [2024-11-09 07:56:19,890 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:19,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [187646662] [2024-11-09 07:56:19,890 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:19,890 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:19,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:20,887 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:20,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:20,943 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:20,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:21,122 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:21,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:21,272 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:21,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:21,467 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:21,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:21,693 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 1 proven. 11 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 07:56:21,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:21,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [187646662] [2024-11-09 07:56:21,693 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [187646662] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:21,693 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [122640398] [2024-11-09 07:56:21,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:21,694 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:21,694 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:21,696 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-09 07:56:21,697 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-09 07:56:21,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:21,851 INFO L255 TraceCheckSpWp]: Trace formula consists of 304 conjuncts, 109 conjuncts are in the unsatisfiable core [2024-11-09 07:56:21,855 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:21,857 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 6 treesize of output 5 [2024-11-09 07:56:22,062 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 11 treesize of output 7 [2024-11-09 07:56:22,070 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 11 treesize of output 7 [2024-11-09 07:56:22,428 INFO L349 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2024-11-09 07:56:22,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2024-11-09 07:56:22,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 17 [2024-11-09 07:56:22,530 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 17 [2024-11-09 07:56:22,717 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0) (= |c_#memory_$Pointer$#0.base| (store |c_old(#memory_$Pointer$#0.base)| alloc_and_zero_internal_~pi~1.base (select |c_#memory_$Pointer$#0.base| alloc_and_zero_internal_~pi~1.base))) (= (store |c_old(#memory_$Pointer$#0.offset)| alloc_and_zero_internal_~pi~1.base (select |c_#memory_$Pointer$#0.offset| alloc_and_zero_internal_~pi~1.base)) |c_#memory_$Pointer$#0.offset|))) is different from true [2024-11-09 07:56:22,791 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-09 07:56:22,800 INFO L349 Elim1Store]: treesize reduction 25, result has 16.7 percent of original size [2024-11-09 07:56:22,800 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 56 treesize of output 51 [2024-11-09 07:56:22,817 INFO L349 Elim1Store]: treesize reduction 8, result has 65.2 percent of original size [2024-11-09 07:56:22,817 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 22 treesize of output 24 [2024-11-09 07:56:22,821 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 29 [2024-11-09 07:56:22,906 INFO L349 Elim1Store]: treesize reduction 49, result has 12.5 percent of original size [2024-11-09 07:56:22,907 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 56 treesize of output 34 [2024-11-09 07:56:22,917 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 29 [2024-11-09 07:56:23,519 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-09 07:56:23,527 INFO L349 Elim1Store]: treesize reduction 29, result has 9.4 percent of original size [2024-11-09 07:56:23,527 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 4 new quantified variables, introduced 3 case distinctions, treesize of input 63 treesize of output 31 [2024-11-09 07:56:23,537 INFO L349 Elim1Store]: treesize reduction 5, result has 37.5 percent of original size [2024-11-09 07:56:23,538 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 33 treesize of output 16 [2024-11-09 07:56:23,546 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 9 not checked. [2024-11-09 07:56:23,546 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:28,901 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [122640398] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:28,901 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:56:28,902 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 50 [2024-11-09 07:56:28,902 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1452308863] [2024-11-09 07:56:28,902 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:28,902 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 50 states [2024-11-09 07:56:28,903 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:28,903 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2024-11-09 07:56:28,904 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=149, Invalid=3045, Unknown=2, NotChecked=110, Total=3306 [2024-11-09 07:56:28,904 INFO L87 Difference]: Start difference. First operand 246 states and 333 transitions. Second operand has 50 states, 46 states have (on average 1.7608695652173914) internal successors, (81), 37 states have internal predecessors, (81), 10 states have call successors, (11), 6 states have call predecessors, (11), 8 states have return successors, (10), 10 states have call predecessors, (10), 8 states have call successors, (10) [2024-11-09 07:56:33,028 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:33,028 INFO L93 Difference]: Finished difference Result 284 states and 374 transitions. [2024-11-09 07:56:33,028 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-09 07:56:33,028 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 46 states have (on average 1.7608695652173914) internal successors, (81), 37 states have internal predecessors, (81), 10 states have call successors, (11), 6 states have call predecessors, (11), 8 states have return successors, (10), 10 states have call predecessors, (10), 8 states have call successors, (10) Word has length 54 [2024-11-09 07:56:33,028 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:33,030 INFO L225 Difference]: With dead ends: 284 [2024-11-09 07:56:33,030 INFO L226 Difference]: Without dead ends: 284 [2024-11-09 07:56:33,031 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 896 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=297, Invalid=5711, Unknown=2, NotChecked=152, Total=6162 [2024-11-09 07:56:33,032 INFO L432 NwaCegarLoop]: 88 mSDtfsCounter, 119 mSDsluCounter, 2277 mSDsCounter, 0 mSdLazyCounter, 3844 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 2365 SdHoareTripleChecker+Invalid, 4121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 3844 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 232 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:33,032 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 2365 Invalid, 4121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 3844 Invalid, 0 Unknown, 232 Unchecked, 2.4s Time] [2024-11-09 07:56:33,033 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 284 states. [2024-11-09 07:56:33,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 284 to 245. [2024-11-09 07:56:33,041 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 245 states, 175 states have (on average 1.48) internal successors, (259), 205 states have internal predecessors, (259), 25 states have call successors, (25), 7 states have call predecessors, (25), 9 states have return successors, (45), 32 states have call predecessors, (45), 25 states have call successors, (45) [2024-11-09 07:56:33,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 329 transitions. [2024-11-09 07:56:33,043 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 329 transitions. Word has length 54 [2024-11-09 07:56:33,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:33,043 INFO L471 AbstractCegarLoop]: Abstraction has 245 states and 329 transitions. [2024-11-09 07:56:33,044 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 50 states, 46 states have (on average 1.7608695652173914) internal successors, (81), 37 states have internal predecessors, (81), 10 states have call successors, (11), 6 states have call predecessors, (11), 8 states have return successors, (10), 10 states have call predecessors, (10), 8 states have call successors, (10) [2024-11-09 07:56:33,044 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 329 transitions. [2024-11-09 07:56:33,044 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-09 07:56:33,044 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:33,045 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 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-09 07:56:33,061 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-09 07:56:33,248 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,SelfDestructingSolverStorable17 [2024-11-09 07:56:33,249 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting ULTIMATE.startErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:33,249 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:33,249 INFO L85 PathProgramCache]: Analyzing trace with hash -809263971, now seen corresponding path program 2 times [2024-11-09 07:56:33,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:33,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1202036345] [2024-11-09 07:56:33,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:33,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:33,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:33,460 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:33,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:33,491 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:33,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:34,219 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:34,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:34,315 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 07:56:34,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:34,475 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 07:56:34,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:34,916 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 17 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 07:56:34,917 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:34,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1202036345] [2024-11-09 07:56:34,917 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1202036345] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:34,917 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2069990785] [2024-11-09 07:56:34,917 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 07:56:34,917 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:34,918 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:34,919 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-09 07:56:34,920 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-09 07:56:35,109 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 07:56:35,109 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 07:56:35,111 INFO L255 TraceCheckSpWp]: Trace formula consists of 293 conjuncts, 39 conjuncts are in the unsatisfiable core [2024-11-09 07:56:35,113 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:35,117 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 6 treesize of output 5 [2024-11-09 07:56:35,145 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1))) is different from true [2024-11-09 07:56:35,172 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) |c_create_internal_#t~ret7.base| (select |c_#valid| |c_create_internal_#t~ret7.base|)))) is different from true [2024-11-09 07:56:35,177 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 15 treesize of output 1 [2024-11-09 07:56:35,185 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (let ((.cse0 (select (select |c_#memory_$Pointer$#0.base| c_create_internal_~now~0.base) c_create_internal_~now~0.offset))) (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) .cse0 (select |c_#valid| .cse0))))) is different from true [2024-11-09 07:56:35,191 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 27 treesize of output 15 [2024-11-09 07:56:35,196 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) |c_create_internal_#t~mem8.base| (select |c_#valid| |c_create_internal_#t~mem8.base|)))) is different from true [2024-11-09 07:56:35,201 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) c_create_internal_~now~0.base (select |c_#valid| c_create_internal_~now~0.base)))) is different from true [2024-11-09 07:56:35,220 WARN L873 $PredicateComparison]: unable to prove that (or (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) c_create_internal_~now~0.base 1))) (exists ((alloc_and_zero_internal_~pi~1.base Int) (v_alloc_and_zero_internal_~pi~1.base_92 Int)) (and (not (= v_alloc_and_zero_internal_~pi~1.base_92 c_create_internal_~now~0.base)) (= |c_#valid| (store (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) c_create_internal_~now~0.base (select |c_#valid| c_create_internal_~now~0.base)) v_alloc_and_zero_internal_~pi~1.base_92 1))))) is different from true [2024-11-09 07:56:35,409 INFO L349 Elim1Store]: treesize reduction 137, result has 16.0 percent of original size [2024-11-09 07:56:35,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 33 treesize of output 79 [2024-11-09 07:56:35,566 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-09 07:56:35,626 INFO L349 Elim1Store]: treesize reduction 220, result has 2.2 percent of original size [2024-11-09 07:56:35,626 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 9 case distinctions, treesize of input 38 treesize of output 25 [2024-11-09 07:56:35,665 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 19 not checked. [2024-11-09 07:56:35,665 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:35,955 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2069990785] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:35,955 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:56:35,955 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 15] total 27 [2024-11-09 07:56:35,955 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1261559347] [2024-11-09 07:56:35,955 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:35,956 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-09 07:56:35,956 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:35,957 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-09 07:56:35,957 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=159, Invalid=456, Unknown=9, NotChecked=306, Total=930 [2024-11-09 07:56:35,957 INFO L87 Difference]: Start difference. First operand 245 states and 329 transitions. Second operand has 28 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 21 states have internal predecessors, (63), 8 states have call successors, (10), 3 states have call predecessors, (10), 7 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2024-11-09 07:56:37,186 WARN L873 $PredicateComparison]: unable to prove that (and (or (exists ((create_internal_~now~0.base Int) (alloc_and_zero_internal_~pi~1.base Int) (v_alloc_and_zero_internal_~pi~1.base_92 Int)) (and (= |c_#valid| (store (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) create_internal_~now~0.base 1) v_alloc_and_zero_internal_~pi~1.base_92 1)) (not (= create_internal_~now~0.base v_alloc_and_zero_internal_~pi~1.base_92)))) (exists ((create_internal_~now~0.base Int) (alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) create_internal_~now~0.base 1)))) (or (exists ((alloc_and_zero_internal_~pi~1.base Int)) (= |c_#valid| (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) c_create_internal_~now~0.base 1))) (exists ((alloc_and_zero_internal_~pi~1.base Int) (v_alloc_and_zero_internal_~pi~1.base_92 Int)) (and (not (= v_alloc_and_zero_internal_~pi~1.base_92 c_create_internal_~now~0.base)) (= |c_#valid| (store (store (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1) c_create_internal_~now~0.base (select |c_#valid| c_create_internal_~now~0.base)) v_alloc_and_zero_internal_~pi~1.base_92 1)))))) is different from true [2024-11-09 07:56:37,574 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:37,574 INFO L93 Difference]: Finished difference Result 299 states and 411 transitions. [2024-11-09 07:56:37,574 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-09 07:56:37,574 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 21 states have internal predecessors, (63), 8 states have call successors, (10), 3 states have call predecessors, (10), 7 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) Word has length 49 [2024-11-09 07:56:37,575 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:37,576 INFO L225 Difference]: With dead ends: 299 [2024-11-09 07:56:37,576 INFO L226 Difference]: Without dead ends: 299 [2024-11-09 07:56:37,576 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 60 SyntacticMatches, 4 SemanticMatches, 39 ConstructedPredicates, 7 IntricatePredicates, 0 DeprecatedPredicates, 267 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=309, Invalid=831, Unknown=10, NotChecked=490, Total=1640 [2024-11-09 07:56:37,577 INFO L432 NwaCegarLoop]: 83 mSDtfsCounter, 163 mSDsluCounter, 602 mSDsCounter, 0 mSdLazyCounter, 998 mSolverCounterSat, 84 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 685 SdHoareTripleChecker+Invalid, 2462 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 84 IncrementalHoareTripleChecker+Valid, 998 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 1376 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:37,577 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [163 Valid, 685 Invalid, 2462 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [84 Valid, 998 Invalid, 4 Unknown, 1376 Unchecked, 1.1s Time] [2024-11-09 07:56:37,578 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 299 states. [2024-11-09 07:56:37,583 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 299 to 256. [2024-11-09 07:56:37,583 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 184 states have (on average 1.4673913043478262) internal successors, (270), 214 states have internal predecessors, (270), 26 states have call successors, (26), 7 states have call predecessors, (26), 10 states have return successors, (56), 34 states have call predecessors, (56), 26 states have call successors, (56) [2024-11-09 07:56:37,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 352 transitions. [2024-11-09 07:56:37,585 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 352 transitions. Word has length 49 [2024-11-09 07:56:37,585 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:37,585 INFO L471 AbstractCegarLoop]: Abstraction has 256 states and 352 transitions. [2024-11-09 07:56:37,585 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 27 states have (on average 2.3333333333333335) internal successors, (63), 21 states have internal predecessors, (63), 8 states have call successors, (10), 3 states have call predecessors, (10), 7 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2024-11-09 07:56:37,586 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 352 transitions. [2024-11-09 07:56:37,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-09 07:56:37,586 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:37,586 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 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-09 07:56:37,601 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-09 07:56:37,791 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:37,791 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting ULTIMATE.startErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:37,791 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:37,791 INFO L85 PathProgramCache]: Analyzing trace with hash -809263970, now seen corresponding path program 2 times [2024-11-09 07:56:37,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:37,792 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1171071028] [2024-11-09 07:56:37,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:37,792 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:37,808 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:38,087 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:38,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:38,189 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:38,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:38,783 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:38,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:38,939 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 07:56:38,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:45,006 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-09 07:56:45,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:45,562 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 4 proven. 19 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 07:56:45,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:45,562 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1171071028] [2024-11-09 07:56:45,562 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1171071028] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:45,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1464483066] [2024-11-09 07:56:45,563 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-09 07:56:45,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:45,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:56:45,565 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-09 07:56:45,567 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-09 07:56:45,744 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-09 07:56:45,744 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 07:56:45,747 INFO L255 TraceCheckSpWp]: Trace formula consists of 293 conjuncts, 53 conjuncts are in the unsatisfiable core [2024-11-09 07:56:45,750 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:56:45,759 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 6 treesize of output 5 [2024-11-09 07:56:45,764 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 8 treesize of output 1 [2024-11-09 07:56:45,932 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= (store |c_old(#length)| alloc_and_zero_internal_~pi~1.base (select |c_#length| alloc_and_zero_internal_~pi~1.base)) |c_#length|) (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0) (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base 1)))) is different from true [2024-11-09 07:56:45,992 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= |c_#valid| (store |c_old(#valid)| alloc_and_zero_internal_~pi~1.base (select |c_#valid| alloc_and_zero_internal_~pi~1.base))) (= (store |c_old(#length)| alloc_and_zero_internal_~pi~1.base (select |c_#length| alloc_and_zero_internal_~pi~1.base)) |c_#length|) (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0))) is different from true [2024-11-09 07:56:46,133 WARN L873 $PredicateComparison]: unable to prove that (exists ((alloc_and_zero_internal_~pi~1.base Int)) (and (= (store |c_old(#length)| alloc_and_zero_internal_~pi~1.base (select |c_#length| alloc_and_zero_internal_~pi~1.base)) |c_#length|) (= (select |c_old(#valid)| alloc_and_zero_internal_~pi~1.base) 0))) is different from true [2024-11-09 07:56:46,570 INFO L349 Elim1Store]: treesize reduction 160, result has 14.4 percent of original size [2024-11-09 07:56:46,570 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 83 treesize of output 124 [2024-11-09 07:56:46,679 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-09 07:56:46,680 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 15 case distinctions, treesize of input 127 treesize of output 233 [2024-11-09 07:56:48,624 INFO L349 Elim1Store]: treesize reduction 162, result has 0.6 percent of original size [2024-11-09 07:56:48,624 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 9 case distinctions, treesize of input 50 treesize of output 16 [2024-11-09 07:56:48,686 WARN L214 Elim1Store]: Array PQE input equivalent to false [2024-11-09 07:56:48,789 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 17 not checked. [2024-11-09 07:56:48,790 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 07:56:49,079 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1464483066] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:56:49,079 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 07:56:49,079 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 12] total 29 [2024-11-09 07:56:49,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [529143627] [2024-11-09 07:56:49,080 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 07:56:49,080 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-09 07:56:49,080 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:49,081 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-09 07:56:49,081 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=702, Unknown=3, NotChecked=168, Total=992 [2024-11-09 07:56:49,081 INFO L87 Difference]: Start difference. First operand 256 states and 352 transitions. Second operand has 30 states, 27 states have (on average 2.814814814814815) internal successors, (76), 24 states have internal predecessors, (76), 9 states have call successors, (10), 3 states have call predecessors, (10), 10 states have return successors, (10), 10 states have call predecessors, (10), 9 states have call successors, (10) [2024-11-09 07:56:54,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:54,789 INFO L93 Difference]: Finished difference Result 311 states and 424 transitions. [2024-11-09 07:56:54,789 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-09 07:56:54,790 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 27 states have (on average 2.814814814814815) internal successors, (76), 24 states have internal predecessors, (76), 9 states have call successors, (10), 3 states have call predecessors, (10), 10 states have return successors, (10), 10 states have call predecessors, (10), 9 states have call successors, (10) Word has length 49 [2024-11-09 07:56:54,790 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:54,791 INFO L225 Difference]: With dead ends: 311 [2024-11-09 07:56:54,791 INFO L226 Difference]: Without dead ends: 311 [2024-11-09 07:56:54,792 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 51 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 3 IntricatePredicates, 0 DeprecatedPredicates, 303 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=155, Invalid=909, Unknown=4, NotChecked=192, Total=1260 [2024-11-09 07:56:54,792 INFO L432 NwaCegarLoop]: 92 mSDtfsCounter, 119 mSDsluCounter, 759 mSDsCounter, 0 mSdLazyCounter, 1450 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 119 SdHoareTripleChecker+Valid, 851 SdHoareTripleChecker+Invalid, 2226 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 1450 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 719 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:54,792 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [119 Valid, 851 Invalid, 2226 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 1450 Invalid, 0 Unknown, 719 Unchecked, 1.4s Time] [2024-11-09 07:56:54,793 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 311 states. [2024-11-09 07:56:54,799 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 311 to 252. [2024-11-09 07:56:54,799 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 252 states, 181 states have (on average 1.4696132596685083) internal successors, (266), 211 states have internal predecessors, (266), 26 states have call successors, (26), 7 states have call predecessors, (26), 9 states have return successors, (46), 33 states have call predecessors, (46), 26 states have call successors, (46) [2024-11-09 07:56:54,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 252 states to 252 states and 338 transitions. [2024-11-09 07:56:54,801 INFO L78 Accepts]: Start accepts. Automaton has 252 states and 338 transitions. Word has length 49 [2024-11-09 07:56:54,801 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:54,801 INFO L471 AbstractCegarLoop]: Abstraction has 252 states and 338 transitions. [2024-11-09 07:56:54,801 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 27 states have (on average 2.814814814814815) internal successors, (76), 24 states have internal predecessors, (76), 9 states have call successors, (10), 3 states have call predecessors, (10), 10 states have return successors, (10), 10 states have call predecessors, (10), 9 states have call successors, (10) [2024-11-09 07:56:54,802 INFO L276 IsEmpty]: Start isEmpty. Operand 252 states and 338 transitions. [2024-11-09 07:56:54,802 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-11-09 07:56:54,802 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:54,803 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:54,821 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-09 07:56:55,006 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:56:55,007 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:55,007 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:55,007 INFO L85 PathProgramCache]: Analyzing trace with hash -611936955, now seen corresponding path program 1 times [2024-11-09 07:56:55,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:55,007 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [742090636] [2024-11-09 07:56:55,007 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:55,007 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:55,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:55,358 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:55,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:55,412 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:55,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:55,421 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:55,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:55,425 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:55,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:55,497 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:55,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:55,545 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-09 07:56:55,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:55,548 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 07:56:55,549 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:55,549 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [742090636] [2024-11-09 07:56:55,549 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [742090636] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:56:55,549 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:56:55,549 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [18] imperfect sequences [] total 18 [2024-11-09 07:56:55,550 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1286006549] [2024-11-09 07:56:55,550 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:56:55,550 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 07:56:55,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:55,551 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 07:56:55,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=306, Unknown=0, NotChecked=0, Total=342 [2024-11-09 07:56:55,551 INFO L87 Difference]: Start difference. First operand 252 states and 338 transitions. Second operand has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 14 states have internal predecessors, (44), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 07:56:56,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:56,376 INFO L93 Difference]: Finished difference Result 286 states and 375 transitions. [2024-11-09 07:56:56,377 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-09 07:56:56,377 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 14 states have internal predecessors, (44), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) Word has length 58 [2024-11-09 07:56:56,377 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:56,378 INFO L225 Difference]: With dead ends: 286 [2024-11-09 07:56:56,378 INFO L226 Difference]: Without dead ends: 286 [2024-11-09 07:56:56,379 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=54, Invalid=452, Unknown=0, NotChecked=0, Total=506 [2024-11-09 07:56:56,379 INFO L432 NwaCegarLoop]: 96 mSDtfsCounter, 54 mSDsluCounter, 1056 mSDsCounter, 0 mSdLazyCounter, 1585 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 1152 SdHoareTripleChecker+Invalid, 1600 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 1585 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:56,379 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 1152 Invalid, 1600 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 1585 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-09 07:56:56,380 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2024-11-09 07:56:56,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 263. [2024-11-09 07:56:56,386 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 263 states, 190 states have (on average 1.4736842105263157) internal successors, (280), 220 states have internal predecessors, (280), 27 states have call successors, (27), 8 states have call predecessors, (27), 10 states have return successors, (47), 34 states have call predecessors, (47), 27 states have call successors, (47) [2024-11-09 07:56:56,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 263 states to 263 states and 354 transitions. [2024-11-09 07:56:56,387 INFO L78 Accepts]: Start accepts. Automaton has 263 states and 354 transitions. Word has length 58 [2024-11-09 07:56:56,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:56,388 INFO L471 AbstractCegarLoop]: Abstraction has 263 states and 354 transitions. [2024-11-09 07:56:56,388 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 14 states have internal predecessors, (44), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 07:56:56,388 INFO L276 IsEmpty]: Start isEmpty. Operand 263 states and 354 transitions. [2024-11-09 07:56:56,389 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-11-09 07:56:56,389 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:56,389 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:56,389 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable20 [2024-11-09 07:56:56,389 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:56,390 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:56,390 INFO L85 PathProgramCache]: Analyzing trace with hash -611936954, now seen corresponding path program 1 times [2024-11-09 07:56:56,390 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:56,390 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1592206492] [2024-11-09 07:56:56,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:56,390 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:56,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:56,839 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:56,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:56,888 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:56,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:56,897 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:56,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:56,904 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:56,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:57,002 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:57,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:57,065 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 47 [2024-11-09 07:56:57,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:57,070 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 07:56:57,070 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:56:57,070 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1592206492] [2024-11-09 07:56:57,070 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1592206492] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 07:56:57,070 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 07:56:57,070 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [18] imperfect sequences [] total 18 [2024-11-09 07:56:57,070 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1417904910] [2024-11-09 07:56:57,071 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 07:56:57,072 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 07:56:57,072 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 07:56:57,073 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 07:56:57,074 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=306, Unknown=0, NotChecked=0, Total=342 [2024-11-09 07:56:57,075 INFO L87 Difference]: Start difference. First operand 263 states and 354 transitions. Second operand has 19 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 14 states have internal predecessors, (45), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 07:56:58,027 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 07:56:58,027 INFO L93 Difference]: Finished difference Result 286 states and 374 transitions. [2024-11-09 07:56:58,028 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-09 07:56:58,028 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 14 states have internal predecessors, (45), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) Word has length 58 [2024-11-09 07:56:58,028 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 07:56:58,029 INFO L225 Difference]: With dead ends: 286 [2024-11-09 07:56:58,029 INFO L226 Difference]: Without dead ends: 286 [2024-11-09 07:56:58,030 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=54, Invalid=452, Unknown=0, NotChecked=0, Total=506 [2024-11-09 07:56:58,030 INFO L432 NwaCegarLoop]: 96 mSDtfsCounter, 53 mSDsluCounter, 1144 mSDsCounter, 0 mSdLazyCounter, 1629 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 1240 SdHoareTripleChecker+Invalid, 1643 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 1629 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-09 07:56:58,031 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 1240 Invalid, 1643 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 1629 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-09 07:56:58,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2024-11-09 07:56:58,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 263. [2024-11-09 07:56:58,037 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 263 states, 190 states have (on average 1.4684210526315788) internal successors, (279), 220 states have internal predecessors, (279), 27 states have call successors, (27), 8 states have call predecessors, (27), 10 states have return successors, (47), 34 states have call predecessors, (47), 27 states have call successors, (47) [2024-11-09 07:56:58,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 263 states to 263 states and 353 transitions. [2024-11-09 07:56:58,038 INFO L78 Accepts]: Start accepts. Automaton has 263 states and 353 transitions. Word has length 58 [2024-11-09 07:56:58,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 07:56:58,038 INFO L471 AbstractCegarLoop]: Abstraction has 263 states and 353 transitions. [2024-11-09 07:56:58,039 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.6470588235294117) internal successors, (45), 14 states have internal predecessors, (45), 5 states have call successors, (6), 3 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 07:56:58,039 INFO L276 IsEmpty]: Start isEmpty. Operand 263 states and 353 transitions. [2024-11-09 07:56:58,040 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-09 07:56:58,040 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 07:56:58,040 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 07:56:58,040 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable21 [2024-11-09 07:56:58,040 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE === [loop_internalErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE, loop_internalErr1REQUIRES_VIOLATIONMEMORY_DEREFERENCE, alloc_and_zeroErr0REQUIRES_VIOLATIONMEMORY_DEREFERENCE (and 48 more)] === [2024-11-09 07:56:58,041 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 07:56:58,041 INFO L85 PathProgramCache]: Analyzing trace with hash -1325109, now seen corresponding path program 1 times [2024-11-09 07:56:58,041 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 07:56:58,041 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [102968277] [2024-11-09 07:56:58,041 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:56:58,041 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 07:56:58,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:58,692 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-09 07:56:58,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:58,749 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-11-09 07:56:58,752 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:58,824 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:56:58,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:58,880 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2024-11-09 07:56:58,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:56:59,997 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-11-09 07:57:00,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:57:00,257 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-09 07:57:00,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:57:00,689 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 17 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-09 07:57:00,690 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 07:57:00,690 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [102968277] [2024-11-09 07:57:00,690 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [102968277] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 07:57:00,690 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [703900964] [2024-11-09 07:57:00,690 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 07:57:00,690 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 07:57:00,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 07:57:00,692 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-09 07:57:00,692 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-09 07:57:00,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 07:57:00,866 INFO L255 TraceCheckSpWp]: Trace formula consists of 361 conjuncts, 79 conjuncts are in the unsatisfiable core [2024-11-09 07:57:00,869 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 07:57:00,905 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 6 treesize of output 5