./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursive-simple/fibo_7-1.c --full-output --traceabstraction.positions.where.we.compute.the.hoare.annotation All --witnessprinter.yaml.format.version 2.1 --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a9b967e5 Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/certificate-witnesses-artifact/automizer/data/config -Xmx15G -Xms4m -jar /storage/repos/certificate-witnesses-artifact/automizer/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/certificate-witnesses-artifact/automizer/data -tc /storage/repos/certificate-witnesses-artifact/automizer/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursive-simple/fibo_7-1.c -s /storage/repos/certificate-witnesses-artifact/automizer/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/certificate-witnesses-artifact/automizer --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 17c70baee0bc6a4a26b6403fb6f46125ad9d7f8a7127109634f2327c61aaf5cb --traceabstraction.positions.where.we.compute.the.hoare.annotation All --witnessprinter.yaml.format.version 2.1 --- Real Ultimate output --- This is Ultimate 0.2.4-dev-a9b967e-m [2024-09-11 20:28:19,516 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-09-11 20:28:19,574 INFO L114 SettingsManager]: Loading settings from /storage/repos/certificate-witnesses-artifact/automizer/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-09-11 20:28:19,579 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-09-11 20:28:19,579 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-09-11 20:28:19,600 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-09-11 20:28:19,600 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-09-11 20:28:19,600 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-09-11 20:28:19,601 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-09-11 20:28:19,601 INFO L153 SettingsManager]: * Use memory slicer=true [2024-09-11 20:28:19,602 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-09-11 20:28:19,603 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-09-11 20:28:19,603 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-09-11 20:28:19,606 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-09-11 20:28:19,606 INFO L153 SettingsManager]: * Use SBE=true [2024-09-11 20:28:19,607 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-09-11 20:28:19,607 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-09-11 20:28:19,607 INFO L153 SettingsManager]: * sizeof long=4 [2024-09-11 20:28:19,607 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-09-11 20:28:19,608 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-09-11 20:28:19,608 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-09-11 20:28:19,609 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-09-11 20:28:19,609 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-09-11 20:28:19,610 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-09-11 20:28:19,610 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-09-11 20:28:19,610 INFO L153 SettingsManager]: * sizeof long double=12 [2024-09-11 20:28:19,610 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-09-11 20:28:19,610 INFO L153 SettingsManager]: * Use constant arrays=true [2024-09-11 20:28:19,611 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-09-11 20:28:19,611 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-09-11 20:28:19,611 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-09-11 20:28:19,611 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-09-11 20:28:19,611 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-11 20:28:19,612 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-09-11 20:28:19,612 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-09-11 20:28:19,612 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-09-11 20:28:19,613 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-09-11 20:28:19,613 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-09-11 20:28:19,613 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-09-11 20:28:19,613 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-09-11 20:28:19,613 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-09-11 20:28:19,614 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-09-11 20:28:19,614 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/certificate-witnesses-artifact/automizer/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/certificate-witnesses-artifact/automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 17c70baee0bc6a4a26b6403fb6f46125ad9d7f8a7127109634f2327c61aaf5cb Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Positions where we compute the Hoare Annotation -> All Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: YAML Format version -> 2.1 [2024-09-11 20:28:19,797 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-09-11 20:28:19,816 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-09-11 20:28:19,819 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-09-11 20:28:19,820 INFO L270 PluginConnector]: Initializing CDTParser... [2024-09-11 20:28:19,820 INFO L274 PluginConnector]: CDTParser initialized [2024-09-11 20:28:19,822 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/certificate-witnesses-artifact/automizer/../sv-benchmarks/c/recursive-simple/fibo_7-1.c [2024-09-11 20:28:21,022 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-09-11 20:28:21,152 INFO L384 CDTParser]: Found 1 translation units. [2024-09-11 20:28:21,153 INFO L180 CDTParser]: Scanning /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursive-simple/fibo_7-1.c [2024-09-11 20:28:21,158 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/certificate-witnesses-artifact/automizer/data/d1dab638c/2ae7c02607144a5fa7bb770284b2a7ab/FLAGfdd84b967 [2024-09-11 20:28:21,168 INFO L435 CDTParser]: Successfully deleted /storage/repos/certificate-witnesses-artifact/automizer/data/d1dab638c/2ae7c02607144a5fa7bb770284b2a7ab [2024-09-11 20:28:21,170 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-09-11 20:28:21,171 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-09-11 20:28:21,172 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-09-11 20:28:21,172 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-09-11 20:28:21,179 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-09-11 20:28:21,179 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,181 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7b46fe36 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21, skipping insertion in model container [2024-09-11 20:28:21,181 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,196 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-09-11 20:28:21,316 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursive-simple/fibo_7-1.c[741,754] [2024-09-11 20:28:21,320 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-11 20:28:21,335 INFO L200 MainTranslator]: Completed pre-run [2024-09-11 20:28:21,347 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursive-simple/fibo_7-1.c[741,754] [2024-09-11 20:28:21,348 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-11 20:28:21,376 INFO L204 MainTranslator]: Completed translation [2024-09-11 20:28:21,377 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21 WrapperNode [2024-09-11 20:28:21,377 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-09-11 20:28:21,378 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-09-11 20:28:21,378 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-09-11 20:28:21,378 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-09-11 20:28:21,383 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,388 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,398 INFO L138 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2024-09-11 20:28:21,398 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-09-11 20:28:21,399 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-09-11 20:28:21,399 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-09-11 20:28:21,399 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-09-11 20:28:21,405 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,406 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,406 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,413 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-09-11 20:28:21,413 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,414 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,415 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,416 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,416 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,417 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,418 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-09-11 20:28:21,418 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-09-11 20:28:21,419 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-09-11 20:28:21,419 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-09-11 20:28:21,420 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (1/1) ... [2024-09-11 20:28:21,424 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-11 20:28:21,435 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:21,454 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/certificate-witnesses-artifact/automizer/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-09-11 20:28:21,457 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-09-11 20:28:21,491 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-09-11 20:28:21,492 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-09-11 20:28:21,492 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-09-11 20:28:21,492 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-09-11 20:28:21,492 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-09-11 20:28:21,492 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-09-11 20:28:21,539 INFO L242 CfgBuilder]: Building ICFG [2024-09-11 20:28:21,540 INFO L268 CfgBuilder]: Building CFG for each procedure with an implementation [2024-09-11 20:28:21,626 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-09-11 20:28:21,627 INFO L291 CfgBuilder]: Performing block encoding [2024-09-11 20:28:21,651 INFO L313 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-09-11 20:28:21,652 INFO L318 CfgBuilder]: Removed 0 assume(true) statements. [2024-09-11 20:28:21,653 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.09 08:28:21 BoogieIcfgContainer [2024-09-11 20:28:21,653 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-09-11 20:28:21,654 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-09-11 20:28:21,655 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-09-11 20:28:21,658 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-09-11 20:28:21,658 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.09 08:28:21" (1/3) ... [2024-09-11 20:28:21,659 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@258be2b6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.09 08:28:21, skipping insertion in model container [2024-09-11 20:28:21,659 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.09 08:28:21" (2/3) ... [2024-09-11 20:28:21,660 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@258be2b6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.09 08:28:21, skipping insertion in model container [2024-09-11 20:28:21,660 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.09 08:28:21" (3/3) ... [2024-09-11 20:28:21,662 INFO L112 eAbstractionObserver]: Analyzing ICFG fibo_7-1.c [2024-09-11 20:28:21,674 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:All NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-09-11 20:28:21,675 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-09-11 20:28:21,716 INFO L335 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-09-11 20:28:21,721 INFO L336 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=All, 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;@5760d816, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-09-11 20:28:21,721 INFO L337 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-09-11 20:28:21,724 INFO L276 IsEmpty]: Start isEmpty. Operand has 17 states, 11 states have (on average 1.3636363636363635) internal successors, (15), 12 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-09-11 20:28:21,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2024-09-11 20:28:21,728 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:21,729 INFO L216 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:21,729 INFO L399 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:21,733 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:21,733 INFO L85 PathProgramCache]: Analyzing trace with hash -798924922, now seen corresponding path program 1 times [2024-09-11 20:28:21,739 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:21,740 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1899211492] [2024-09-11 20:28:21,740 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:21,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:21,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:21,908 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:21,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:21,959 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-11 20:28:21,959 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:21,960 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1899211492] [2024-09-11 20:28:21,960 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1899211492] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-11 20:28:21,960 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-11 20:28:21,960 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-09-11 20:28:21,962 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [529395447] [2024-09-11 20:28:21,962 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-11 20:28:21,965 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-11 20:28:21,965 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:21,982 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-11 20:28:21,983 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-11 20:28:21,984 INFO L87 Difference]: Start difference. First operand has 17 states, 11 states have (on average 1.3636363636363635) internal successors, (15), 12 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-09-11 20:28:22,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:22,046 INFO L93 Difference]: Finished difference Result 27 states and 35 transitions. [2024-09-11 20:28:22,048 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-11 20:28:22,049 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 9 [2024-09-11 20:28:22,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:22,054 INFO L225 Difference]: With dead ends: 27 [2024-09-11 20:28:22,054 INFO L226 Difference]: Without dead ends: 19 [2024-09-11 20:28:22,056 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-11 20:28:22,058 INFO L434 NwaCegarLoop]: 13 mSDtfsCounter, 9 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:22,058 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 34 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-11 20:28:22,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2024-09-11 20:28:22,131 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2024-09-11 20:28:22,132 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 12 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-09-11 20:28:22,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-09-11 20:28:22,136 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 9 [2024-09-11 20:28:22,136 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:22,136 INFO L474 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-09-11 20:28:22,136 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-09-11 20:28:22,138 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:22,138 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2024-09-11 20:28:22,139 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-09-11 20:28:22,141 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:22,141 INFO L216 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:22,141 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-09-11 20:28:22,141 INFO L399 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:22,142 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:22,142 INFO L85 PathProgramCache]: Analyzing trace with hash 1717873930, now seen corresponding path program 1 times [2024-09-11 20:28:22,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:22,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317538605] [2024-09-11 20:28:22,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:22,143 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:22,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:22,196 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:22,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:22,247 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-11 20:28:22,248 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:22,248 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317538605] [2024-09-11 20:28:22,248 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [317538605] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-11 20:28:22,248 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-11 20:28:22,249 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-09-11 20:28:22,249 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1834646186] [2024-09-11 20:28:22,249 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-11 20:28:22,250 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-11 20:28:22,251 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:22,252 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-11 20:28:22,253 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-11 20:28:22,253 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 5 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-09-11 20:28:22,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:22,300 INFO L93 Difference]: Finished difference Result 23 states and 28 transitions. [2024-09-11 20:28:22,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-11 20:28:22,301 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2024-09-11 20:28:22,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:22,302 INFO L225 Difference]: With dead ends: 23 [2024-09-11 20:28:22,302 INFO L226 Difference]: Without dead ends: 19 [2024-09-11 20:28:22,303 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-11 20:28:22,305 INFO L434 NwaCegarLoop]: 11 mSDtfsCounter, 7 mSDsluCounter, 16 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 27 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:22,305 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 27 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-11 20:28:22,306 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2024-09-11 20:28:22,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2024-09-11 20:28:22,313 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 12 states have internal predecessors, (13), 3 states have call successors, (3), 1 states have call predecessors, (3), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-09-11 20:28:22,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2024-09-11 20:28:22,314 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 21 transitions. Word has length 10 [2024-09-11 20:28:22,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:22,314 INFO L474 AbstractCegarLoop]: Abstraction has 17 states and 21 transitions. [2024-09-11 20:28:22,314 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.0) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-09-11 20:28:22,315 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:22,315 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 21 transitions. [2024-09-11 20:28:22,316 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-09-11 20:28:22,316 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:22,316 INFO L216 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:22,316 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-09-11 20:28:22,317 INFO L399 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:22,317 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:22,318 INFO L85 PathProgramCache]: Analyzing trace with hash 913644549, now seen corresponding path program 1 times [2024-09-11 20:28:22,318 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:22,318 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1268517550] [2024-09-11 20:28:22,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:22,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:22,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:22,371 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:22,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:22,427 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:22,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:22,449 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-09-11 20:28:22,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:22,458 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-11 20:28:22,458 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:22,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1268517550] [2024-09-11 20:28:22,458 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1268517550] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:22,458 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1064230545] [2024-09-11 20:28:22,460 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:22,460 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:22,460 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:22,462 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:22,463 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-09-11 20:28:22,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:22,509 INFO L262 TraceCheckSpWp]: Trace formula consists of 70 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-09-11 20:28:22,513 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:22,586 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-11 20:28:22,587 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:22,754 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-09-11 20:28:22,754 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1064230545] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:22,754 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:22,754 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 7] total 12 [2024-09-11 20:28:22,754 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1096469065] [2024-09-11 20:28:22,754 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:22,755 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-09-11 20:28:22,755 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:22,755 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-09-11 20:28:22,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=97, Unknown=0, NotChecked=0, Total=132 [2024-09-11 20:28:22,756 INFO L87 Difference]: Start difference. First operand 17 states and 21 transitions. Second operand has 12 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2024-09-11 20:28:22,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:22,812 INFO L93 Difference]: Finished difference Result 34 states and 45 transitions. [2024-09-11 20:28:22,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-09-11 20:28:22,812 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) Word has length 22 [2024-09-11 20:28:22,813 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:22,813 INFO L225 Difference]: With dead ends: 34 [2024-09-11 20:28:22,813 INFO L226 Difference]: Without dead ends: 19 [2024-09-11 20:28:22,814 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 44 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=131, Unknown=0, NotChecked=0, Total=182 [2024-09-11 20:28:22,814 INFO L434 NwaCegarLoop]: 11 mSDtfsCounter, 17 mSDsluCounter, 24 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 74 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:22,815 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 35 Invalid, 74 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-11 20:28:22,815 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2024-09-11 20:28:22,818 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2024-09-11 20:28:22,818 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 19 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 14 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-09-11 20:28:22,819 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 23 transitions. [2024-09-11 20:28:22,819 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 23 transitions. Word has length 22 [2024-09-11 20:28:22,819 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:22,819 INFO L474 AbstractCegarLoop]: Abstraction has 19 states and 23 transitions. [2024-09-11 20:28:22,819 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 3.2222222222222223) internal successors, (29), 12 states have internal predecessors, (29), 8 states have call successors, (8), 1 states have call predecessors, (8), 4 states have return successors, (8), 2 states have call predecessors, (8), 8 states have call successors, (8) [2024-09-11 20:28:22,819 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:22,820 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 23 transitions. [2024-09-11 20:28:22,820 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2024-09-11 20:28:22,820 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:22,820 INFO L216 NwaCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:22,833 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-09-11 20:28:23,024 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:23,025 INFO L399 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:23,025 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:23,025 INFO L85 PathProgramCache]: Analyzing trace with hash -252103063, now seen corresponding path program 1 times [2024-09-11 20:28:23,025 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:23,025 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [450971978] [2024-09-11 20:28:23,025 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:23,026 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:23,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,078 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:23,082 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,143 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:23,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,166 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:23,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,172 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-09-11 20:28:23,172 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:23,172 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [450971978] [2024-09-11 20:28:23,172 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [450971978] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:23,172 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [961775614] [2024-09-11 20:28:23,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:23,173 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:23,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:23,174 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:23,176 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-09-11 20:28:23,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,205 INFO L262 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-09-11 20:28:23,206 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:23,244 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-09-11 20:28:23,244 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:23,386 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 8 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-09-11 20:28:23,387 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [961775614] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:23,387 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:23,387 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6, 7] total 11 [2024-09-11 20:28:23,388 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [181771990] [2024-09-11 20:28:23,388 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:23,388 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-09-11 20:28:23,388 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:23,389 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-09-11 20:28:23,389 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2024-09-11 20:28:23,389 INFO L87 Difference]: Start difference. First operand 19 states and 23 transitions. Second operand has 11 states, 9 states have (on average 3.0) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (7), 1 states have call predecessors, (7), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-09-11 20:28:23,484 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:23,484 INFO L93 Difference]: Finished difference Result 37 states and 51 transitions. [2024-09-11 20:28:23,485 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-09-11 20:28:23,485 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 3.0) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (7), 1 states have call predecessors, (7), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) Word has length 23 [2024-09-11 20:28:23,485 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:23,486 INFO L225 Difference]: With dead ends: 37 [2024-09-11 20:28:23,486 INFO L226 Difference]: Without dead ends: 33 [2024-09-11 20:28:23,486 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 45 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 30 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=89, Unknown=0, NotChecked=0, Total=132 [2024-09-11 20:28:23,487 INFO L434 NwaCegarLoop]: 16 mSDtfsCounter, 18 mSDsluCounter, 39 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 55 SdHoareTripleChecker+Invalid, 130 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:23,487 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 55 Invalid, 130 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 117 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-11 20:28:23,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2024-09-11 20:28:23,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2024-09-11 20:28:23,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 6 states have call successors, (6), 2 states have call predecessors, (6), 5 states have return successors, (16), 7 states have call predecessors, (16), 6 states have call successors, (16) [2024-09-11 20:28:23,495 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 47 transitions. [2024-09-11 20:28:23,496 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 47 transitions. Word has length 23 [2024-09-11 20:28:23,496 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:23,496 INFO L474 AbstractCegarLoop]: Abstraction has 33 states and 47 transitions. [2024-09-11 20:28:23,496 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 3.0) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (7), 1 states have call predecessors, (7), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-09-11 20:28:23,496 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:23,497 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 47 transitions. [2024-09-11 20:28:23,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2024-09-11 20:28:23,498 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:23,498 INFO L216 NwaCegarLoop]: trace histogram [5, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:23,510 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-09-11 20:28:23,698 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:23,699 INFO L399 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:23,699 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:23,699 INFO L85 PathProgramCache]: Analyzing trace with hash 659330, now seen corresponding path program 2 times [2024-09-11 20:28:23,699 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:23,699 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1702372554] [2024-09-11 20:28:23,699 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:23,700 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:23,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,733 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:23,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,765 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:23,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,811 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:23,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,816 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:23,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,822 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:23,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:23,839 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 23 proven. 7 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-09-11 20:28:23,839 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:23,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1702372554] [2024-09-11 20:28:23,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1702372554] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:23,840 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1436948709] [2024-09-11 20:28:23,840 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-11 20:28:23,840 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:23,840 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:23,842 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:23,843 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-09-11 20:28:23,878 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-11 20:28:23,878 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-11 20:28:23,881 INFO L262 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-09-11 20:28:23,882 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:23,939 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 6 proven. 21 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-09-11 20:28:23,939 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:24,193 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 6 proven. 28 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-09-11 20:28:24,194 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1436948709] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:24,194 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:24,194 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7, 9] total 17 [2024-09-11 20:28:24,194 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1540831080] [2024-09-11 20:28:24,194 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:24,194 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-09-11 20:28:24,195 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:24,195 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-09-11 20:28:24,195 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=204, Unknown=0, NotChecked=0, Total=272 [2024-09-11 20:28:24,196 INFO L87 Difference]: Start difference. First operand 33 states and 47 transitions. Second operand has 17 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 17 states have internal predecessors, (43), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (13), 6 states have call predecessors, (13), 10 states have call successors, (13) [2024-09-11 20:28:24,341 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:24,342 INFO L93 Difference]: Finished difference Result 68 states and 105 transitions. [2024-09-11 20:28:24,342 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-09-11 20:28:24,342 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 17 states have internal predecessors, (43), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (13), 6 states have call predecessors, (13), 10 states have call successors, (13) Word has length 36 [2024-09-11 20:28:24,343 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:24,343 INFO L225 Difference]: With dead ends: 68 [2024-09-11 20:28:24,343 INFO L226 Difference]: Without dead ends: 37 [2024-09-11 20:28:24,344 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 73 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=138, Invalid=368, Unknown=0, NotChecked=0, Total=506 [2024-09-11 20:28:24,345 INFO L434 NwaCegarLoop]: 14 mSDtfsCounter, 33 mSDsluCounter, 42 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 56 SdHoareTripleChecker+Invalid, 156 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:24,345 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 56 Invalid, 156 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-11 20:28:24,345 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2024-09-11 20:28:24,351 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2024-09-11 20:28:24,351 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 25 states have internal predecessors, (29), 5 states have call successors, (5), 4 states have call predecessors, (5), 5 states have return successors, (11), 7 states have call predecessors, (11), 5 states have call successors, (11) [2024-09-11 20:28:24,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 45 transitions. [2024-09-11 20:28:24,352 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 45 transitions. Word has length 36 [2024-09-11 20:28:24,352 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:24,354 INFO L474 AbstractCegarLoop]: Abstraction has 37 states and 45 transitions. [2024-09-11 20:28:24,354 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.8666666666666667) internal successors, (43), 17 states have internal predecessors, (43), 10 states have call successors, (12), 1 states have call predecessors, (12), 7 states have return successors, (13), 6 states have call predecessors, (13), 10 states have call successors, (13) [2024-09-11 20:28:24,354 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:24,355 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 45 transitions. [2024-09-11 20:28:24,356 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2024-09-11 20:28:24,357 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:24,357 INFO L216 NwaCegarLoop]: trace histogram [13, 13, 11, 6, 6, 6, 6, 6, 6, 6, 5, 2, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:24,370 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-09-11 20:28:24,558 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:24,558 INFO L399 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:24,558 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:24,558 INFO L85 PathProgramCache]: Analyzing trace with hash -867130448, now seen corresponding path program 3 times [2024-09-11 20:28:24,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:24,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [635105071] [2024-09-11 20:28:24,559 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:24,559 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:24,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,644 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:24,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,712 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:24,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,742 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:24,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,776 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:24,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,789 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:24,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,792 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:24,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,794 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:24,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,809 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:24,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,818 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:24,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,821 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:24,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,823 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:24,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,824 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:24,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,826 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:24,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:24,828 INFO L134 CoverageAnalysis]: Checked inductivity of 427 backedges. 27 proven. 166 refuted. 0 times theorem prover too weak. 234 trivial. 0 not checked. [2024-09-11 20:28:24,828 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:24,828 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [635105071] [2024-09-11 20:28:24,828 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [635105071] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:24,828 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1162464957] [2024-09-11 20:28:24,828 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-09-11 20:28:24,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:24,829 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:24,832 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:24,832 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-09-11 20:28:24,877 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2024-09-11 20:28:24,877 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-11 20:28:24,877 INFO L262 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-09-11 20:28:24,879 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:24,937 INFO L134 CoverageAnalysis]: Checked inductivity of 427 backedges. 174 proven. 17 refuted. 0 times theorem prover too weak. 236 trivial. 0 not checked. [2024-09-11 20:28:24,937 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:25,258 INFO L134 CoverageAnalysis]: Checked inductivity of 427 backedges. 174 proven. 18 refuted. 0 times theorem prover too weak. 235 trivial. 0 not checked. [2024-09-11 20:28:25,259 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1162464957] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:25,259 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:25,259 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8, 9] total 19 [2024-09-11 20:28:25,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1535113094] [2024-09-11 20:28:25,260 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:25,260 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-09-11 20:28:25,260 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:25,261 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-09-11 20:28:25,262 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=260, Unknown=0, NotChecked=0, Total=342 [2024-09-11 20:28:25,263 INFO L87 Difference]: Start difference. First operand 37 states and 45 transitions. Second operand has 19 states, 18 states have (on average 2.8333333333333335) internal successors, (51), 19 states have internal predecessors, (51), 9 states have call successors, (13), 1 states have call predecessors, (13), 8 states have return successors, (17), 12 states have call predecessors, (17), 9 states have call successors, (17) [2024-09-11 20:28:25,473 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:25,473 INFO L93 Difference]: Finished difference Result 88 states and 132 transitions. [2024-09-11 20:28:25,474 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-09-11 20:28:25,474 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 2.8333333333333335) internal successors, (51), 19 states have internal predecessors, (51), 9 states have call successors, (13), 1 states have call predecessors, (13), 8 states have return successors, (17), 12 states have call predecessors, (17), 9 states have call successors, (17) Word has length 92 [2024-09-11 20:28:25,475 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:25,476 INFO L225 Difference]: With dead ends: 88 [2024-09-11 20:28:25,476 INFO L226 Difference]: Without dead ends: 52 [2024-09-11 20:28:25,478 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 228 GetRequests, 196 SyntacticMatches, 4 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 224 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=234, Invalid=636, Unknown=0, NotChecked=0, Total=870 [2024-09-11 20:28:25,479 INFO L434 NwaCegarLoop]: 19 mSDtfsCounter, 58 mSDsluCounter, 77 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 70 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 261 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 70 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:25,479 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 96 Invalid, 261 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [70 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-11 20:28:25,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2024-09-11 20:28:25,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 49. [2024-09-11 20:28:25,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 34 states have (on average 1.1176470588235294) internal successors, (38), 33 states have internal predecessors, (38), 8 states have call successors, (8), 6 states have call predecessors, (8), 6 states have return successors, (16), 9 states have call predecessors, (16), 8 states have call successors, (16) [2024-09-11 20:28:25,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 62 transitions. [2024-09-11 20:28:25,493 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 62 transitions. Word has length 92 [2024-09-11 20:28:25,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:25,496 INFO L474 AbstractCegarLoop]: Abstraction has 49 states and 62 transitions. [2024-09-11 20:28:25,496 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 2.8333333333333335) internal successors, (51), 19 states have internal predecessors, (51), 9 states have call successors, (13), 1 states have call predecessors, (13), 8 states have return successors, (17), 12 states have call predecessors, (17), 9 states have call successors, (17) [2024-09-11 20:28:25,496 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:25,496 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 62 transitions. [2024-09-11 20:28:25,499 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 133 [2024-09-11 20:28:25,501 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:25,501 INFO L216 NwaCegarLoop]: trace histogram [19, 19, 15, 9, 9, 9, 9, 9, 9, 9, 6, 4, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:25,513 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-09-11 20:28:25,701 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:25,702 INFO L399 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:25,702 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:25,702 INFO L85 PathProgramCache]: Analyzing trace with hash 1193756999, now seen corresponding path program 4 times [2024-09-11 20:28:25,702 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:25,702 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [772445131] [2024-09-11 20:28:25,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:25,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:25,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,808 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:25,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,879 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:25,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,920 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:25,923 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,948 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:25,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,971 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:25,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,984 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:25,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,987 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:25,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,989 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:25,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,996 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:25,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,997 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:25,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:25,999 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:26,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,054 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:26,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,103 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:26,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,154 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:26,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,158 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:26,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,163 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:26,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,167 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:26,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,175 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:26,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,176 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:26,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:26,179 INFO L134 CoverageAnalysis]: Checked inductivity of 933 backedges. 198 proven. 308 refuted. 0 times theorem prover too weak. 427 trivial. 0 not checked. [2024-09-11 20:28:26,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:26,179 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [772445131] [2024-09-11 20:28:26,180 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [772445131] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:26,180 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [100509949] [2024-09-11 20:28:26,180 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-09-11 20:28:26,180 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:26,180 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:26,182 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:26,182 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-09-11 20:28:26,239 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-09-11 20:28:26,239 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-11 20:28:26,240 INFO L262 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-09-11 20:28:26,243 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:26,345 INFO L134 CoverageAnalysis]: Checked inductivity of 933 backedges. 207 proven. 356 refuted. 0 times theorem prover too weak. 370 trivial. 0 not checked. [2024-09-11 20:28:26,345 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:27,371 INFO L134 CoverageAnalysis]: Checked inductivity of 933 backedges. 207 proven. 383 refuted. 0 times theorem prover too weak. 343 trivial. 0 not checked. [2024-09-11 20:28:27,372 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [100509949] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:27,372 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:27,372 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 13, 19] total 30 [2024-09-11 20:28:27,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [677265582] [2024-09-11 20:28:27,372 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:27,372 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-09-11 20:28:27,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:27,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-09-11 20:28:27,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=212, Invalid=658, Unknown=0, NotChecked=0, Total=870 [2024-09-11 20:28:27,374 INFO L87 Difference]: Start difference. First operand 49 states and 62 transitions. Second operand has 30 states, 29 states have (on average 2.7586206896551726) internal successors, (80), 30 states have internal predecessors, (80), 24 states have call successors, (27), 1 states have call predecessors, (27), 10 states have return successors, (36), 15 states have call predecessors, (36), 24 states have call successors, (36) [2024-09-11 20:28:27,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:27,628 INFO L93 Difference]: Finished difference Result 115 states and 178 transitions. [2024-09-11 20:28:27,628 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-09-11 20:28:27,629 INFO L78 Accepts]: Start accepts. Automaton has has 30 states, 29 states have (on average 2.7586206896551726) internal successors, (80), 30 states have internal predecessors, (80), 24 states have call successors, (27), 1 states have call predecessors, (27), 10 states have return successors, (36), 15 states have call predecessors, (36), 24 states have call successors, (36) Word has length 132 [2024-09-11 20:28:27,629 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:27,631 INFO L225 Difference]: With dead ends: 115 [2024-09-11 20:28:27,631 INFO L226 Difference]: Without dead ends: 72 [2024-09-11 20:28:27,633 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 330 GetRequests, 281 SyntacticMatches, 9 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 585 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=455, Invalid=1267, Unknown=0, NotChecked=0, Total=1722 [2024-09-11 20:28:27,635 INFO L434 NwaCegarLoop]: 19 mSDtfsCounter, 81 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 215 mSolverCounterSat, 115 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 330 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 115 IncrementalHoareTripleChecker+Valid, 215 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:27,637 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 94 Invalid, 330 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [115 Valid, 215 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-11 20:28:27,638 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-09-11 20:28:27,650 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 66. [2024-09-11 20:28:27,652 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 47 states have (on average 1.0425531914893618) internal successors, (49), 45 states have internal predecessors, (49), 11 states have call successors, (11), 9 states have call predecessors, (11), 7 states have return successors, (25), 11 states have call predecessors, (25), 11 states have call successors, (25) [2024-09-11 20:28:27,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 85 transitions. [2024-09-11 20:28:27,654 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 85 transitions. Word has length 132 [2024-09-11 20:28:27,654 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:27,654 INFO L474 AbstractCegarLoop]: Abstraction has 66 states and 85 transitions. [2024-09-11 20:28:27,654 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 30 states, 29 states have (on average 2.7586206896551726) internal successors, (80), 30 states have internal predecessors, (80), 24 states have call successors, (27), 1 states have call predecessors, (27), 10 states have return successors, (36), 15 states have call predecessors, (36), 24 states have call successors, (36) [2024-09-11 20:28:27,654 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:27,654 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 85 transitions. [2024-09-11 20:28:27,656 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 215 [2024-09-11 20:28:27,656 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:27,656 INFO L216 NwaCegarLoop]: trace histogram [31, 31, 25, 15, 15, 15, 15, 15, 15, 15, 10, 6, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:27,669 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-09-11 20:28:27,860 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-09-11 20:28:27,861 INFO L399 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:27,861 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:27,861 INFO L85 PathProgramCache]: Analyzing trace with hash -1272855121, now seen corresponding path program 5 times [2024-09-11 20:28:27,861 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:27,861 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1232076124] [2024-09-11 20:28:27,861 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:27,861 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:27,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:27,986 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:27,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,102 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,155 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,192 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,218 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,251 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,264 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:28,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,266 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:28,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,269 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:28,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,274 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,275 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:28,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,276 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:28,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,282 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,283 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,285 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,286 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:28,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,287 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:28,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,288 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 105 [2024-09-11 20:28:28,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,342 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,374 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,379 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,380 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,381 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,384 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:28,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,385 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:28,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,386 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:28,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,425 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,428 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:28,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,431 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:28,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,437 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,439 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:28,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,440 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:28,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,441 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:28,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:28,444 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 403 proven. 706 refuted. 0 times theorem prover too weak. 1471 trivial. 0 not checked. [2024-09-11 20:28:28,444 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:28,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1232076124] [2024-09-11 20:28:28,444 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1232076124] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:28,444 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1216309325] [2024-09-11 20:28:28,444 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-09-11 20:28:28,444 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:28,445 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:28,446 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:28,447 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-09-11 20:28:28,535 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 24 check-sat command(s) [2024-09-11 20:28:28,535 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-11 20:28:28,537 INFO L262 TraceCheckSpWp]: Trace formula consists of 389 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-09-11 20:28:28,540 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:28,648 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 630 proven. 586 refuted. 0 times theorem prover too weak. 1364 trivial. 0 not checked. [2024-09-11 20:28:28,648 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:29,982 INFO L134 CoverageAnalysis]: Checked inductivity of 2580 backedges. 634 proven. 619 refuted. 0 times theorem prover too weak. 1327 trivial. 0 not checked. [2024-09-11 20:28:29,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1216309325] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:29,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:29,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 14, 21] total 33 [2024-09-11 20:28:29,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [609747101] [2024-09-11 20:28:29,983 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:29,984 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-09-11 20:28:29,985 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:29,986 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-09-11 20:28:29,986 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=812, Unknown=0, NotChecked=0, Total=1056 [2024-09-11 20:28:29,986 INFO L87 Difference]: Start difference. First operand 66 states and 85 transitions. Second operand has 33 states, 32 states have (on average 2.8125) internal successors, (90), 33 states have internal predecessors, (90), 25 states have call successors, (31), 1 states have call predecessors, (31), 12 states have return successors, (42), 20 states have call predecessors, (42), 25 states have call successors, (42) [2024-09-11 20:28:30,368 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:30,368 INFO L93 Difference]: Finished difference Result 146 states and 232 transitions. [2024-09-11 20:28:30,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-09-11 20:28:30,368 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 32 states have (on average 2.8125) internal successors, (90), 33 states have internal predecessors, (90), 25 states have call successors, (31), 1 states have call predecessors, (31), 12 states have return successors, (42), 20 states have call predecessors, (42), 25 states have call successors, (42) Word has length 214 [2024-09-11 20:28:30,369 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:30,370 INFO L225 Difference]: With dead ends: 146 [2024-09-11 20:28:30,370 INFO L226 Difference]: Without dead ends: 90 [2024-09-11 20:28:30,371 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 525 GetRequests, 466 SyntacticMatches, 10 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 853 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=641, Invalid=1909, Unknown=0, NotChecked=0, Total=2550 [2024-09-11 20:28:30,371 INFO L434 NwaCegarLoop]: 24 mSDtfsCounter, 149 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 309 mSolverCounterSat, 140 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 154 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 449 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 140 IncrementalHoareTripleChecker+Valid, 309 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:30,372 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [154 Valid, 137 Invalid, 449 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [140 Valid, 309 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-11 20:28:30,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2024-09-11 20:28:30,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 83. [2024-09-11 20:28:30,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 59 states have (on average 1.0338983050847457) internal successors, (61), 57 states have internal predecessors, (61), 15 states have call successors, (15), 12 states have call predecessors, (15), 8 states have return successors, (36), 13 states have call predecessors, (36), 15 states have call successors, (36) [2024-09-11 20:28:30,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 112 transitions. [2024-09-11 20:28:30,383 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 112 transitions. Word has length 214 [2024-09-11 20:28:30,383 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:30,383 INFO L474 AbstractCegarLoop]: Abstraction has 83 states and 112 transitions. [2024-09-11 20:28:30,384 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 32 states have (on average 2.8125) internal successors, (90), 33 states have internal predecessors, (90), 25 states have call successors, (31), 1 states have call predecessors, (31), 12 states have return successors, (42), 20 states have call predecessors, (42), 25 states have call successors, (42) [2024-09-11 20:28:30,384 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:30,384 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 112 transitions. [2024-09-11 20:28:30,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 283 [2024-09-11 20:28:30,386 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:30,386 INFO L216 NwaCegarLoop]: trace histogram [41, 41, 33, 20, 20, 20, 20, 20, 20, 20, 13, 8, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:30,398 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-09-11 20:28:30,590 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:30,591 INFO L399 AbstractCegarLoop]: === Iteration 9 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:30,591 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:30,592 INFO L85 PathProgramCache]: Analyzing trace with hash 1893730074, now seen corresponding path program 6 times [2024-09-11 20:28:30,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:30,592 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1178258026] [2024-09-11 20:28:30,592 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:30,592 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:30,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:31,599 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:31,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,121 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,330 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,430 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,500 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,553 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,592 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,597 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:32,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,616 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:32,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,621 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:32,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,648 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,653 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:32,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,663 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:32,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,687 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,701 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,708 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:32,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,715 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:32,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,729 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 105 [2024-09-11 20:28:32,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,796 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,823 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,839 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,845 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:32,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,851 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:32,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,857 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:32,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,869 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,874 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:32,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,881 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 173 [2024-09-11 20:28:32,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:32,981 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:32,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,032 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:33,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,057 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:33,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,070 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:33,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,075 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:33,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,080 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:33,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,084 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:33,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,102 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:33,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,107 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:33,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,111 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:33,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,130 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:33,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,144 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:33,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,148 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:33,149 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,153 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:33,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:33,162 INFO L134 CoverageAnalysis]: Checked inductivity of 4568 backedges. 0 proven. 1500 refuted. 0 times theorem prover too weak. 3068 trivial. 0 not checked. [2024-09-11 20:28:33,162 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:33,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1178258026] [2024-09-11 20:28:33,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1178258026] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:33,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [398525193] [2024-09-11 20:28:33,162 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-09-11 20:28:33,162 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:33,162 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:33,164 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:33,165 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-09-11 20:28:33,301 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 41 check-sat command(s) [2024-09-11 20:28:33,301 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-11 20:28:33,306 INFO L262 TraceCheckSpWp]: Trace formula consists of 647 conjuncts, 167 conjuncts are in the unsatisfiable core [2024-09-11 20:28:33,325 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:33,578 INFO L134 CoverageAnalysis]: Checked inductivity of 4568 backedges. 0 proven. 1500 refuted. 0 times theorem prover too weak. 3068 trivial. 0 not checked. [2024-09-11 20:28:33,578 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:34,598 INFO L134 CoverageAnalysis]: Checked inductivity of 4568 backedges. 0 proven. 1500 refuted. 0 times theorem prover too weak. 3068 trivial. 0 not checked. [2024-09-11 20:28:34,598 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [398525193] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:34,598 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:34,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22, 22] total 28 [2024-09-11 20:28:34,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1948992480] [2024-09-11 20:28:34,598 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:34,599 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-09-11 20:28:34,599 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:34,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-09-11 20:28:34,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=691, Unknown=0, NotChecked=0, Total=756 [2024-09-11 20:28:34,600 INFO L87 Difference]: Start difference. First operand 83 states and 112 transitions. Second operand has 28 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 15 states have internal predecessors, (33), 6 states have call successors, (7), 1 states have call predecessors, (7), 7 states have return successors, (18), 18 states have call predecessors, (18), 6 states have call successors, (18) [2024-09-11 20:28:34,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:34,815 INFO L93 Difference]: Finished difference Result 104 states and 154 transitions. [2024-09-11 20:28:34,817 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-09-11 20:28:34,817 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 15 states have internal predecessors, (33), 6 states have call successors, (7), 1 states have call predecessors, (7), 7 states have return successors, (18), 18 states have call predecessors, (18), 6 states have call successors, (18) Word has length 282 [2024-09-11 20:28:34,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:34,819 INFO L225 Difference]: With dead ends: 104 [2024-09-11 20:28:34,819 INFO L226 Difference]: Without dead ends: 100 [2024-09-11 20:28:34,819 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 729 GetRequests, 703 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=65, Invalid=691, Unknown=0, NotChecked=0, Total=756 [2024-09-11 20:28:34,819 INFO L434 NwaCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 597 mSDsCounter, 0 mSdLazyCounter, 498 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 636 SdHoareTripleChecker+Invalid, 498 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 498 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:34,820 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 636 Invalid, 498 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 498 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-11 20:28:34,820 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-09-11 20:28:34,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 93. [2024-09-11 20:28:34,835 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 65 states have (on average 1.0307692307692307) internal successors, (67), 63 states have internal predecessors, (67), 17 states have call successors, (17), 12 states have call predecessors, (17), 10 states have return successors, (54), 17 states have call predecessors, (54), 17 states have call successors, (54) [2024-09-11 20:28:34,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 138 transitions. [2024-09-11 20:28:34,836 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 138 transitions. Word has length 282 [2024-09-11 20:28:34,836 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:34,837 INFO L474 AbstractCegarLoop]: Abstraction has 93 states and 138 transitions. [2024-09-11 20:28:34,837 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 15 states have internal predecessors, (33), 6 states have call successors, (7), 1 states have call predecessors, (7), 7 states have return successors, (18), 18 states have call predecessors, (18), 6 states have call successors, (18) [2024-09-11 20:28:34,837 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:34,837 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 138 transitions. [2024-09-11 20:28:34,840 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 324 [2024-09-11 20:28:34,840 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:34,840 INFO L216 NwaCegarLoop]: trace histogram [47, 47, 38, 23, 23, 23, 23, 23, 23, 23, 15, 9, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:34,852 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-09-11 20:28:35,043 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:35,044 INFO L399 AbstractCegarLoop]: === Iteration 10 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:35,044 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:35,044 INFO L85 PathProgramCache]: Analyzing trace with hash 826064675, now seen corresponding path program 7 times [2024-09-11 20:28:35,044 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:35,044 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [519283192] [2024-09-11 20:28:35,044 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:35,044 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:35,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,219 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:35,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,394 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,469 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,525 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,563 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,590 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,612 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,624 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,626 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:35,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,629 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:35,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,632 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,633 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,634 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:35,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,640 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,641 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,642 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,643 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:35,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,644 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 105 [2024-09-11 20:28:35,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,652 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,653 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,655 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,657 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,658 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,658 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:35,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,659 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:35,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,661 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,663 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,664 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 173 [2024-09-11 20:28:35,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,729 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,777 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,805 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,808 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,810 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,811 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,812 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,813 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,814 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:35,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,815 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:35,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,857 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,859 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,861 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:35,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,869 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,871 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,872 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,873 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:35,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,874 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 105 [2024-09-11 20:28:35,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,887 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,898 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:35,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,904 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:35,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,906 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:35,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:35,909 INFO L134 CoverageAnalysis]: Checked inductivity of 6039 backedges. 1307 proven. 1260 refuted. 0 times theorem prover too weak. 3472 trivial. 0 not checked. [2024-09-11 20:28:35,909 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:35,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [519283192] [2024-09-11 20:28:35,910 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [519283192] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:35,910 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1837916277] [2024-09-11 20:28:35,910 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-09-11 20:28:35,910 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:35,910 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:35,911 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:35,913 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-09-11 20:28:36,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:36,037 INFO L262 TraceCheckSpWp]: Trace formula consists of 738 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-09-11 20:28:36,040 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:36,148 INFO L134 CoverageAnalysis]: Checked inductivity of 6039 backedges. 1091 proven. 467 refuted. 0 times theorem prover too weak. 4481 trivial. 0 not checked. [2024-09-11 20:28:36,148 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:37,779 INFO L134 CoverageAnalysis]: Checked inductivity of 6039 backedges. 1091 proven. 518 refuted. 0 times theorem prover too weak. 4430 trivial. 0 not checked. [2024-09-11 20:28:37,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1837916277] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:37,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:37,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 11, 17] total 35 [2024-09-11 20:28:37,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2052278548] [2024-09-11 20:28:37,780 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:37,781 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2024-09-11 20:28:37,781 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:37,781 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-09-11 20:28:37,782 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=260, Invalid=930, Unknown=0, NotChecked=0, Total=1190 [2024-09-11 20:28:37,782 INFO L87 Difference]: Start difference. First operand 93 states and 138 transitions. Second operand has 35 states, 34 states have (on average 2.5294117647058822) internal successors, (86), 35 states have internal predecessors, (86), 24 states have call successors, (29), 1 states have call predecessors, (29), 15 states have return successors, (43), 25 states have call predecessors, (43), 24 states have call successors, (43) [2024-09-11 20:28:38,232 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:38,232 INFO L93 Difference]: Finished difference Result 226 states and 448 transitions. [2024-09-11 20:28:38,232 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-09-11 20:28:38,233 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 34 states have (on average 2.5294117647058822) internal successors, (86), 35 states have internal predecessors, (86), 24 states have call successors, (29), 1 states have call predecessors, (29), 15 states have return successors, (43), 25 states have call predecessors, (43), 24 states have call successors, (43) Word has length 323 [2024-09-11 20:28:38,233 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:38,235 INFO L225 Difference]: With dead ends: 226 [2024-09-11 20:28:38,235 INFO L226 Difference]: Without dead ends: 123 [2024-09-11 20:28:38,237 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 790 GetRequests, 725 SyntacticMatches, 8 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1171 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=765, Invalid=2657, Unknown=0, NotChecked=0, Total=3422 [2024-09-11 20:28:38,237 INFO L434 NwaCegarLoop]: 35 mSDtfsCounter, 216 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 532 mSolverCounterSat, 163 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 217 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 695 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 163 IncrementalHoareTripleChecker+Valid, 532 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:38,237 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [217 Valid, 175 Invalid, 695 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [163 Valid, 532 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-09-11 20:28:38,238 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-09-11 20:28:38,248 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 109. [2024-09-11 20:28:38,248 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 77 states have (on average 1.025974025974026) internal successors, (79), 75 states have internal predecessors, (79), 21 states have call successors, (21), 16 states have call predecessors, (21), 10 states have return successors, (46), 17 states have call predecessors, (46), 21 states have call successors, (46) [2024-09-11 20:28:38,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 146 transitions. [2024-09-11 20:28:38,249 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 146 transitions. Word has length 323 [2024-09-11 20:28:38,250 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:38,250 INFO L474 AbstractCegarLoop]: Abstraction has 109 states and 146 transitions. [2024-09-11 20:28:38,250 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 34 states have (on average 2.5294117647058822) internal successors, (86), 35 states have internal predecessors, (86), 24 states have call successors, (29), 1 states have call predecessors, (29), 15 states have return successors, (43), 25 states have call predecessors, (43), 24 states have call successors, (43) [2024-09-11 20:28:38,250 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:38,250 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 146 transitions. [2024-09-11 20:28:38,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 351 [2024-09-11 20:28:38,253 INFO L208 NwaCegarLoop]: Found error trace [2024-09-11 20:28:38,253 INFO L216 NwaCegarLoop]: trace histogram [51, 51, 41, 25, 25, 25, 25, 25, 25, 25, 16, 10, 1, 1, 1, 1, 1, 1] [2024-09-11 20:28:38,268 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-09-11 20:28:38,453 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,9 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:38,454 INFO L399 AbstractCegarLoop]: === Iteration 11 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-11 20:28:38,455 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:38,455 INFO L85 PathProgramCache]: Analyzing trace with hash 425175685, now seen corresponding path program 8 times [2024-09-11 20:28:38,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-11 20:28:38,455 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1624138548] [2024-09-11 20:28:38,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-11 20:28:38,456 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-11 20:28:38,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:38,645 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2024-09-11 20:28:38,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:38,814 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:38,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:38,928 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:38,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:38,992 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:38,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,033 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,055 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,059 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,060 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,061 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,062 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:39,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,063 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:39,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,095 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,097 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,099 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:39,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,104 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,106 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,106 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,107 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:39,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,108 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 105 [2024-09-11 20:28:39,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,116 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,118 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,120 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,120 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,121 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:39,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,122 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:39,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,124 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,124 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,125 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,126 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 173 [2024-09-11 20:28:39,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,159 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,190 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,214 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,226 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,228 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:39,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,230 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:39,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,233 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,234 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,236 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 241 [2024-09-11 20:28:39,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,247 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,251 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,254 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,256 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,257 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,257 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,258 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:39,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,259 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 37 [2024-09-11 20:28:39,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,261 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,262 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,263 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 64 [2024-09-11 20:28:39,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,266 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,267 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-09-11 20:28:39,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,269 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-09-11 20:28:39,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,270 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 23 [2024-09-11 20:28:39,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-11 20:28:39,273 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 913 proven. 1281 refuted. 0 times theorem prover too weak. 4926 trivial. 0 not checked. [2024-09-11 20:28:39,273 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-11 20:28:39,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1624138548] [2024-09-11 20:28:39,273 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1624138548] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-11 20:28:39,273 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1111943703] [2024-09-11 20:28:39,273 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-11 20:28:39,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-11 20:28:39,274 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-11 20:28:39,275 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-11 20:28:39,276 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-09-11 20:28:39,410 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-11 20:28:39,410 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-11 20:28:39,416 INFO L262 TraceCheckSpWp]: Trace formula consists of 798 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-09-11 20:28:39,420 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-11 20:28:39,522 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 419 proven. 1507 refuted. 0 times theorem prover too weak. 5194 trivial. 0 not checked. [2024-09-11 20:28:39,524 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-11 20:28:41,447 INFO L134 CoverageAnalysis]: Checked inductivity of 7120 backedges. 419 proven. 1577 refuted. 0 times theorem prover too weak. 5124 trivial. 0 not checked. [2024-09-11 20:28:41,447 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1111943703] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-11 20:28:41,447 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-11 20:28:41,447 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 12, 19] total 33 [2024-09-11 20:28:41,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1540823162] [2024-09-11 20:28:41,448 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-11 20:28:41,448 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 33 states [2024-09-11 20:28:41,448 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-11 20:28:41,449 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2024-09-11 20:28:41,449 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=249, Invalid=807, Unknown=0, NotChecked=0, Total=1056 [2024-09-11 20:28:41,450 INFO L87 Difference]: Start difference. First operand 109 states and 146 transitions. Second operand has 33 states, 32 states have (on average 2.6875) internal successors, (86), 33 states have internal predecessors, (86), 26 states have call successors, (29), 1 states have call predecessors, (29), 14 states have return successors, (43), 20 states have call predecessors, (43), 26 states have call successors, (43) [2024-09-11 20:28:41,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-11 20:28:41,754 INFO L93 Difference]: Finished difference Result 210 states and 293 transitions. [2024-09-11 20:28:41,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-09-11 20:28:41,754 INFO L78 Accepts]: Start accepts. Automaton has has 33 states, 32 states have (on average 2.6875) internal successors, (86), 33 states have internal predecessors, (86), 26 states have call successors, (29), 1 states have call predecessors, (29), 14 states have return successors, (43), 20 states have call predecessors, (43), 26 states have call successors, (43) Word has length 350 [2024-09-11 20:28:41,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-11 20:28:41,755 INFO L225 Difference]: With dead ends: 210 [2024-09-11 20:28:41,755 INFO L226 Difference]: Without dead ends: 0 [2024-09-11 20:28:41,756 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 831 GetRequests, 780 SyntacticMatches, 9 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 699 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=469, Invalid=1423, Unknown=0, NotChecked=0, Total=1892 [2024-09-11 20:28:41,756 INFO L434 NwaCegarLoop]: 35 mSDtfsCounter, 65 mSDsluCounter, 157 mSDsCounter, 0 mSdLazyCounter, 604 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 192 SdHoareTripleChecker+Invalid, 656 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 604 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-11 20:28:41,757 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [67 Valid, 192 Invalid, 656 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 604 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-11 20:28:41,757 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-09-11 20:28:41,757 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-09-11 20:28:41,757 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-09-11 20:28:41,757 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-09-11 20:28:41,757 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 350 [2024-09-11 20:28:41,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-11 20:28:41,757 INFO L474 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-09-11 20:28:41,758 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 33 states, 32 states have (on average 2.6875) internal successors, (86), 33 states have internal predecessors, (86), 26 states have call successors, (29), 1 states have call predecessors, (29), 14 states have return successors, (43), 20 states have call predecessors, (43), 26 states have call successors, (43) [2024-09-11 20:28:41,758 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-11 20:28:41,758 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-09-11 20:28:41,758 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-09-11 20:28:41,760 INFO L785 garLoopResultBuilder]: Registering result SAFE for location ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-09-11 20:28:41,773 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-09-11 20:28:41,961 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-09-11 20:28:41,964 INFO L408 BasicCegarLoop]: Path program histogram: [8, 1, 1, 1] [2024-09-11 20:28:41,965 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-09-11 20:28:44,144 INFO L165 ceAbstractionStarter]: Computing trace abstraction results [2024-09-11 20:28:44,160 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 11.09 08:28:44 BoogieIcfgContainer [2024-09-11 20:28:44,160 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-09-11 20:28:44,161 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-09-11 20:28:44,161 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-09-11 20:28:44,161 INFO L274 PluginConnector]: Witness Printer initialized [2024-09-11 20:28:44,161 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.09 08:28:21" (3/4) ... [2024-09-11 20:28:44,163 INFO L139 WitnessPrinter]: Generating witness for correct program [2024-09-11 20:28:44,173 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure fibo [2024-09-11 20:28:44,179 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 13 nodes and edges [2024-09-11 20:28:44,179 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 5 nodes and edges [2024-09-11 20:28:44,179 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-09-11 20:28:44,179 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-09-11 20:28:44,242 INFO L149 WitnessManager]: Wrote witness to /storage/repos/certificate-witnesses-artifact/automizer/witness.graphml [2024-09-11 20:28:44,242 INFO L149 WitnessManager]: Wrote witness to /storage/repos/certificate-witnesses-artifact/automizer/witness.yml [2024-09-11 20:28:44,242 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-09-11 20:28:44,242 INFO L158 Benchmark]: Toolchain (without parser) took 23071.77ms. Allocated memory was 159.4MB in the beginning and 553.6MB in the end (delta: 394.3MB). Free memory was 87.9MB in the beginning and 462.5MB in the end (delta: -374.6MB). Peak memory consumption was 21.5MB. Max. memory is 16.1GB. [2024-09-11 20:28:44,243 INFO L158 Benchmark]: CDTParser took 1.07ms. Allocated memory is still 159.4MB. Free memory was 113.9MB in the beginning and 113.8MB in the end (delta: 139.8kB). There was no memory consumed. Max. memory is 16.1GB. [2024-09-11 20:28:44,243 INFO L158 Benchmark]: CACSL2BoogieTranslator took 205.57ms. Allocated memory is still 159.4MB. Free memory was 87.8MB in the beginning and 131.1MB in the end (delta: -43.3MB). Peak memory consumption was 18.5MB. Max. memory is 16.1GB. [2024-09-11 20:28:44,243 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.25ms. Allocated memory is still 159.4MB. Free memory was 131.1MB in the beginning and 129.9MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. [2024-09-11 20:28:44,243 INFO L158 Benchmark]: Boogie Preprocessor took 19.29ms. Allocated memory is still 159.4MB. Free memory was 129.9MB in the beginning and 128.3MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-09-11 20:28:44,243 INFO L158 Benchmark]: RCFGBuilder took 234.33ms. Allocated memory is still 159.4MB. Free memory was 128.3MB in the beginning and 117.4MB in the end (delta: 10.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-09-11 20:28:44,244 INFO L158 Benchmark]: TraceAbstraction took 22506.18ms. Allocated memory was 159.4MB in the beginning and 553.6MB in the end (delta: 394.3MB). Free memory was 116.8MB in the beginning and 466.7MB in the end (delta: -349.9MB). Peak memory consumption was 321.7MB. Max. memory is 16.1GB. [2024-09-11 20:28:44,244 INFO L158 Benchmark]: Witness Printer took 81.41ms. Allocated memory is still 553.6MB. Free memory was 466.7MB in the beginning and 462.5MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-09-11 20:28:44,245 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 1.07ms. Allocated memory is still 159.4MB. Free memory was 113.9MB in the beginning and 113.8MB in the end (delta: 139.8kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 205.57ms. Allocated memory is still 159.4MB. Free memory was 87.8MB in the beginning and 131.1MB in the end (delta: -43.3MB). Peak memory consumption was 18.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 20.25ms. Allocated memory is still 159.4MB. Free memory was 131.1MB in the beginning and 129.9MB in the end (delta: 1.2MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 19.29ms. Allocated memory is still 159.4MB. Free memory was 129.9MB in the beginning and 128.3MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 234.33ms. Allocated memory is still 159.4MB. Free memory was 128.3MB in the beginning and 117.4MB in the end (delta: 10.9MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * TraceAbstraction took 22506.18ms. Allocated memory was 159.4MB in the beginning and 553.6MB in the end (delta: 394.3MB). Free memory was 116.8MB in the beginning and 466.7MB in the end (delta: -349.9MB). Peak memory consumption was 321.7MB. Max. memory is 16.1GB. * Witness Printer took 81.41ms. Allocated memory is still 553.6MB. Free memory was 466.7MB in the beginning and 462.5MB in the end (delta: 4.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 29]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 17 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 20.3s, OverallIterations: 11, TraceHistogramMax: 51, PathProgramHistogramMax: 8, EmptinessCheckTime: 0.0s, AutomataDifference: 2.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 688 SdHoareTripleChecker+Valid, 1.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 653 mSDsluCounter, 1537 SdHoareTripleChecker+Invalid, 1.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1301 mSDsCounter, 613 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2720 IncrementalHoareTripleChecker+Invalid, 3333 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 613 mSolverCounterUnsat, 236 mSDtfsCounter, 2720 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 3655 GetRequests, 3317 SyntacticMatches, 47 SemanticMatches, 291 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3690 ImplicationChecksByTransitivity, 2.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=109occurred in iteration=10, InterpolantAutomatonStates: 198, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 11 MinimizatonAttempts, 41 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 14.9s InterpolantComputationTime, 2967 NumberOfCodeBlocks, 2873 NumberOfCodeBlocksAsserted, 91 NumberOfCheckSat, 4412 ConstructedInterpolants, 0 QuantifiedInterpolants, 8086 SizeOfPredicates, 36 NumberOfNonLiveVariables, 3198 ConjunctsInSsa, 267 ConjunctsInUnsatCore, 29 InterpolantComputations, 2 PerfectInterpolantSequences, 50856/65217 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 28]: Location Invariant Derived location invariant: (7 <= x) - ProcedureContractResult [Line: 7]: Procedure Contract for fibo Derived contract for procedure fibo. Ensures: (((((((((((\result == 3) && (4 == \old(n))) || ((2 == \old(n)) && (\result == 1))) || (7 < \old(n))) || (\old(n) < 1)) || ((3 == \old(n)) && (\result == 2))) || ((\result == 8) && (6 == \old(n)))) || ((\result == 1) && (1 == \old(n)))) || ((\result == 13) && (7 == \old(n)))) || ((\result == 5) && (5 == \old(n)))) && ((0 < \old(n)) || (\result == 0))) RESULT: Ultimate proved your program to be correct! [2024-09-11 20:28:44,263 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE