./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound50.c --full-output --procedureinliner.inline.calls.to.implemented.procedures NEVER --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 1d5fa637 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/nla-digbench-scaling/egcd-ll_valuebound50.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 3134c54bcf8aadaf562f6870f2277db1ec6f958b1ed6dba99e7410745dba79ba --procedureinliner.inline.calls.to.implemented.procedures NEVER --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-1d5fa63-m [2024-09-13 09:14:36,054 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-09-13 09:14:36,129 INFO L114 SettingsManager]: Loading settings from /storage/repos/certificate-witnesses-artifact/automizer/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-09-13 09:14:36,134 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-09-13 09:14:36,135 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-09-13 09:14:36,157 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-09-13 09:14:36,158 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-09-13 09:14:36,158 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-09-13 09:14:36,159 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-09-13 09:14:36,159 INFO L153 SettingsManager]: * Use memory slicer=true [2024-09-13 09:14:36,159 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-09-13 09:14:36,160 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-09-13 09:14:36,160 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-09-13 09:14:36,161 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-09-13 09:14:36,161 INFO L153 SettingsManager]: * Use SBE=true [2024-09-13 09:14:36,163 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-09-13 09:14:36,164 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-09-13 09:14:36,164 INFO L153 SettingsManager]: * sizeof long=4 [2024-09-13 09:14:36,164 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-09-13 09:14:36,166 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-09-13 09:14:36,167 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-09-13 09:14:36,169 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-09-13 09:14:36,169 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-09-13 09:14:36,170 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-09-13 09:14:36,171 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-09-13 09:14:36,171 INFO L153 SettingsManager]: * sizeof long double=12 [2024-09-13 09:14:36,171 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-09-13 09:14:36,171 INFO L153 SettingsManager]: * Use constant arrays=true [2024-09-13 09:14:36,172 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-09-13 09:14:36,172 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-09-13 09:14:36,172 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-09-13 09:14:36,173 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-09-13 09:14:36,173 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-13 09:14:36,174 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-09-13 09:14:36,174 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-09-13 09:14:36,174 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-09-13 09:14:36,175 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-09-13 09:14:36,175 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-09-13 09:14:36,175 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-09-13 09:14:36,176 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-09-13 09:14:36,176 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-09-13 09:14:36,176 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-09-13 09:14:36,176 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 -> 3134c54bcf8aadaf562f6870f2277db1ec6f958b1ed6dba99e7410745dba79ba Applying setting for plugin de.uni_freiburg.informatik.ultimate.boogie.procedureinliner: Inline calls to implemented procedures -> NEVER 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-13 09:14:36,417 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-09-13 09:14:36,441 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-09-13 09:14:36,444 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-09-13 09:14:36,445 INFO L270 PluginConnector]: Initializing CDTParser... [2024-09-13 09:14:36,446 INFO L274 PluginConnector]: CDTParser initialized [2024-09-13 09:14:36,447 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/certificate-witnesses-artifact/automizer/../sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound50.c [2024-09-13 09:14:37,851 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-09-13 09:14:38,041 INFO L384 CDTParser]: Found 1 translation units. [2024-09-13 09:14:38,042 INFO L180 CDTParser]: Scanning /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/nla-digbench-scaling/egcd-ll_valuebound50.c [2024-09-13 09:14:38,050 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/certificate-witnesses-artifact/automizer/data/0399c43e0/35a6c7bdfb8a4fc0a6d5277cd7dd5161/FLAG0930643da [2024-09-13 09:14:38,061 INFO L435 CDTParser]: Successfully deleted /storage/repos/certificate-witnesses-artifact/automizer/data/0399c43e0/35a6c7bdfb8a4fc0a6d5277cd7dd5161 [2024-09-13 09:14:38,063 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-09-13 09:14:38,065 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-09-13 09:14:38,066 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-09-13 09:14:38,066 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-09-13 09:14:38,071 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-09-13 09:14:38,072 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,073 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@18166ffd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38, skipping insertion in model container [2024-09-13 09:14:38,073 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,091 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-09-13 09:14:38,220 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/nla-digbench-scaling/egcd-ll_valuebound50.c[489,502] [2024-09-13 09:14:38,241 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-13 09:14:38,249 INFO L200 MainTranslator]: Completed pre-run [2024-09-13 09:14:38,260 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/nla-digbench-scaling/egcd-ll_valuebound50.c[489,502] [2024-09-13 09:14:38,271 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-13 09:14:38,290 INFO L204 MainTranslator]: Completed translation [2024-09-13 09:14:38,291 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38 WrapperNode [2024-09-13 09:14:38,291 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-09-13 09:14:38,292 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-09-13 09:14:38,292 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-09-13 09:14:38,293 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-09-13 09:14:38,299 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,306 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,313 INFO L138 Inliner]: procedures = 14, calls = 18, calls flagged for inlining = 0, calls inlined = 0, statements flattened = 0 [2024-09-13 09:14:38,313 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-09-13 09:14:38,314 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-09-13 09:14:38,314 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-09-13 09:14:38,314 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-09-13 09:14:38,323 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,324 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,325 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,336 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-13 09:14:38,337 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,337 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,340 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,343 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,344 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,344 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,346 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-09-13 09:14:38,347 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-09-13 09:14:38,347 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-09-13 09:14:38,347 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-09-13 09:14:38,348 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (1/1) ... [2024-09-13 09:14:38,357 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-13 09:14:38,371 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:38,387 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-13 09:14:38,393 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-13 09:14:38,464 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-09-13 09:14:38,465 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-09-13 09:14:38,465 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-09-13 09:14:38,465 INFO L130 BoogieDeclarations]: Found specification of procedure main [2024-09-13 09:14:38,465 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2024-09-13 09:14:38,465 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-09-13 09:14:38,466 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2024-09-13 09:14:38,468 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2024-09-13 09:14:38,468 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-09-13 09:14:38,469 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-09-13 09:14:38,469 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-09-13 09:14:38,470 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-09-13 09:14:38,554 INFO L242 CfgBuilder]: Building ICFG [2024-09-13 09:14:38,556 INFO L268 CfgBuilder]: Building CFG for each procedure with an implementation [2024-09-13 09:14:38,739 INFO L? ?]: Removed 4 outVars from TransFormulas that were not future-live. [2024-09-13 09:14:38,739 INFO L291 CfgBuilder]: Performing block encoding [2024-09-13 09:14:38,762 INFO L313 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-09-13 09:14:38,762 INFO L318 CfgBuilder]: Removed 1 assume(true) statements. [2024-09-13 09:14:38,763 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.09 09:14:38 BoogieIcfgContainer [2024-09-13 09:14:38,763 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-09-13 09:14:38,765 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-09-13 09:14:38,765 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-09-13 09:14:38,768 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-09-13 09:14:38,769 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 13.09 09:14:38" (1/3) ... [2024-09-13 09:14:38,769 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4da11e96 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 13.09 09:14:38, skipping insertion in model container [2024-09-13 09:14:38,769 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.09 09:14:38" (2/3) ... [2024-09-13 09:14:38,770 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4da11e96 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 13.09 09:14:38, skipping insertion in model container [2024-09-13 09:14:38,770 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.09 09:14:38" (3/3) ... [2024-09-13 09:14:38,771 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound50.c [2024-09-13 09:14:38,786 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:All NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-09-13 09:14:38,786 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-09-13 09:14:38,841 INFO L335 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-09-13 09:14:38,847 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;@dfaa493, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-09-13 09:14:38,848 INFO L337 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-09-13 09:14:38,851 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 16 states have (on average 1.4375) internal successors, (23), 17 states have internal predecessors, (23), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-09-13 09:14:38,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-09-13 09:14:38,859 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:38,860 INFO L216 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:38,860 INFO L399 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:38,868 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:38,869 INFO L85 PathProgramCache]: Analyzing trace with hash 963610160, now seen corresponding path program 1 times [2024-09-13 09:14:38,877 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:38,877 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [622651469] [2024-09-13 09:14:38,877 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:38,878 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:38,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,024 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-13 09:14:39,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,044 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-13 09:14:39,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,058 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-13 09:14:39,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,064 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-09-13 09:14:39,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,069 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-13 09:14:39,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,075 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-09-13 09:14:39,075 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:39,075 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [622651469] [2024-09-13 09:14:39,076 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [622651469] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-13 09:14:39,078 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-13 09:14:39,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-09-13 09:14:39,080 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [849570231] [2024-09-13 09:14:39,081 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:39,084 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-09-13 09:14:39,084 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:39,103 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-09-13 09:14:39,104 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-09-13 09:14:39,106 INFO L87 Difference]: Start difference. First operand has 35 states, 16 states have (on average 1.4375) internal successors, (23), 17 states have internal predecessors, (23), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-09-13 09:14:39,145 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:39,146 INFO L93 Difference]: Finished difference Result 64 states and 102 transitions. [2024-09-13 09:14:39,151 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-09-13 09:14:39,152 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 32 [2024-09-13 09:14:39,152 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:39,160 INFO L225 Difference]: With dead ends: 64 [2024-09-13 09:14:39,160 INFO L226 Difference]: Without dead ends: 31 [2024-09-13 09:14:39,165 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-09-13 09:14:39,169 INFO L434 NwaCegarLoop]: 43 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:39,170 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 43 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-13 09:14:39,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2024-09-13 09:14:39,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2024-09-13 09:14:39,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 31 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 15 states have internal predecessors, (17), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-09-13 09:14:39,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 41 transitions. [2024-09-13 09:14:39,213 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 41 transitions. Word has length 32 [2024-09-13 09:14:39,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:39,214 INFO L474 AbstractCegarLoop]: Abstraction has 31 states and 41 transitions. [2024-09-13 09:14:39,215 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-09-13 09:14:39,215 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:39,217 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 41 transitions. [2024-09-13 09:14:39,218 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2024-09-13 09:14:39,219 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:39,220 INFO L216 NwaCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:39,220 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-09-13 09:14:39,220 INFO L399 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:39,221 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:39,222 INFO L85 PathProgramCache]: Analyzing trace with hash -914175556, now seen corresponding path program 1 times [2024-09-13 09:14:39,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:39,222 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1062007718] [2024-09-13 09:14:39,222 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:39,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:39,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-13 09:14:39,282 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [501303647] [2024-09-13 09:14:39,282 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:39,282 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:39,283 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:39,285 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-13 09:14:39,286 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-13 09:14:39,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,362 INFO L262 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-09-13 09:14:39,371 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:39,487 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-09-13 09:14:39,488 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-09-13 09:14:39,488 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:39,488 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1062007718] [2024-09-13 09:14:39,488 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-13 09:14:39,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [501303647] [2024-09-13 09:14:39,489 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [501303647] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-13 09:14:39,489 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-13 09:14:39,489 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-09-13 09:14:39,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1937777251] [2024-09-13 09:14:39,490 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:39,492 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-13 09:14:39,492 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:39,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-13 09:14:39,493 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-13 09:14:39,493 INFO L87 Difference]: Start difference. First operand 31 states and 41 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-09-13 09:14:39,563 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:39,564 INFO L93 Difference]: Finished difference Result 47 states and 64 transitions. [2024-09-13 09:14:39,565 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-13 09:14:39,565 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 32 [2024-09-13 09:14:39,565 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:39,566 INFO L225 Difference]: With dead ends: 47 [2024-09-13 09:14:39,567 INFO L226 Difference]: Without dead ends: 45 [2024-09-13 09:14:39,567 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-09-13 09:14:39,568 INFO L434 NwaCegarLoop]: 34 mSDtfsCounter, 5 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:39,570 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 129 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-13 09:14:39,571 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-09-13 09:14:39,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2024-09-13 09:14:39,585 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 20 states have (on average 1.25) internal successors, (25), 22 states have internal predecessors, (25), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-09-13 09:14:39,587 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 61 transitions. [2024-09-13 09:14:39,589 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 61 transitions. Word has length 32 [2024-09-13 09:14:39,589 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:39,589 INFO L474 AbstractCegarLoop]: Abstraction has 44 states and 61 transitions. [2024-09-13 09:14:39,589 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2024-09-13 09:14:39,590 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:39,590 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 61 transitions. [2024-09-13 09:14:39,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2024-09-13 09:14:39,591 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:39,591 INFO L216 NwaCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:39,606 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-09-13 09:14:39,792 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:39,792 INFO L399 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:39,793 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:39,793 INFO L85 PathProgramCache]: Analyzing trace with hash 737940505, now seen corresponding path program 1 times [2024-09-13 09:14:39,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:39,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1998760181] [2024-09-13 09:14:39,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:39,793 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:39,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-13 09:14:39,833 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [230851639] [2024-09-13 09:14:39,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:39,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:39,835 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:39,837 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-13 09:14:39,838 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-13 09:14:39,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:39,922 INFO L262 TraceCheckSpWp]: Trace formula consists of 99 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-09-13 09:14:39,924 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:40,004 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-09-13 09:14:40,005 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-09-13 09:14:40,005 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:40,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1998760181] [2024-09-13 09:14:40,007 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-13 09:14:40,007 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [230851639] [2024-09-13 09:14:40,007 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [230851639] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-13 09:14:40,008 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-13 09:14:40,008 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-09-13 09:14:40,008 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [267318214] [2024-09-13 09:14:40,008 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:40,008 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-13 09:14:40,008 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:40,009 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-13 09:14:40,009 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-13 09:14:40,009 INFO L87 Difference]: Start difference. First operand 44 states and 61 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-09-13 09:14:40,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:40,081 INFO L93 Difference]: Finished difference Result 51 states and 67 transitions. [2024-09-13 09:14:40,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-13 09:14:40,081 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 37 [2024-09-13 09:14:40,082 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:40,082 INFO L225 Difference]: With dead ends: 51 [2024-09-13 09:14:40,083 INFO L226 Difference]: Without dead ends: 49 [2024-09-13 09:14:40,084 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-09-13 09:14:40,086 INFO L434 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 95 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:40,087 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 131 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-13 09:14:40,088 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-09-13 09:14:40,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 48. [2024-09-13 09:14:40,102 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 48 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 25 states have internal predecessors, (28), 19 states have call successors, (19), 6 states have call predecessors, (19), 5 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2024-09-13 09:14:40,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 64 transitions. [2024-09-13 09:14:40,104 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 64 transitions. Word has length 37 [2024-09-13 09:14:40,104 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:40,104 INFO L474 AbstractCegarLoop]: Abstraction has 48 states and 64 transitions. [2024-09-13 09:14:40,105 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-09-13 09:14:40,105 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:40,105 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 64 transitions. [2024-09-13 09:14:40,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-09-13 09:14:40,110 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:40,110 INFO L216 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:40,124 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-09-13 09:14:40,311 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:40,311 INFO L399 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:40,312 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:40,312 INFO L85 PathProgramCache]: Analyzing trace with hash 1385223068, now seen corresponding path program 1 times [2024-09-13 09:14:40,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:40,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1000601997] [2024-09-13 09:14:40,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:40,312 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:40,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-13 09:14:40,351 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [613727700] [2024-09-13 09:14:40,351 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:40,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:40,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:40,353 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-13 09:14:40,356 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-13 09:14:40,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:40,408 INFO L262 TraceCheckSpWp]: Trace formula consists of 108 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-09-13 09:14:40,410 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:40,465 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-09-13 09:14:40,465 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-09-13 09:14:40,466 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:40,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1000601997] [2024-09-13 09:14:40,466 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-13 09:14:40,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613727700] [2024-09-13 09:14:40,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [613727700] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-13 09:14:40,466 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-13 09:14:40,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-09-13 09:14:40,467 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [268009567] [2024-09-13 09:14:40,467 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:40,467 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-13 09:14:40,467 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:40,468 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-13 09:14:40,468 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-13 09:14:40,468 INFO L87 Difference]: Start difference. First operand 48 states and 64 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-09-13 09:14:40,538 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:40,539 INFO L93 Difference]: Finished difference Result 73 states and 104 transitions. [2024-09-13 09:14:40,539 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-13 09:14:40,539 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 42 [2024-09-13 09:14:40,540 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:40,545 INFO L225 Difference]: With dead ends: 73 [2024-09-13 09:14:40,545 INFO L226 Difference]: Without dead ends: 69 [2024-09-13 09:14:40,546 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 38 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-09-13 09:14:40,547 INFO L434 NwaCegarLoop]: 36 mSDtfsCounter, 6 mSDsluCounter, 94 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 130 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:40,548 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 130 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-13 09:14:40,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2024-09-13 09:14:40,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 69. [2024-09-13 09:14:40,573 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 32 states have (on average 1.28125) internal successors, (41), 36 states have internal predecessors, (41), 30 states have call successors, (30), 7 states have call predecessors, (30), 6 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2024-09-13 09:14:40,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 97 transitions. [2024-09-13 09:14:40,575 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 97 transitions. Word has length 42 [2024-09-13 09:14:40,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:40,576 INFO L474 AbstractCegarLoop]: Abstraction has 69 states and 97 transitions. [2024-09-13 09:14:40,576 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-09-13 09:14:40,577 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:40,577 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 97 transitions. [2024-09-13 09:14:40,578 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-09-13 09:14:40,578 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:40,578 INFO L216 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:40,594 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-13 09:14:40,782 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:40,783 INFO L399 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:40,783 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:40,783 INFO L85 PathProgramCache]: Analyzing trace with hash -1071635405, now seen corresponding path program 1 times [2024-09-13 09:14:40,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:40,783 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1829396966] [2024-09-13 09:14:40,784 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:40,785 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:40,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:40,995 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-13 09:14:40,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,002 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-13 09:14:41,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,010 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-13 09:14:41,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,016 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-09-13 09:14:41,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,024 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-13 09:14:41,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,027 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-09-13 09:14:41,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,034 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-09-13 09:14:41,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,037 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-09-13 09:14:41,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,044 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-09-13 09:14:41,045 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:41,045 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1829396966] [2024-09-13 09:14:41,045 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1829396966] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-13 09:14:41,045 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-13 09:14:41,045 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-09-13 09:14:41,046 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [892362732] [2024-09-13 09:14:41,046 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:41,046 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-13 09:14:41,046 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:41,047 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-13 09:14:41,048 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-13 09:14:41,048 INFO L87 Difference]: Start difference. First operand 69 states and 97 transitions. Second operand has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 1 states have call predecessors, (8), 1 states have call successors, (8) [2024-09-13 09:14:41,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:41,104 INFO L93 Difference]: Finished difference Result 75 states and 102 transitions. [2024-09-13 09:14:41,104 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-13 09:14:41,104 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 1 states have call predecessors, (8), 1 states have call successors, (8) Word has length 48 [2024-09-13 09:14:41,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:41,106 INFO L225 Difference]: With dead ends: 75 [2024-09-13 09:14:41,107 INFO L226 Difference]: Without dead ends: 73 [2024-09-13 09:14:41,107 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-09-13 09:14:41,108 INFO L434 NwaCegarLoop]: 40 mSDtfsCounter, 3 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 140 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:41,109 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 140 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-13 09:14:41,112 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-09-13 09:14:41,128 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 73. [2024-09-13 09:14:41,128 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 73 states, 35 states have (on average 1.2571428571428571) internal successors, (44), 39 states have internal predecessors, (44), 30 states have call successors, (30), 8 states have call predecessors, (30), 7 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2024-09-13 09:14:41,129 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 73 states to 73 states and 100 transitions. [2024-09-13 09:14:41,130 INFO L78 Accepts]: Start accepts. Automaton has 73 states and 100 transitions. Word has length 48 [2024-09-13 09:14:41,131 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:41,133 INFO L474 AbstractCegarLoop]: Abstraction has 73 states and 100 transitions. [2024-09-13 09:14:41,134 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 3.75) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 1 states have call predecessors, (8), 1 states have call successors, (8) [2024-09-13 09:14:41,134 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:41,134 INFO L276 IsEmpty]: Start isEmpty. Operand 73 states and 100 transitions. [2024-09-13 09:14:41,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2024-09-13 09:14:41,135 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:41,136 INFO L216 NwaCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:41,136 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-09-13 09:14:41,136 INFO L399 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:41,136 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:41,136 INFO L85 PathProgramCache]: Analyzing trace with hash 1501538128, now seen corresponding path program 1 times [2024-09-13 09:14:41,137 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:41,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [783207507] [2024-09-13 09:14:41,137 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:41,137 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:41,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-13 09:14:41,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [428492173] [2024-09-13 09:14:41,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:41,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:41,178 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:41,180 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-13 09:14:41,184 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-13 09:14:41,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,242 INFO L262 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-09-13 09:14:41,245 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:41,349 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2024-09-13 09:14:41,350 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-09-13 09:14:41,351 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:41,351 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [783207507] [2024-09-13 09:14:41,351 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-13 09:14:41,351 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [428492173] [2024-09-13 09:14:41,351 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [428492173] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-13 09:14:41,351 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-13 09:14:41,352 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-09-13 09:14:41,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [176711562] [2024-09-13 09:14:41,352 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:41,354 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-13 09:14:41,354 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:41,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-13 09:14:41,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-09-13 09:14:41,355 INFO L87 Difference]: Start difference. First operand 73 states and 100 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-09-13 09:14:41,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:41,410 INFO L93 Difference]: Finished difference Result 83 states and 108 transitions. [2024-09-13 09:14:41,410 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-13 09:14:41,410 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 50 [2024-09-13 09:14:41,411 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:41,412 INFO L225 Difference]: With dead ends: 83 [2024-09-13 09:14:41,412 INFO L226 Difference]: Without dead ends: 80 [2024-09-13 09:14:41,412 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 46 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-09-13 09:14:41,413 INFO L434 NwaCegarLoop]: 35 mSDtfsCounter, 4 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 132 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:41,413 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 132 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-13 09:14:41,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 80 states. [2024-09-13 09:14:41,429 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 80 to 78. [2024-09-13 09:14:41,430 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 41 states have (on average 1.2195121951219512) internal successors, (50), 44 states have internal predecessors, (50), 27 states have call successors, (27), 10 states have call predecessors, (27), 9 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-09-13 09:14:41,431 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 101 transitions. [2024-09-13 09:14:41,432 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 101 transitions. Word has length 50 [2024-09-13 09:14:41,432 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:41,432 INFO L474 AbstractCegarLoop]: Abstraction has 78 states and 101 transitions. [2024-09-13 09:14:41,433 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-09-13 09:14:41,433 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:41,433 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 101 transitions. [2024-09-13 09:14:41,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2024-09-13 09:14:41,435 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:41,435 INFO L216 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:41,451 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-13 09:14:41,635 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-13 09:14:41,636 INFO L399 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:41,636 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:41,636 INFO L85 PathProgramCache]: Analyzing trace with hash 789508930, now seen corresponding path program 1 times [2024-09-13 09:14:41,636 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:41,636 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1530741222] [2024-09-13 09:14:41,636 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:41,637 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:41,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,855 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-13 09:14:41,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,857 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-13 09:14:41,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,860 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-13 09:14:41,861 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,863 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-09-13 09:14:41,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,866 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-13 09:14:41,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,868 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-09-13 09:14:41,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,872 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-09-13 09:14:41,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,904 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-09-13 09:14:41,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,918 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-09-13 09:14:41,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,922 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-09-13 09:14:41,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:41,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1530741222] [2024-09-13 09:14:41,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1530741222] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-13 09:14:41,922 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1898136847] [2024-09-13 09:14:41,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:41,923 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:41,923 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:41,925 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-13 09:14:41,926 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-13 09:14:41,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:41,984 INFO L262 TraceCheckSpWp]: Trace formula consists of 128 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-09-13 09:14:41,986 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:42,100 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-09-13 09:14:42,101 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-09-13 09:14:42,102 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1898136847] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-13 09:14:42,102 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-09-13 09:14:42,102 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 11 [2024-09-13 09:14:42,102 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1017782003] [2024-09-13 09:14:42,102 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:42,104 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-09-13 09:14:42,105 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:42,105 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-09-13 09:14:42,105 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-09-13 09:14:42,105 INFO L87 Difference]: Start difference. First operand 78 states and 101 transitions. Second operand has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-09-13 09:14:42,206 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:42,206 INFO L93 Difference]: Finished difference Result 91 states and 113 transitions. [2024-09-13 09:14:42,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-09-13 09:14:42,207 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 53 [2024-09-13 09:14:42,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:42,208 INFO L225 Difference]: With dead ends: 91 [2024-09-13 09:14:42,208 INFO L226 Difference]: Without dead ends: 87 [2024-09-13 09:14:42,208 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=119, Unknown=0, NotChecked=0, Total=156 [2024-09-13 09:14:42,209 INFO L434 NwaCegarLoop]: 34 mSDtfsCounter, 6 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 58 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 65 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 58 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:42,209 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 157 Invalid, 65 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 58 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-13 09:14:42,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2024-09-13 09:14:42,222 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 86. [2024-09-13 09:14:42,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 47 states have (on average 1.1702127659574468) internal successors, (55), 50 states have internal predecessors, (55), 27 states have call successors, (27), 12 states have call predecessors, (27), 11 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-09-13 09:14:42,225 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 106 transitions. [2024-09-13 09:14:42,225 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 106 transitions. Word has length 53 [2024-09-13 09:14:42,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:42,226 INFO L474 AbstractCegarLoop]: Abstraction has 86 states and 106 transitions. [2024-09-13 09:14:42,227 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 3.0) internal successors, (15), 5 states have internal predecessors, (15), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-09-13 09:14:42,228 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:42,228 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 106 transitions. [2024-09-13 09:14:42,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2024-09-13 09:14:42,229 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:42,229 INFO L216 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:42,245 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-09-13 09:14:42,433 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-13 09:14:42,434 INFO L399 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:42,434 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:42,434 INFO L85 PathProgramCache]: Analyzing trace with hash 1427018501, now seen corresponding path program 2 times [2024-09-13 09:14:42,434 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:42,434 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1018116360] [2024-09-13 09:14:42,434 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:42,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:42,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-13 09:14:42,450 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1333903247] [2024-09-13 09:14:42,450 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-13 09:14:42,450 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:42,450 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:42,452 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-13 09:14:42,454 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-13 09:14:42,505 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-13 09:14:42,505 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-13 09:14:42,510 INFO L262 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-09-13 09:14:42,512 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:42,801 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 25 proven. 4 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-09-13 09:14:42,802 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-13 09:14:43,358 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-09-13 09:14:43,358 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:43,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1018116360] [2024-09-13 09:14:43,358 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-13 09:14:43,358 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1333903247] [2024-09-13 09:14:43,358 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1333903247] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-13 09:14:43,358 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-13 09:14:43,359 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 17 [2024-09-13 09:14:43,359 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1079655985] [2024-09-13 09:14:43,359 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-13 09:14:43,359 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-09-13 09:14:43,359 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:43,360 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-09-13 09:14:43,360 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2024-09-13 09:14:43,360 INFO L87 Difference]: Start difference. First operand 86 states and 106 transitions. Second operand has 17 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 3 states have call predecessors, (16), 3 states have return successors, (14), 6 states have call predecessors, (14), 5 states have call successors, (14) [2024-09-13 09:14:47,704 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.91s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-09-13 09:14:47,887 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:47,887 INFO L93 Difference]: Finished difference Result 128 states and 166 transitions. [2024-09-13 09:14:47,887 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-09-13 09:14:47,888 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 3 states have call predecessors, (16), 3 states have return successors, (14), 6 states have call predecessors, (14), 5 states have call successors, (14) Word has length 55 [2024-09-13 09:14:47,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:47,889 INFO L225 Difference]: With dead ends: 128 [2024-09-13 09:14:47,889 INFO L226 Difference]: Without dead ends: 126 [2024-09-13 09:14:47,890 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=101, Invalid=405, Unknown=0, NotChecked=0, Total=506 [2024-09-13 09:14:47,891 INFO L434 NwaCegarLoop]: 27 mSDtfsCounter, 30 mSDsluCounter, 225 mSDsCounter, 0 mSdLazyCounter, 319 mSolverCounterSat, 56 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 375 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 56 IncrementalHoareTripleChecker+Valid, 319 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:47,891 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 252 Invalid, 375 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [56 Valid, 319 Invalid, 0 Unknown, 0 Unchecked, 4.3s Time] [2024-09-13 09:14:47,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-09-13 09:14:47,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 94. [2024-09-13 09:14:47,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 53 states have (on average 1.150943396226415) internal successors, (61), 56 states have internal predecessors, (61), 27 states have call successors, (27), 14 states have call predecessors, (27), 13 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2024-09-13 09:14:47,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 112 transitions. [2024-09-13 09:14:47,921 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 112 transitions. Word has length 55 [2024-09-13 09:14:47,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:47,922 INFO L474 AbstractCegarLoop]: Abstraction has 94 states and 112 transitions. [2024-09-13 09:14:47,922 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.1333333333333333) internal successors, (32), 13 states have internal predecessors, (32), 7 states have call successors, (16), 3 states have call predecessors, (16), 3 states have return successors, (14), 6 states have call predecessors, (14), 5 states have call successors, (14) [2024-09-13 09:14:47,922 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:47,922 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 112 transitions. [2024-09-13 09:14:47,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-09-13 09:14:47,923 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:47,923 INFO L216 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:47,940 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-09-13 09:14:48,127 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-13 09:14:48,128 INFO L399 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:48,128 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:48,128 INFO L85 PathProgramCache]: Analyzing trace with hash 1563984878, now seen corresponding path program 1 times [2024-09-13 09:14:48,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:48,129 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2145211979] [2024-09-13 09:14:48,129 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:48,129 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:48,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-13 09:14:48,144 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1096237283] [2024-09-13 09:14:48,144 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:48,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:48,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:48,146 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-13 09:14:48,148 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-13 09:14:48,199 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:48,200 INFO L262 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-09-13 09:14:48,202 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:48,569 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 21 proven. 17 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-09-13 09:14:48,570 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-13 09:14:48,998 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 9 proven. 17 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-09-13 09:14:48,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:48,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2145211979] [2024-09-13 09:14:48,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-13 09:14:48,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1096237283] [2024-09-13 09:14:48,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1096237283] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-13 09:14:49,000 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-13 09:14:49,000 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 9] total 19 [2024-09-13 09:14:49,000 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [969949731] [2024-09-13 09:14:49,001 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-13 09:14:49,001 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-09-13 09:14:49,001 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:49,002 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-09-13 09:14:49,003 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=282, Unknown=0, NotChecked=0, Total=342 [2024-09-13 09:14:49,003 INFO L87 Difference]: Start difference. First operand 94 states and 112 transitions. Second operand has 19 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 15 states have internal predecessors, (32), 7 states have call successors, (19), 3 states have call predecessors, (19), 3 states have return successors, (17), 7 states have call predecessors, (17), 7 states have call successors, (17) [2024-09-13 09:14:53,495 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-09-13 09:14:54,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:54,063 INFO L93 Difference]: Finished difference Result 135 states and 175 transitions. [2024-09-13 09:14:54,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-09-13 09:14:54,063 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 15 states have internal predecessors, (32), 7 states have call successors, (19), 3 states have call predecessors, (19), 3 states have return successors, (17), 7 states have call predecessors, (17), 7 states have call successors, (17) Word has length 60 [2024-09-13 09:14:54,064 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:54,065 INFO L225 Difference]: With dead ends: 135 [2024-09-13 09:14:54,065 INFO L226 Difference]: Without dead ends: 117 [2024-09-13 09:14:54,066 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=110, Invalid=442, Unknown=0, NotChecked=0, Total=552 [2024-09-13 09:14:54,066 INFO L434 NwaCegarLoop]: 27 mSDtfsCounter, 28 mSDsluCounter, 216 mSDsCounter, 0 mSdLazyCounter, 313 mSolverCounterSat, 58 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 372 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 313 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.8s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:54,067 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 243 Invalid, 372 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 313 Invalid, 1 Unknown, 0 Unchecked, 4.8s Time] [2024-09-13 09:14:54,067 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-09-13 09:14:54,097 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 90. [2024-09-13 09:14:54,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 53 states have (on average 1.1320754716981132) internal successors, (60), 55 states have internal predecessors, (60), 23 states have call successors, (23), 14 states have call predecessors, (23), 13 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2024-09-13 09:14:54,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 103 transitions. [2024-09-13 09:14:54,099 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 103 transitions. Word has length 60 [2024-09-13 09:14:54,099 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:54,099 INFO L474 AbstractCegarLoop]: Abstraction has 90 states and 103 transitions. [2024-09-13 09:14:54,099 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 1.7777777777777777) internal successors, (32), 15 states have internal predecessors, (32), 7 states have call successors, (19), 3 states have call predecessors, (19), 3 states have return successors, (17), 7 states have call predecessors, (17), 7 states have call successors, (17) [2024-09-13 09:14:54,100 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:54,100 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 103 transitions. [2024-09-13 09:14:54,101 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-09-13 09:14:54,101 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:54,101 INFO L216 NwaCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:54,117 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-09-13 09:14:54,301 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-13 09:14:54,302 INFO L399 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:54,303 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:54,303 INFO L85 PathProgramCache]: Analyzing trace with hash 1657370914, now seen corresponding path program 1 times [2024-09-13 09:14:54,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:54,303 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [89770469] [2024-09-13 09:14:54,303 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:54,303 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:54,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-13 09:14:54,323 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [164555687] [2024-09-13 09:14:54,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:54,323 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:54,323 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:54,325 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-13 09:14:54,334 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-13 09:14:54,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:54,388 INFO L262 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-09-13 09:14:54,390 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:54,523 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-09-13 09:14:54,523 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-13 09:14:54,611 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2024-09-13 09:14:54,612 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:54,612 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [89770469] [2024-09-13 09:14:54,612 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-13 09:14:54,612 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [164555687] [2024-09-13 09:14:54,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [164555687] provided 1 perfect and 1 imperfect interpolant sequences [2024-09-13 09:14:54,613 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-09-13 09:14:54,613 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2024-09-13 09:14:54,613 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1943022051] [2024-09-13 09:14:54,613 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-13 09:14:54,614 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-09-13 09:14:54,614 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:54,614 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-09-13 09:14:54,614 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-09-13 09:14:54,615 INFO L87 Difference]: Start difference. First operand 90 states and 103 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-09-13 09:14:54,728 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:54,728 INFO L93 Difference]: Finished difference Result 96 states and 108 transitions. [2024-09-13 09:14:54,729 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-09-13 09:14:54,729 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 68 [2024-09-13 09:14:54,731 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:54,732 INFO L225 Difference]: With dead ends: 96 [2024-09-13 09:14:54,733 INFO L226 Difference]: Without dead ends: 91 [2024-09-13 09:14:54,734 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 127 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-09-13 09:14:54,734 INFO L434 NwaCegarLoop]: 33 mSDtfsCounter, 4 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:54,735 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 117 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-13 09:14:54,735 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-09-13 09:14:54,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 89. [2024-09-13 09:14:54,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 55 states have (on average 1.1090909090909091) internal successors, (61), 55 states have internal predecessors, (61), 20 states have call successors, (20), 15 states have call predecessors, (20), 13 states have return successors, (18), 18 states have call predecessors, (18), 18 states have call successors, (18) [2024-09-13 09:14:54,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 99 transitions. [2024-09-13 09:14:54,762 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 99 transitions. Word has length 68 [2024-09-13 09:14:54,762 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:54,762 INFO L474 AbstractCegarLoop]: Abstraction has 89 states and 99 transitions. [2024-09-13 09:14:54,762 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-09-13 09:14:54,763 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:54,763 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 99 transitions. [2024-09-13 09:14:54,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 72 [2024-09-13 09:14:54,764 INFO L208 NwaCegarLoop]: Found error trace [2024-09-13 09:14:54,764 INFO L216 NwaCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:54,781 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-09-13 09:14:54,964 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-13 09:14:54,965 INFO L399 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-13 09:14:54,965 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:54,965 INFO L85 PathProgramCache]: Analyzing trace with hash -335668690, now seen corresponding path program 1 times [2024-09-13 09:14:54,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-13 09:14:54,965 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [458375240] [2024-09-13 09:14:54,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:54,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-13 09:14:54,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,146 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-13 09:14:55,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,149 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-13 09:14:55,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,151 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-13 09:14:55,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,153 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2024-09-13 09:14:55,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,154 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-13 09:14:55,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,156 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2024-09-13 09:14:55,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,158 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2024-09-13 09:14:55,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,159 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-09-13 09:14:55,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,161 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2024-09-13 09:14:55,161 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,162 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 51 [2024-09-13 09:14:55,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,185 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 56 [2024-09-13 09:14:55,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,195 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 62 [2024-09-13 09:14:55,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,198 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-09-13 09:14:55,198 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-13 09:14:55,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [458375240] [2024-09-13 09:14:55,199 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [458375240] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-13 09:14:55,199 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1713217279] [2024-09-13 09:14:55,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-13 09:14:55,199 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-13 09:14:55,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-13 09:14:55,201 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-13 09:14:55,202 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-13 09:14:55,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-13 09:14:55,252 INFO L262 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-09-13 09:14:55,253 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-13 09:14:55,298 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-09-13 09:14:55,299 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-13 09:14:55,398 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 27 proven. 7 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-09-13 09:14:55,399 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1713217279] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-13 09:14:55,399 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-13 09:14:55,399 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8, 8] total 11 [2024-09-13 09:14:55,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1802127986] [2024-09-13 09:14:55,400 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-13 09:14:55,400 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-09-13 09:14:55,400 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-13 09:14:55,401 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-09-13 09:14:55,401 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2024-09-13 09:14:55,401 INFO L87 Difference]: Start difference. First operand 89 states and 99 transitions. Second operand has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2024-09-13 09:14:55,571 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-13 09:14:55,571 INFO L93 Difference]: Finished difference Result 96 states and 107 transitions. [2024-09-13 09:14:55,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-09-13 09:14:55,572 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) Word has length 71 [2024-09-13 09:14:55,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-13 09:14:55,573 INFO L225 Difference]: With dead ends: 96 [2024-09-13 09:14:55,573 INFO L226 Difference]: Without dead ends: 0 [2024-09-13 09:14:55,573 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2024-09-13 09:14:55,574 INFO L434 NwaCegarLoop]: 26 mSDtfsCounter, 7 mSDsluCounter, 151 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 177 SdHoareTripleChecker+Invalid, 100 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-13 09:14:55,574 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [8 Valid, 177 Invalid, 100 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-13 09:14:55,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-09-13 09:14:55,575 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-09-13 09:14:55,575 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-13 09:14:55,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-09-13 09:14:55,575 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 71 [2024-09-13 09:14:55,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-13 09:14:55,575 INFO L474 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-09-13 09:14:55,576 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 2.5) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (13), 4 states have call predecessors, (13), 4 states have call successors, (13) [2024-09-13 09:14:55,576 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-13 09:14:55,576 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-09-13 09:14:55,576 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-09-13 09:14:55,578 INFO L785 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-09-13 09:14:55,595 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-09-13 09:14:55,782 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-13 09:14:55,787 INFO L408 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-13 09:14:55,789 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2024-09-13 09:15:07,397 WARN L293 SmtUtils]: Spent 7.61s on a formula simplification. DAG size of input: 85 DAG size of output: 36 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2024-09-13 09:15:26,667 WARN L293 SmtUtils]: Spent 11.40s on a formula simplification. DAG size of input: 76 DAG size of output: 36 (called from [L 162] de.uni_freiburg.informatik.ultimate.lib.proofs.floydhoare.HoareAnnotationComposer.combineInter) [2024-09-13 09:15:30,958 INFO L165 ceAbstractionStarter]: Computing trace abstraction results [2024-09-13 09:15:30,973 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 13.09 09:15:30 BoogieIcfgContainer [2024-09-13 09:15:30,974 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-09-13 09:15:30,974 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-09-13 09:15:30,974 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-09-13 09:15:30,974 INFO L274 PluginConnector]: Witness Printer initialized [2024-09-13 09:15:30,975 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.09 09:14:38" (3/4) ... [2024-09-13 09:15:30,976 INFO L139 WitnessPrinter]: Generating witness for correct program [2024-09-13 09:15:30,980 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure ULTIMATE.init [2024-09-13 09:15:30,980 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure assume_abort_if_not [2024-09-13 09:15:30,980 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure main [2024-09-13 09:15:30,980 INFO L361 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2024-09-13 09:15:30,983 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 18 nodes and edges [2024-09-13 09:15:30,983 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 6 nodes and edges [2024-09-13 09:15:30,984 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2024-09-13 09:15:30,984 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-09-13 09:15:30,984 INFO L896 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2024-09-13 09:15:31,067 INFO L149 WitnessManager]: Wrote witness to /storage/repos/certificate-witnesses-artifact/automizer/witness.graphml [2024-09-13 09:15:31,068 INFO L149 WitnessManager]: Wrote witness to /storage/repos/certificate-witnesses-artifact/automizer/witness.yml [2024-09-13 09:15:31,068 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-09-13 09:15:31,068 INFO L158 Benchmark]: Toolchain (without parser) took 53003.64ms. Allocated memory was 142.6MB in the beginning and 257.9MB in the end (delta: 115.3MB). Free memory was 73.4MB in the beginning and 150.2MB in the end (delta: -76.8MB). Peak memory consumption was 39.3MB. Max. memory is 16.1GB. [2024-09-13 09:15:31,068 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 142.6MB. Free memory is still 94.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-09-13 09:15:31,069 INFO L158 Benchmark]: CACSL2BoogieTranslator took 225.07ms. Allocated memory is still 142.6MB. Free memory was 73.2MB in the beginning and 61.5MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-09-13 09:15:31,069 INFO L158 Benchmark]: Boogie Procedure Inliner took 21.45ms. Allocated memory is still 142.6MB. Free memory was 61.4MB in the beginning and 60.4MB in the end (delta: 939.0kB). There was no memory consumed. Max. memory is 16.1GB. [2024-09-13 09:15:31,069 INFO L158 Benchmark]: Boogie Preprocessor took 32.13ms. Allocated memory is still 142.6MB. Free memory was 60.4MB in the beginning and 58.7MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-09-13 09:15:31,070 INFO L158 Benchmark]: RCFGBuilder took 416.20ms. Allocated memory was 142.6MB in the beginning and 213.9MB in the end (delta: 71.3MB). Free memory was 58.6MB in the beginning and 178.7MB in the end (delta: -120.1MB). Peak memory consumption was 10.8MB. Max. memory is 16.1GB. [2024-09-13 09:15:31,070 INFO L158 Benchmark]: TraceAbstraction took 52208.43ms. Allocated memory was 213.9MB in the beginning and 257.9MB in the end (delta: 44.0MB). Free memory was 177.7MB in the beginning and 155.4MB in the end (delta: 22.3MB). Peak memory consumption was 146.0MB. Max. memory is 16.1GB. [2024-09-13 09:15:31,070 INFO L158 Benchmark]: Witness Printer took 93.79ms. Allocated memory is still 257.9MB. Free memory was 155.4MB in the beginning and 150.2MB in the end (delta: 5.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-09-13 09:15:31,071 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.17ms. Allocated memory is still 142.6MB. Free memory is still 94.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 225.07ms. Allocated memory is still 142.6MB. Free memory was 73.2MB in the beginning and 61.5MB in the end (delta: 11.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 21.45ms. Allocated memory is still 142.6MB. Free memory was 61.4MB in the beginning and 60.4MB in the end (delta: 939.0kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 32.13ms. Allocated memory is still 142.6MB. Free memory was 60.4MB in the beginning and 58.7MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 416.20ms. Allocated memory was 142.6MB in the beginning and 213.9MB in the end (delta: 71.3MB). Free memory was 58.6MB in the beginning and 178.7MB in the end (delta: -120.1MB). Peak memory consumption was 10.8MB. Max. memory is 16.1GB. * TraceAbstraction took 52208.43ms. Allocated memory was 213.9MB in the beginning and 257.9MB in the end (delta: 44.0MB). Free memory was 177.7MB in the beginning and 155.4MB in the end (delta: 22.3MB). Peak memory consumption was 146.0MB. Max. memory is 16.1GB. * Witness Printer took 93.79ms. Allocated memory is still 257.9MB. Free memory was 155.4MB in the beginning and 150.2MB in the end (delta: 5.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: 13]: 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 5 procedures, 35 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 17.0s, OverallIterations: 11, TraceHistogramMax: 8, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 10.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 125 SdHoareTripleChecker+Valid, 9.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 99 mSDsluCounter, 1651 SdHoareTripleChecker+Invalid, 9.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1280 mSDsCounter, 130 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 987 IncrementalHoareTripleChecker+Invalid, 1118 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 130 mSolverCounterUnsat, 371 mSDtfsCounter, 987 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 830 GetRequests, 734 SyntacticMatches, 4 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 197 ImplicationChecksByTransitivity, 1.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=94occurred in iteration=8, InterpolantAutomatonStates: 79, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 11 MinimizatonAttempts, 66 StatesRemovedByMinimization, 7 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 3.3s InterpolantComputationTime, 1016 NumberOfCodeBlocks, 1016 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 909 ConstructedInterpolants, 0 QuantifiedInterpolants, 2752 SizeOfPredicates, 18 NumberOfNonLiveVariables, 1156 ConjunctsInSsa, 154 ConjunctsInUnsatCore, 17 InterpolantComputations, 8 PerfectInterpolantSequences, 1091/1171 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: 35]: Loop Invariant Derived loop invariant: (((((b == (((__int128) q * x) + ((__int128) y * s))) && (1 <= x)) && (a == (((__int128) y * r) + ((__int128) p * x)))) && (1 <= y)) && (((__int128) p * s) == (((__int128) q * r) + 1))) - ProcedureContractResult [Line: 7]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not. Ensures: (\old(cond) != 0) - ProcedureContractResult [Line: 10]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert. Requires: (1 <= \old(cond)) Ensures: (1 <= \old(cond)) RESULT: Ultimate proved your program to be correct! [2024-09-13 09:15:31,097 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