./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.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 04d6fb36 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/recursified_nla-digbench/recursified_sqrt1-ll.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 ac02a57e98f6481647f49b84c91fda6d0505e35fbffb37ed6b508f20e911a1af --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-tmp.dk.referee-eval-04d6fb3-m [2024-09-15 20:00:07,673 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-09-15 20:00:07,751 INFO L114 SettingsManager]: Loading settings from /storage/repos/certificate-witnesses-artifact/automizer/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-09-15 20:00:07,758 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-09-15 20:00:07,758 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-09-15 20:00:07,788 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-09-15 20:00:07,789 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-09-15 20:00:07,789 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-09-15 20:00:07,790 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-09-15 20:00:07,793 INFO L153 SettingsManager]: * Use memory slicer=true [2024-09-15 20:00:07,794 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-09-15 20:00:07,794 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-09-15 20:00:07,794 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-09-15 20:00:07,795 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-09-15 20:00:07,795 INFO L153 SettingsManager]: * Use SBE=true [2024-09-15 20:00:07,798 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-09-15 20:00:07,798 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-09-15 20:00:07,798 INFO L153 SettingsManager]: * sizeof long=4 [2024-09-15 20:00:07,799 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-09-15 20:00:07,799 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-09-15 20:00:07,799 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-09-15 20:00:07,799 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-09-15 20:00:07,800 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-09-15 20:00:07,800 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-09-15 20:00:07,800 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-09-15 20:00:07,800 INFO L153 SettingsManager]: * sizeof long double=12 [2024-09-15 20:00:07,801 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-09-15 20:00:07,801 INFO L153 SettingsManager]: * Use constant arrays=true [2024-09-15 20:00:07,801 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-09-15 20:00:07,801 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-09-15 20:00:07,801 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-09-15 20:00:07,802 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-09-15 20:00:07,802 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-15 20:00:07,802 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-09-15 20:00:07,802 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-09-15 20:00:07,803 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-09-15 20:00:07,803 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-09-15 20:00:07,803 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-09-15 20:00:07,805 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-09-15 20:00:07,805 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-09-15 20:00:07,805 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-09-15 20:00:07,805 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-09-15 20:00:07,806 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 -> ac02a57e98f6481647f49b84c91fda6d0505e35fbffb37ed6b508f20e911a1af 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-15 20:00:08,132 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-09-15 20:00:08,154 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-09-15 20:00:08,157 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-09-15 20:00:08,158 INFO L270 PluginConnector]: Initializing CDTParser... [2024-09-15 20:00:08,159 INFO L274 PluginConnector]: CDTParser initialized [2024-09-15 20:00:08,160 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/certificate-witnesses-artifact/automizer/../sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c [2024-09-15 20:00:09,594 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-09-15 20:00:09,794 INFO L384 CDTParser]: Found 1 translation units. [2024-09-15 20:00:09,796 INFO L180 CDTParser]: Scanning /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c [2024-09-15 20:00:09,805 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/certificate-witnesses-artifact/automizer/data/5dd5f5cc2/406cd05b77bf4dfea2d091cbde695632/FLAG03240ba11 [2024-09-15 20:00:09,820 INFO L435 CDTParser]: Successfully deleted /storage/repos/certificate-witnesses-artifact/automizer/data/5dd5f5cc2/406cd05b77bf4dfea2d091cbde695632 [2024-09-15 20:00:09,824 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-09-15 20:00:09,825 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-09-15 20:00:09,826 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-09-15 20:00:09,826 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-09-15 20:00:09,833 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-09-15 20:00:09,834 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.09 08:00:09" (1/1) ... [2024-09-15 20:00:09,834 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@71ea4356 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:09, skipping insertion in model container [2024-09-15 20:00:09,835 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 15.09 08:00:09" (1/1) ... [2024-09-15 20:00:09,854 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-09-15 20:00:10,003 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c[1052,1065] [2024-09-15 20:00:10,026 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-15 20:00:10,041 INFO L200 MainTranslator]: Completed pre-run [2024-09-15 20:00:10,054 WARN L248 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursified_nla-digbench/recursified_sqrt1-ll.c[1052,1065] [2024-09-15 20:00:10,062 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-15 20:00:10,081 INFO L204 MainTranslator]: Completed translation [2024-09-15 20:00:10,081 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10 WrapperNode [2024-09-15 20:00:10,081 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-09-15 20:00:10,082 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-09-15 20:00:10,083 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-09-15 20:00:10,084 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-09-15 20:00:10,090 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,097 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,104 INFO L138 Inliner]: procedures = 16, calls = 58, calls flagged for inlining = 0, calls inlined = 0, statements flattened = 0 [2024-09-15 20:00:10,104 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-09-15 20:00:10,105 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-09-15 20:00:10,105 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-09-15 20:00:10,106 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-09-15 20:00:10,115 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,115 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,117 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,136 INFO L175 MemorySlicer]: Split 33 memory accesses to 5 slices as follows [2, 8, 12, 9, 2]. 36 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0]. The 7 writes are split as follows [0, 2, 2, 2, 1]. [2024-09-15 20:00:10,138 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,138 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,147 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,151 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,152 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,156 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,159 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-09-15 20:00:10,159 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-09-15 20:00:10,162 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-09-15 20:00:10,162 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-09-15 20:00:10,163 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (1/1) ... [2024-09-15 20:00:10,168 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-15 20:00:10,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:10,196 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-15 20:00:10,198 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-15 20:00:10,255 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-09-15 20:00:10,256 INFO L130 BoogieDeclarations]: Found specification of procedure main [2024-09-15 20:00:10,256 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2024-09-15 20:00:10,256 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-09-15 20:00:10,256 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-09-15 20:00:10,256 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-09-15 20:00:10,257 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-09-15 20:00:10,258 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-09-15 20:00:10,258 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-09-15 20:00:10,258 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-09-15 20:00:10,258 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-09-15 20:00:10,258 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-09-15 20:00:10,258 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-09-15 20:00:10,259 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-09-15 20:00:10,259 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2024-09-15 20:00:10,259 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2024-09-15 20:00:10,259 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_29_to_40_0 [2024-09-15 20:00:10,259 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_29_to_40_0 [2024-09-15 20:00:10,259 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-09-15 20:00:10,259 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-09-15 20:00:10,259 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-09-15 20:00:10,259 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-09-15 20:00:10,260 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-09-15 20:00:10,260 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-09-15 20:00:10,260 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-09-15 20:00:10,260 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-09-15 20:00:10,260 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-09-15 20:00:10,260 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-09-15 20:00:10,354 INFO L242 CfgBuilder]: Building ICFG [2024-09-15 20:00:10,356 INFO L268 CfgBuilder]: Building CFG for each procedure with an implementation [2024-09-15 20:00:10,594 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-09-15 20:00:10,595 INFO L291 CfgBuilder]: Performing block encoding [2024-09-15 20:00:10,617 INFO L313 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-09-15 20:00:10,618 INFO L318 CfgBuilder]: Removed 1 assume(true) statements. [2024-09-15 20:00:10,619 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.09 08:00:10 BoogieIcfgContainer [2024-09-15 20:00:10,619 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-09-15 20:00:10,621 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-09-15 20:00:10,622 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-09-15 20:00:10,624 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-09-15 20:00:10,625 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 15.09 08:00:09" (1/3) ... [2024-09-15 20:00:10,625 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10e98982 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.09 08:00:10, skipping insertion in model container [2024-09-15 20:00:10,626 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 15.09 08:00:10" (2/3) ... [2024-09-15 20:00:10,626 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10e98982 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.09 08:00:10, skipping insertion in model container [2024-09-15 20:00:10,627 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.09 08:00:10" (3/3) ... [2024-09-15 20:00:10,628 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_sqrt1-ll.c [2024-09-15 20:00:10,642 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:All NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-09-15 20:00:10,642 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-09-15 20:00:10,700 INFO L335 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-09-15 20:00:10,708 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;@3bb6f2f8, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-09-15 20:00:10,709 INFO L337 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-09-15 20:00:10,713 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 20 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-09-15 20:00:10,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-09-15 20:00:10,720 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:10,721 INFO L216 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:00:10,722 INFO L399 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:10,727 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:10,727 INFO L85 PathProgramCache]: Analyzing trace with hash 793561350, now seen corresponding path program 1 times [2024-09-15 20:00:10,737 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:10,737 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [109879995] [2024-09-15 20:00:10,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:10,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:10,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:11,480 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-15 20:00:11,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:11,489 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-15 20:00:11,492 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:11,493 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [109879995] [2024-09-15 20:00:11,493 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [109879995] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-15 20:00:11,493 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-15 20:00:11,493 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-09-15 20:00:11,495 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1079624474] [2024-09-15 20:00:11,495 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-15 20:00:11,500 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-15 20:00:11,500 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:11,522 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-15 20:00:11,523 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-09-15 20:00:11,525 INFO L87 Difference]: Start difference. First operand has 34 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 20 states have internal predecessors, (22), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-09-15 20:00:11,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:11,773 INFO L93 Difference]: Finished difference Result 80 states and 113 transitions. [2024-09-15 20:00:11,775 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-09-15 20:00:11,776 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-09-15 20:00:11,777 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:11,783 INFO L225 Difference]: With dead ends: 80 [2024-09-15 20:00:11,783 INFO L226 Difference]: Without dead ends: 48 [2024-09-15 20:00:11,788 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2024-09-15 20:00:11,792 INFO L434 NwaCegarLoop]: 27 mSDtfsCounter, 17 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 126 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 118 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:11,795 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 160 Invalid, 126 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 118 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-15 20:00:11,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2024-09-15 20:00:11,836 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 45. [2024-09-15 20:00:11,837 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 28 states have internal predecessors, (29), 13 states have call successors, (13), 6 states have call predecessors, (13), 5 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2024-09-15 20:00:11,839 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 54 transitions. [2024-09-15 20:00:11,841 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 54 transitions. Word has length 12 [2024-09-15 20:00:11,841 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:11,841 INFO L474 AbstractCegarLoop]: Abstraction has 45 states and 54 transitions. [2024-09-15 20:00:11,841 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 6 states have internal predecessors, (7), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-09-15 20:00:11,842 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:11,842 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 54 transitions. [2024-09-15 20:00:11,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-09-15 20:00:11,843 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:11,843 INFO L216 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:00:11,843 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-09-15 20:00:11,843 INFO L399 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:11,844 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:11,844 INFO L85 PathProgramCache]: Analyzing trace with hash -179619090, now seen corresponding path program 1 times [2024-09-15 20:00:11,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:11,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1275676562] [2024-09-15 20:00:11,845 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:11,845 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:11,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:00:11,876 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [386899578] [2024-09-15 20:00:11,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:11,877 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:00:11,877 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:11,880 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-15 20:00:11,883 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-15 20:00:11,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:11,999 INFO L262 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-09-15 20:00:12,006 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:00:12,046 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:12,055 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:12,342 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-15 20:00:12,342 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:00:12,639 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 27 [2024-09-15 20:00:12,822 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-15 20:00:12,822 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:12,822 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1275676562] [2024-09-15 20:00:12,823 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:00:12,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [386899578] [2024-09-15 20:00:12,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [386899578] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-15 20:00:12,823 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-15 20:00:12,824 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 21 [2024-09-15 20:00:12,824 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [383574] [2024-09-15 20:00:12,824 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-15 20:00:12,825 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-09-15 20:00:12,825 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:12,828 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-09-15 20:00:12,829 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=360, Unknown=0, NotChecked=0, Total=420 [2024-09-15 20:00:12,829 INFO L87 Difference]: Start difference. First operand 45 states and 54 transitions. Second operand has 21 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 7 states have call successors, (8), 5 states have call predecessors, (8), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-09-15 20:00:18,066 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-09-15 20:00:22,207 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [1] [2024-09-15 20:00:22,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:22,260 INFO L93 Difference]: Finished difference Result 81 states and 95 transitions. [2024-09-15 20:00:22,260 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-09-15 20:00:22,261 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 7 states have call successors, (8), 5 states have call predecessors, (8), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 18 [2024-09-15 20:00:22,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:22,263 INFO L225 Difference]: With dead ends: 81 [2024-09-15 20:00:22,264 INFO L226 Difference]: Without dead ends: 79 [2024-09-15 20:00:22,264 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 14 SyntacticMatches, 2 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=191, Invalid=931, Unknown=0, NotChecked=0, Total=1122 [2024-09-15 20:00:22,265 INFO L434 NwaCegarLoop]: 18 mSDtfsCounter, 59 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 435 mSolverCounterSat, 33 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 470 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 435 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.8s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:22,266 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [61 Valid, 180 Invalid, 470 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 435 Invalid, 2 Unknown, 0 Unchecked, 8.8s Time] [2024-09-15 20:00:22,266 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2024-09-15 20:00:22,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 77. [2024-09-15 20:00:22,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 46 states have (on average 1.108695652173913) internal successors, (51), 49 states have internal predecessors, (51), 20 states have call successors, (20), 10 states have call predecessors, (20), 10 states have return successors, (20), 18 states have call predecessors, (20), 17 states have call successors, (20) [2024-09-15 20:00:22,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 91 transitions. [2024-09-15 20:00:22,307 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 91 transitions. Word has length 18 [2024-09-15 20:00:22,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:22,307 INFO L474 AbstractCegarLoop]: Abstraction has 77 states and 91 transitions. [2024-09-15 20:00:22,308 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 15 states have (on average 1.2) internal successors, (18), 15 states have internal predecessors, (18), 7 states have call successors, (8), 5 states have call predecessors, (8), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-09-15 20:00:22,308 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:22,309 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 91 transitions. [2024-09-15 20:00:22,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-09-15 20:00:22,310 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:22,310 INFO L216 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:00:22,329 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-09-15 20:00:22,514 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-15 20:00:22,515 INFO L399 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:22,515 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:22,515 INFO L85 PathProgramCache]: Analyzing trace with hash 1495099348, now seen corresponding path program 1 times [2024-09-15 20:00:22,515 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:22,516 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1401798621] [2024-09-15 20:00:22,516 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:22,516 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:22,539 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:00:22,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [642902925] [2024-09-15 20:00:22,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:22,543 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:00:22,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:22,545 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-15 20:00:22,547 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-15 20:00:22,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:22,627 INFO L262 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 37 conjuncts are in the unsatisfiable core [2024-09-15 20:00:22,631 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:00:22,640 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:22,648 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:22,910 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-15 20:00:22,910 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:00:23,092 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-15 20:00:23,093 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:23,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1401798621] [2024-09-15 20:00:23,093 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:00:23,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [642902925] [2024-09-15 20:00:23,093 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [642902925] provided 1 perfect and 1 imperfect interpolant sequences [2024-09-15 20:00:23,094 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-09-15 20:00:23,094 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2024-09-15 20:00:23,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [209904677] [2024-09-15 20:00:23,094 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-15 20:00:23,094 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-15 20:00:23,094 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:23,095 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-15 20:00:23,095 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-09-15 20:00:23,095 INFO L87 Difference]: Start difference. First operand 77 states and 91 transitions. Second operand has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-09-15 20:00:23,449 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:23,449 INFO L93 Difference]: Finished difference Result 91 states and 105 transitions. [2024-09-15 20:00:23,450 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-09-15 20:00:23,450 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2024-09-15 20:00:23,450 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:23,452 INFO L225 Difference]: With dead ends: 91 [2024-09-15 20:00:23,454 INFO L226 Difference]: Without dead ends: 89 [2024-09-15 20:00:23,454 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 31 SyntacticMatches, 5 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2024-09-15 20:00:23,455 INFO L434 NwaCegarLoop]: 24 mSDtfsCounter, 17 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 123 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 123 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:23,457 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 121 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 123 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-15 20:00:23,458 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2024-09-15 20:00:23,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2024-09-15 20:00:23,503 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 54 states have (on average 1.0925925925925926) internal successors, (59), 57 states have internal predecessors, (59), 20 states have call successors, (20), 12 states have call predecessors, (20), 14 states have return successors, (23), 19 states have call predecessors, (23), 17 states have call successors, (23) [2024-09-15 20:00:23,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 102 transitions. [2024-09-15 20:00:23,508 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 102 transitions. Word has length 24 [2024-09-15 20:00:23,508 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:23,508 INFO L474 AbstractCegarLoop]: Abstraction has 89 states and 102 transitions. [2024-09-15 20:00:23,509 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.0) internal successors, (12), 6 states have internal predecessors, (12), 4 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-09-15 20:00:23,509 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:23,509 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 102 transitions. [2024-09-15 20:00:23,510 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-09-15 20:00:23,510 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:23,510 INFO L216 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:00:23,530 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-15 20:00:23,711 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-15 20:00:23,711 INFO L399 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:23,712 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:23,712 INFO L85 PathProgramCache]: Analyzing trace with hash -1496297149, now seen corresponding path program 1 times [2024-09-15 20:00:23,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:23,712 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1659406335] [2024-09-15 20:00:23,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:23,713 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:23,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:24,397 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-15 20:00:24,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:24,403 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-15 20:00:24,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:24,408 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-15 20:00:24,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:24,413 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-09-15 20:00:24,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:24,420 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-09-15 20:00:24,424 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:24,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1659406335] [2024-09-15 20:00:24,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1659406335] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:00:24,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1563889899] [2024-09-15 20:00:24,424 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:24,424 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:00:24,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:24,426 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-15 20:00:24,427 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-15 20:00:24,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:24,518 INFO L262 TraceCheckSpWp]: Trace formula consists of 249 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-09-15 20:00:24,522 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:00:24,799 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 21 [2024-09-15 20:00:24,804 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 21 [2024-09-15 20:00:24,850 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2024-09-15 20:00:24,854 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:00:24,924 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 5 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-15 20:00:24,925 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:00:29,342 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 7 proven. 8 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-09-15 20:00:29,342 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1563889899] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-15 20:00:29,343 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-15 20:00:29,343 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 10] total 21 [2024-09-15 20:00:29,343 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1336202516] [2024-09-15 20:00:29,343 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-15 20:00:29,344 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-09-15 20:00:29,344 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:29,345 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-09-15 20:00:29,345 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=356, Unknown=1, NotChecked=0, Total=420 [2024-09-15 20:00:29,345 INFO L87 Difference]: Start difference. First operand 89 states and 102 transitions. Second operand has 21 states, 16 states have (on average 2.3125) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (17), 7 states have call predecessors, (17), 4 states have return successors, (10), 3 states have call predecessors, (10), 5 states have call successors, (10) [2024-09-15 20:00:31,044 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:31,044 INFO L93 Difference]: Finished difference Result 95 states and 107 transitions. [2024-09-15 20:00:31,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-09-15 20:00:31,047 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 2.3125) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (17), 7 states have call predecessors, (17), 4 states have return successors, (10), 3 states have call predecessors, (10), 5 states have call successors, (10) Word has length 34 [2024-09-15 20:00:31,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:31,048 INFO L225 Difference]: With dead ends: 95 [2024-09-15 20:00:31,048 INFO L226 Difference]: Without dead ends: 93 [2024-09-15 20:00:31,049 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 65 SyntacticMatches, 5 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=155, Invalid=774, Unknown=1, NotChecked=0, Total=930 [2024-09-15 20:00:31,050 INFO L434 NwaCegarLoop]: 24 mSDtfsCounter, 79 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 322 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 360 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 322 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:31,052 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 156 Invalid, 360 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 322 Invalid, 0 Unknown, 0 Unchecked, 1.0s Time] [2024-09-15 20:00:31,054 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-09-15 20:00:31,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-09-15 20:00:31,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 57 states have (on average 1.087719298245614) internal successors, (62), 60 states have internal predecessors, (62), 20 states have call successors, (20), 13 states have call predecessors, (20), 15 states have return successors, (23), 19 states have call predecessors, (23), 17 states have call successors, (23) [2024-09-15 20:00:31,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 105 transitions. [2024-09-15 20:00:31,116 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 105 transitions. Word has length 34 [2024-09-15 20:00:31,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:31,116 INFO L474 AbstractCegarLoop]: Abstraction has 93 states and 105 transitions. [2024-09-15 20:00:31,116 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 2.3125) internal successors, (37), 17 states have internal predecessors, (37), 9 states have call successors, (17), 7 states have call predecessors, (17), 4 states have return successors, (10), 3 states have call predecessors, (10), 5 states have call successors, (10) [2024-09-15 20:00:31,117 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:31,117 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 105 transitions. [2024-09-15 20:00:31,117 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2024-09-15 20:00:31,117 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:31,118 INFO L216 NwaCegarLoop]: trace histogram [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] [2024-09-15 20:00:31,134 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-09-15 20:00:31,318 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-15 20:00:31,319 INFO L399 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:31,319 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:31,320 INFO L85 PathProgramCache]: Analyzing trace with hash 2049263454, now seen corresponding path program 1 times [2024-09-15 20:00:31,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:31,320 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1829461173] [2024-09-15 20:00:31,321 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:31,321 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:31,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:31,601 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-15 20:00:31,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:31,629 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-15 20:00:31,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:31,737 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-15 20:00:31,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:31,742 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-15 20:00:31,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:31,747 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-15 20:00:31,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:31,751 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-09-15 20:00:31,751 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:31,751 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1829461173] [2024-09-15 20:00:31,751 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1829461173] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-15 20:00:31,751 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-15 20:00:31,751 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-09-15 20:00:31,751 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1931698127] [2024-09-15 20:00:31,752 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-15 20:00:31,752 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-15 20:00:31,752 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:31,752 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-15 20:00:31,753 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-09-15 20:00:31,753 INFO L87 Difference]: Start difference. First operand 93 states and 105 transitions. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-09-15 20:00:32,267 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:32,267 INFO L93 Difference]: Finished difference Result 99 states and 110 transitions. [2024-09-15 20:00:32,268 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-09-15 20:00:32,268 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 34 [2024-09-15 20:00:32,268 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:32,269 INFO L225 Difference]: With dead ends: 99 [2024-09-15 20:00:32,269 INFO L226 Difference]: Without dead ends: 97 [2024-09-15 20:00:32,270 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2024-09-15 20:00:32,270 INFO L434 NwaCegarLoop]: 17 mSDtfsCounter, 23 mSDsluCounter, 48 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 65 SdHoareTripleChecker+Invalid, 158 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:32,271 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 65 Invalid, 158 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-09-15 20:00:32,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2024-09-15 20:00:32,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 97. [2024-09-15 20:00:32,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 60 states have (on average 1.0833333333333333) internal successors, (65), 63 states have internal predecessors, (65), 20 states have call successors, (20), 14 states have call predecessors, (20), 16 states have return successors, (23), 19 states have call predecessors, (23), 17 states have call successors, (23) [2024-09-15 20:00:32,330 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 108 transitions. [2024-09-15 20:00:32,331 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 108 transitions. Word has length 34 [2024-09-15 20:00:32,331 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:32,331 INFO L474 AbstractCegarLoop]: Abstraction has 97 states and 108 transitions. [2024-09-15 20:00:32,331 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2024-09-15 20:00:32,332 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:32,333 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 108 transitions. [2024-09-15 20:00:32,334 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-09-15 20:00:32,334 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:32,334 INFO L216 NwaCegarLoop]: trace histogram [5, 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] [2024-09-15 20:00:32,334 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-09-15 20:00:32,334 INFO L399 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:32,335 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:32,335 INFO L85 PathProgramCache]: Analyzing trace with hash 863672261, now seen corresponding path program 1 times [2024-09-15 20:00:32,335 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:32,335 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1809002211] [2024-09-15 20:00:32,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:32,335 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:32,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:00:32,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [174669290] [2024-09-15 20:00:32,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:32,355 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:00:32,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:32,356 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-15 20:00:32,358 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-15 20:00:32,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:32,445 INFO L262 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-09-15 20:00:32,448 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:00:32,455 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:32,465 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:32,899 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 18 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-09-15 20:00:32,899 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:00:33,420 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:33,420 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1809002211] [2024-09-15 20:00:33,420 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:00:33,420 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [174669290] [2024-09-15 20:00:33,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [174669290] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:00:33,421 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-15 20:00:33,421 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2024-09-15 20:00:33,421 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [775231783] [2024-09-15 20:00:33,421 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-15 20:00:33,421 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-15 20:00:33,421 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:33,422 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-15 20:00:33,422 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2024-09-15 20:00:33,422 INFO L87 Difference]: Start difference. First operand 97 states and 108 transitions. Second operand has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-09-15 20:00:34,085 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:34,085 INFO L93 Difference]: Finished difference Result 105 states and 114 transitions. [2024-09-15 20:00:34,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-09-15 20:00:34,086 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) Word has length 40 [2024-09-15 20:00:34,086 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:34,087 INFO L225 Difference]: With dead ends: 105 [2024-09-15 20:00:34,087 INFO L226 Difference]: Without dead ends: 101 [2024-09-15 20:00:34,088 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 46 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2024-09-15 20:00:34,088 INFO L434 NwaCegarLoop]: 15 mSDtfsCounter, 26 mSDsluCounter, 53 mSDsCounter, 0 mSdLazyCounter, 165 mSolverCounterSat, 25 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 68 SdHoareTripleChecker+Invalid, 192 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 165 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:34,089 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 68 Invalid, 192 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 165 Invalid, 2 Unknown, 0 Unchecked, 0.5s Time] [2024-09-15 20:00:34,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2024-09-15 20:00:34,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 99. [2024-09-15 20:00:34,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 62 states have (on average 1.064516129032258) internal successors, (66), 64 states have internal predecessors, (66), 20 states have call successors, (20), 15 states have call predecessors, (20), 16 states have return successors, (23), 19 states have call predecessors, (23), 17 states have call successors, (23) [2024-09-15 20:00:34,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 109 transitions. [2024-09-15 20:00:34,124 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 109 transitions. Word has length 40 [2024-09-15 20:00:34,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:34,124 INFO L474 AbstractCegarLoop]: Abstraction has 99 states and 109 transitions. [2024-09-15 20:00:34,124 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 2.857142857142857) internal successors, (20), 7 states have internal predecessors, (20), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 3 states have call predecessors, (6), 3 states have call successors, (6) [2024-09-15 20:00:34,125 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:34,125 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 109 transitions. [2024-09-15 20:00:34,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-09-15 20:00:34,126 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:34,126 INFO L216 NwaCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:00:34,145 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-15 20:00:34,327 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-15 20:00:34,327 INFO L399 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:34,328 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:34,328 INFO L85 PathProgramCache]: Analyzing trace with hash 398231530, now seen corresponding path program 1 times [2024-09-15 20:00:34,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:34,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [375509161] [2024-09-15 20:00:34,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:34,329 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:34,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:00:34,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [550150340] [2024-09-15 20:00:34,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:34,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:00:34,354 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:34,356 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-15 20:00:34,358 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-15 20:00:34,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:34,452 INFO L262 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-09-15 20:00:34,454 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:00:34,470 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:34,488 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:35,009 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 30 proven. 4 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-09-15 20:00:35,009 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:00:35,401 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:35,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [375509161] [2024-09-15 20:00:35,401 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:00:35,401 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [550150340] [2024-09-15 20:00:35,401 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [550150340] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:00:35,401 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-15 20:00:35,401 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2024-09-15 20:00:35,402 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [964043654] [2024-09-15 20:00:35,402 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-15 20:00:35,402 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-15 20:00:35,402 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:35,403 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-15 20:00:35,403 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2024-09-15 20:00:35,403 INFO L87 Difference]: Start difference. First operand 99 states and 109 transitions. Second operand has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-09-15 20:00:36,146 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:36,146 INFO L93 Difference]: Finished difference Result 101 states and 110 transitions. [2024-09-15 20:00:36,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-09-15 20:00:36,146 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 46 [2024-09-15 20:00:36,147 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:36,147 INFO L225 Difference]: With dead ends: 101 [2024-09-15 20:00:36,148 INFO L226 Difference]: Without dead ends: 81 [2024-09-15 20:00:36,148 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 55 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2024-09-15 20:00:36,149 INFO L434 NwaCegarLoop]: 15 mSDtfsCounter, 18 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 148 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 65 SdHoareTripleChecker+Invalid, 171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 148 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:36,149 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 65 Invalid, 171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 148 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-09-15 20:00:36,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-09-15 20:00:36,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 81. [2024-09-15 20:00:36,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 50 states have (on average 1.06) internal successors, (53), 52 states have internal predecessors, (53), 17 states have call successors, (17), 12 states have call predecessors, (17), 13 states have return successors, (20), 16 states have call predecessors, (20), 15 states have call successors, (20) [2024-09-15 20:00:36,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 90 transitions. [2024-09-15 20:00:36,177 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 90 transitions. Word has length 46 [2024-09-15 20:00:36,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:36,177 INFO L474 AbstractCegarLoop]: Abstraction has 81 states and 90 transitions. [2024-09-15 20:00:36,177 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.0) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-09-15 20:00:36,178 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:36,178 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 90 transitions. [2024-09-15 20:00:36,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-09-15 20:00:36,182 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:36,182 INFO L216 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:00:36,199 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-15 20:00:36,382 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-15 20:00:36,383 INFO L399 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:36,383 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:36,383 INFO L85 PathProgramCache]: Analyzing trace with hash 15363389, now seen corresponding path program 1 times [2024-09-15 20:00:36,383 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:36,384 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1702334667] [2024-09-15 20:00:36,384 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:36,384 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:36,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:36,998 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-15 20:00:36,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:37,064 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-15 20:00:37,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:37,811 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-15 20:00:37,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:37,826 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-15 20:00:37,827 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:37,844 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-15 20:00:37,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:37,864 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-15 20:00:37,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:38,026 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-15 20:00:38,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:38,030 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-15 20:00:38,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:38,032 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-15 20:00:38,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:38,036 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2024-09-15 20:00:38,037 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:00:38,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1702334667] [2024-09-15 20:00:38,037 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1702334667] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:00:38,037 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [212966951] [2024-09-15 20:00:38,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:38,037 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:00:38,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:38,039 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-15 20:00:38,041 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-15 20:00:38,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:00:38,145 INFO L262 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-09-15 20:00:38,148 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:00:38,158 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:38,173 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:39,585 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:00:39,596 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:00:39,736 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 9 proven. 54 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-09-15 20:00:39,737 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:00:40,800 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [212966951] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:00:40,800 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-15 20:00:40,800 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 16] total 21 [2024-09-15 20:00:40,800 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1573500369] [2024-09-15 20:00:40,800 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-15 20:00:40,801 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-09-15 20:00:40,801 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:00:40,801 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-09-15 20:00:40,801 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=520, Unknown=0, NotChecked=0, Total=600 [2024-09-15 20:00:40,802 INFO L87 Difference]: Start difference. First operand 81 states and 90 transitions. Second operand has 21 states, 16 states have (on average 2.4375) internal successors, (39), 18 states have internal predecessors, (39), 9 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (14), 7 states have call predecessors, (14), 8 states have call successors, (14) [2024-09-15 20:00:42,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:00:42,463 INFO L93 Difference]: Finished difference Result 90 states and 99 transitions. [2024-09-15 20:00:42,463 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-09-15 20:00:42,463 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 16 states have (on average 2.4375) internal successors, (39), 18 states have internal predecessors, (39), 9 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (14), 7 states have call predecessors, (14), 8 states have call successors, (14) Word has length 58 [2024-09-15 20:00:42,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:00:42,465 INFO L225 Difference]: With dead ends: 90 [2024-09-15 20:00:42,465 INFO L226 Difference]: Without dead ends: 88 [2024-09-15 20:00:42,465 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 72 SyntacticMatches, 5 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 231 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=189, Invalid=1071, Unknown=0, NotChecked=0, Total=1260 [2024-09-15 20:00:42,466 INFO L434 NwaCegarLoop]: 15 mSDtfsCounter, 40 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 374 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 396 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 374 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-09-15 20:00:42,466 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [42 Valid, 91 Invalid, 396 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 374 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-09-15 20:00:42,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2024-09-15 20:00:42,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 87. [2024-09-15 20:00:42,502 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 54 states have (on average 1.0555555555555556) internal successors, (57), 56 states have internal predecessors, (57), 18 states have call successors, (18), 13 states have call predecessors, (18), 14 states have return successors, (21), 17 states have call predecessors, (21), 16 states have call successors, (21) [2024-09-15 20:00:42,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 96 transitions. [2024-09-15 20:00:42,503 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 96 transitions. Word has length 58 [2024-09-15 20:00:42,503 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:00:42,503 INFO L474 AbstractCegarLoop]: Abstraction has 87 states and 96 transitions. [2024-09-15 20:00:42,504 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 16 states have (on average 2.4375) internal successors, (39), 18 states have internal predecessors, (39), 9 states have call successors, (17), 6 states have call predecessors, (17), 6 states have return successors, (14), 7 states have call predecessors, (14), 8 states have call successors, (14) [2024-09-15 20:00:42,504 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:42,504 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 96 transitions. [2024-09-15 20:00:42,506 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2024-09-15 20:00:42,507 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:00:42,507 INFO L216 NwaCegarLoop]: trace histogram [8, 7, 7, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:00:42,525 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-09-15 20:00:42,707 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-15 20:00:42,707 INFO L399 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:00:42,708 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:00:42,708 INFO L85 PathProgramCache]: Analyzing trace with hash -1755980760, now seen corresponding path program 2 times [2024-09-15 20:00:42,708 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:00:42,708 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1683443116] [2024-09-15 20:00:42,708 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:00:42,708 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:00:42,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:00:42,745 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1569210325] [2024-09-15 20:00:42,745 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-15 20:00:42,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:00:42,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:00:42,747 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-15 20:00:42,749 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-15 20:00:42,866 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-15 20:00:42,866 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-15 20:00:42,868 INFO L262 TraceCheckSpWp]: Trace formula consists of 364 conjuncts, 115 conjuncts are in the unsatisfiable core [2024-09-15 20:00:42,873 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:00:42,884 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:42,904 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:00:43,038 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-09-15 20:00:43,533 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:00:43,547 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:00:44,597 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:00:44,664 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-09-15 20:00:44,664 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2024-09-15 20:00:44,679 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2024-09-15 20:00:44,679 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 7 [2024-09-15 20:00:45,217 INFO L134 CoverageAnalysis]: Checked inductivity of 118 backedges. 2 proven. 106 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-09-15 20:00:45,218 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:00:46,192 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 33 [2024-09-15 20:01:05,000 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2024-09-15 20:01:05,190 INFO L134 CoverageAnalysis]: Checked inductivity of 118 backedges. 18 proven. 44 refuted. 3 times theorem prover too weak. 53 trivial. 0 not checked. [2024-09-15 20:01:05,191 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:01:05,191 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1683443116] [2024-09-15 20:01:05,191 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:01:05,191 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1569210325] [2024-09-15 20:01:05,191 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1569210325] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-15 20:01:05,191 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-15 20:01:05,191 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 17] total 36 [2024-09-15 20:01:05,191 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [992350599] [2024-09-15 20:01:05,191 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-15 20:01:05,192 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2024-09-15 20:01:05,192 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:01:05,193 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2024-09-15 20:01:05,193 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=1129, Unknown=3, NotChecked=0, Total=1260 [2024-09-15 20:01:05,193 INFO L87 Difference]: Start difference. First operand 87 states and 96 transitions. Second operand has 36 states, 28 states have (on average 2.107142857142857) internal successors, (59), 29 states have internal predecessors, (59), 16 states have call successors, (24), 11 states have call predecessors, (24), 8 states have return successors, (15), 7 states have call predecessors, (15), 11 states have call successors, (15) [2024-09-15 20:01:16,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:01:16,925 INFO L93 Difference]: Finished difference Result 151 states and 161 transitions. [2024-09-15 20:01:16,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2024-09-15 20:01:16,926 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 28 states have (on average 2.107142857142857) internal successors, (59), 29 states have internal predecessors, (59), 16 states have call successors, (24), 11 states have call predecessors, (24), 8 states have return successors, (15), 7 states have call predecessors, (15), 11 states have call successors, (15) Word has length 62 [2024-09-15 20:01:16,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:01:16,927 INFO L225 Difference]: With dead ends: 151 [2024-09-15 20:01:16,927 INFO L226 Difference]: Without dead ends: 149 [2024-09-15 20:01:16,929 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 77 SyntacticMatches, 12 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1381 ImplicationChecksByTransitivity, 28.1s TimeCoverageRelationStatistics Valid=625, Invalid=4774, Unknown=3, NotChecked=0, Total=5402 [2024-09-15 20:01:16,930 INFO L434 NwaCegarLoop]: 39 mSDtfsCounter, 122 mSDsluCounter, 382 mSDsCounter, 0 mSdLazyCounter, 1221 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 126 SdHoareTripleChecker+Valid, 421 SdHoareTripleChecker+Invalid, 1270 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 1221 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2024-09-15 20:01:16,930 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [126 Valid, 421 Invalid, 1270 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 1221 Invalid, 0 Unknown, 0 Unchecked, 4.1s Time] [2024-09-15 20:01:16,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2024-09-15 20:01:16,989 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 135. [2024-09-15 20:01:16,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 135 states, 86 states have (on average 1.058139534883721) internal successors, (91), 89 states have internal predecessors, (91), 24 states have call successors, (24), 21 states have call predecessors, (24), 24 states have return successors, (29), 24 states have call predecessors, (29), 21 states have call successors, (29) [2024-09-15 20:01:16,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 135 states to 135 states and 144 transitions. [2024-09-15 20:01:16,991 INFO L78 Accepts]: Start accepts. Automaton has 135 states and 144 transitions. Word has length 62 [2024-09-15 20:01:16,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:01:16,991 INFO L474 AbstractCegarLoop]: Abstraction has 135 states and 144 transitions. [2024-09-15 20:01:16,991 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 28 states have (on average 2.107142857142857) internal successors, (59), 29 states have internal predecessors, (59), 16 states have call successors, (24), 11 states have call predecessors, (24), 8 states have return successors, (15), 7 states have call predecessors, (15), 11 states have call successors, (15) [2024-09-15 20:01:16,991 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:01:16,991 INFO L276 IsEmpty]: Start isEmpty. Operand 135 states and 144 transitions. [2024-09-15 20:01:16,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-09-15 20:01:16,992 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:01:16,992 INFO L216 NwaCegarLoop]: trace histogram [8, 7, 7, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:01:17,006 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-09-15 20:01:17,193 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-15 20:01:17,193 INFO L399 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:01:17,193 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:01:17,193 INFO L85 PathProgramCache]: Analyzing trace with hash 765303396, now seen corresponding path program 1 times [2024-09-15 20:01:17,194 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:01:17,194 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1816090370] [2024-09-15 20:01:17,194 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:01:17,194 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:01:17,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:01:17,219 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1630299963] [2024-09-15 20:01:17,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:01:17,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:01:17,219 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:01:17,221 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-15 20:01:17,225 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-15 20:01:17,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:01:17,344 INFO L262 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 85 conjuncts are in the unsatisfiable core [2024-09-15 20:01:17,347 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:01:17,361 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:01:17,373 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-09-15 20:01:22,299 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 26 [2024-09-15 20:01:26,788 WARN L876 $PredicateComparison]: unable to prove that (exists ((|v_func_to_recursive_line_29_to_40_0_#in~s.base_BEFORE_CALL_7| Int) (|v_func_to_recursive_line_29_to_40_0_#in~s.offset_BEFORE_CALL_7| Int) (|v_func_to_recursive_line_29_to_40_0_#in~a.offset_BEFORE_CALL_12| Int) (|v_func_to_recursive_line_29_to_40_0_#in~a.base_BEFORE_CALL_12| Int)) (<= (select (select |c_#memory_int#1| |v_func_to_recursive_line_29_to_40_0_#in~s.base_BEFORE_CALL_7|) |v_func_to_recursive_line_29_to_40_0_#in~s.offset_BEFORE_CALL_7|) (let ((.cse0 (select (select |c_#memory_int#3| |v_func_to_recursive_line_29_to_40_0_#in~a.base_BEFORE_CALL_12|) |v_func_to_recursive_line_29_to_40_0_#in~a.offset_BEFORE_CALL_12|))) (+ (* .cse0 2) (* .cse0 .cse0) 1)))) is different from true [2024-09-15 20:01:39,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 13 [2024-09-15 20:01:39,915 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:01:56,768 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 27 proven. 58 refuted. 8 times theorem prover too weak. 12 trivial. 4 not checked. [2024-09-15 20:01:56,768 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:02:02,573 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 48 treesize of output 40 [2024-09-15 20:02:03,797 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 22 [2024-09-15 20:02:08,440 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:02:08,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1816090370] [2024-09-15 20:02:08,441 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:02:08,441 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1630299963] [2024-09-15 20:02:08,441 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1630299963] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:02:08,441 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-15 20:02:08,441 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2024-09-15 20:02:08,441 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1852609984] [2024-09-15 20:02:08,441 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-15 20:02:08,441 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-09-15 20:02:08,442 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:02:08,442 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-09-15 20:02:08,442 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=616, Unknown=8, NotChecked=50, Total=756 [2024-09-15 20:02:08,443 INFO L87 Difference]: Start difference. First operand 135 states and 144 transitions. Second operand has 22 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 19 states have internal predecessors, (35), 10 states have call successors, (12), 6 states have call predecessors, (12), 7 states have return successors, (10), 6 states have call predecessors, (10), 9 states have call successors, (10) [2024-09-15 20:02:16,942 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:02:16,942 INFO L93 Difference]: Finished difference Result 143 states and 150 transitions. [2024-09-15 20:02:16,942 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-09-15 20:02:16,942 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 19 states have internal predecessors, (35), 10 states have call successors, (12), 6 states have call predecessors, (12), 7 states have return successors, (10), 6 states have call predecessors, (10), 9 states have call successors, (10) Word has length 64 [2024-09-15 20:02:16,943 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:02:16,944 INFO L225 Difference]: With dead ends: 143 [2024-09-15 20:02:16,944 INFO L226 Difference]: Without dead ends: 139 [2024-09-15 20:02:16,945 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 52 SyntacticMatches, 7 SemanticMatches, 49 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 526 ImplicationChecksByTransitivity, 54.2s TimeCoverageRelationStatistics Valid=297, Invalid=2148, Unknown=9, NotChecked=96, Total=2550 [2024-09-15 20:02:16,945 INFO L434 NwaCegarLoop]: 15 mSDtfsCounter, 38 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 562 mSolverCounterSat, 33 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 655 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 562 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 59 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-09-15 20:02:16,946 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [40 Valid, 91 Invalid, 655 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 562 Invalid, 1 Unknown, 59 Unchecked, 1.9s Time] [2024-09-15 20:02:16,946 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2024-09-15 20:02:17,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 137. [2024-09-15 20:02:17,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 88 states have (on average 1.0454545454545454) internal successors, (92), 90 states have internal predecessors, (92), 24 states have call successors, (24), 22 states have call predecessors, (24), 24 states have return successors, (29), 24 states have call predecessors, (29), 21 states have call successors, (29) [2024-09-15 20:02:17,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 145 transitions. [2024-09-15 20:02:17,025 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 145 transitions. Word has length 64 [2024-09-15 20:02:17,025 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:02:17,025 INFO L474 AbstractCegarLoop]: Abstraction has 137 states and 145 transitions. [2024-09-15 20:02:17,025 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 17 states have (on average 2.0588235294117645) internal successors, (35), 19 states have internal predecessors, (35), 10 states have call successors, (12), 6 states have call predecessors, (12), 7 states have return successors, (10), 6 states have call predecessors, (10), 9 states have call successors, (10) [2024-09-15 20:02:17,026 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:02:17,026 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 145 transitions. [2024-09-15 20:02:17,028 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-09-15 20:02:17,030 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:02:17,030 INFO L216 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:02:17,049 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-09-15 20:02:17,230 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-15 20:02:17,231 INFO L399 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:02:17,231 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:02:17,231 INFO L85 PathProgramCache]: Analyzing trace with hash 1393874761, now seen corresponding path program 1 times [2024-09-15 20:02:17,231 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:02:17,231 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1587325206] [2024-09-15 20:02:17,231 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:02:17,232 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:02:17,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:02:17,260 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [735376844] [2024-09-15 20:02:17,261 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:02:17,261 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:02:17,261 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:02:17,263 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-15 20:02:17,264 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-15 20:02:17,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:17,391 INFO L262 TraceCheckSpWp]: Trace formula consists of 335 conjuncts, 81 conjuncts are in the unsatisfiable core [2024-09-15 20:02:17,394 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:02:17,409 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:02:17,441 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:02:17,461 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:02:18,450 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2024-09-15 20:02:18,542 INFO L349 Elim1Store]: treesize reduction 16, result has 55.6 percent of original size [2024-09-15 20:02:18,543 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 32 [2024-09-15 20:02:18,621 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:02:21,332 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 61 proven. 17 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2024-09-15 20:02:21,332 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:02:27,822 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:02:27,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1587325206] [2024-09-15 20:02:27,823 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:02:27,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [735376844] [2024-09-15 20:02:27,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [735376844] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:02:27,823 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-15 20:02:27,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-09-15 20:02:27,823 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [477771056] [2024-09-15 20:02:27,823 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-15 20:02:27,824 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-09-15 20:02:27,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:02:27,824 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-09-15 20:02:27,824 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=479, Unknown=1, NotChecked=0, Total=552 [2024-09-15 20:02:27,825 INFO L87 Difference]: Start difference. First operand 137 states and 145 transitions. Second operand has 17 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) [2024-09-15 20:02:32,204 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:02:32,204 INFO L93 Difference]: Finished difference Result 139 states and 146 transitions. [2024-09-15 20:02:32,204 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-09-15 20:02:32,205 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) Word has length 70 [2024-09-15 20:02:32,205 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:02:32,206 INFO L225 Difference]: With dead ends: 139 [2024-09-15 20:02:32,206 INFO L226 Difference]: Without dead ends: 117 [2024-09-15 20:02:32,206 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 62 SyntacticMatches, 3 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 172 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=174, Invalid=1015, Unknown=1, NotChecked=0, Total=1190 [2024-09-15 20:02:32,207 INFO L434 NwaCegarLoop]: 15 mSDtfsCounter, 14 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 428 mSolverCounterSat, 17 mSolverCounterUnsat, 8 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 453 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 428 IncrementalHoareTripleChecker+Invalid, 8 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-09-15 20:02:32,207 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 76 Invalid, 453 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 428 Invalid, 8 Unknown, 0 Unchecked, 2.2s Time] [2024-09-15 20:02:32,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-09-15 20:02:32,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 117. [2024-09-15 20:02:32,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 117 states, 75 states have (on average 1.04) internal successors, (78), 77 states have internal predecessors, (78), 21 states have call successors, (21), 19 states have call predecessors, (21), 20 states have return successors, (25), 20 states have call predecessors, (25), 19 states have call successors, (25) [2024-09-15 20:02:32,281 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 117 states to 117 states and 124 transitions. [2024-09-15 20:02:32,281 INFO L78 Accepts]: Start accepts. Automaton has 117 states and 124 transitions. Word has length 70 [2024-09-15 20:02:32,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:02:32,281 INFO L474 AbstractCegarLoop]: Abstraction has 117 states and 124 transitions. [2024-09-15 20:02:32,282 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 13 states have (on average 2.3846153846153846) internal successors, (31), 14 states have internal predecessors, (31), 8 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (11), 6 states have call predecessors, (11), 7 states have call successors, (11) [2024-09-15 20:02:32,282 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:02:32,282 INFO L276 IsEmpty]: Start isEmpty. Operand 117 states and 124 transitions. [2024-09-15 20:02:32,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2024-09-15 20:02:32,283 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:02:32,283 INFO L216 NwaCegarLoop]: trace histogram [10, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:02:32,296 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-09-15 20:02:32,483 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-15 20:02:32,483 INFO L399 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:02:32,484 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:02:32,484 INFO L85 PathProgramCache]: Analyzing trace with hash 657256540, now seen corresponding path program 2 times [2024-09-15 20:02:32,484 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:02:32,484 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1115428743] [2024-09-15 20:02:32,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:02:32,484 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:02:32,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:33,489 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-15 20:02:33,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:33,558 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-15 20:02:33,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:34,673 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-15 20:02:34,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:34,689 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-15 20:02:34,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:34,705 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-15 20:02:34,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:34,721 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-15 20:02:34,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:35,526 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-15 20:02:35,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:35,531 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-15 20:02:35,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:35,535 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-15 20:02:35,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:35,541 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-15 20:02:35,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:36,364 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-15 20:02:36,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:36,369 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-15 20:02:36,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:36,372 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-15 20:02:36,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-15 20:02:36,376 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 31 proven. 16 refuted. 0 times theorem prover too weak. 149 trivial. 0 not checked. [2024-09-15 20:02:36,376 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:02:36,376 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1115428743] [2024-09-15 20:02:36,376 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1115428743] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:02:36,376 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1421618741] [2024-09-15 20:02:36,377 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-15 20:02:36,377 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:02:36,377 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:02:36,378 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-15 20:02:36,382 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-09-15 20:02:36,524 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-15 20:02:36,524 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-15 20:02:36,526 INFO L262 TraceCheckSpWp]: Trace formula consists of 405 conjuncts, 76 conjuncts are in the unsatisfiable core [2024-09-15 20:02:36,530 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:02:37,983 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 21 [2024-09-15 20:02:37,993 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 21 [2024-09-15 20:02:38,382 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 15 [2024-09-15 20:02:38,393 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:02:38,603 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 58 proven. 64 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-09-15 20:02:38,604 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:02:40,531 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-15 20:02:40,531 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 92 treesize of output 91 [2024-09-15 20:02:40,561 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-15 20:02:40,561 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 108 treesize of output 99 [2024-09-15 20:02:41,225 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1421618741] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:02:41,225 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-15 20:02:41,225 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 14] total 26 [2024-09-15 20:02:41,226 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [999279533] [2024-09-15 20:02:41,226 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-15 20:02:41,226 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-09-15 20:02:41,226 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:02:41,227 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-09-15 20:02:41,227 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=592, Unknown=0, NotChecked=0, Total=702 [2024-09-15 20:02:41,227 INFO L87 Difference]: Start difference. First operand 117 states and 124 transitions. Second operand has 26 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 23 states have internal predecessors, (54), 14 states have call successors, (28), 6 states have call predecessors, (28), 7 states have return successors, (25), 11 states have call predecessors, (25), 13 states have call successors, (25) [2024-09-15 20:02:43,669 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-15 20:02:43,669 INFO L93 Difference]: Finished difference Result 123 states and 129 transitions. [2024-09-15 20:02:43,670 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-09-15 20:02:43,670 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 23 states have internal predecessors, (54), 14 states have call successors, (28), 6 states have call predecessors, (28), 7 states have return successors, (25), 11 states have call predecessors, (25), 13 states have call successors, (25) Word has length 82 [2024-09-15 20:02:43,670 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-15 20:02:43,671 INFO L225 Difference]: With dead ends: 123 [2024-09-15 20:02:43,671 INFO L226 Difference]: Without dead ends: 121 [2024-09-15 20:02:43,672 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 112 SyntacticMatches, 5 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 420 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=260, Invalid=1222, Unknown=0, NotChecked=0, Total=1482 [2024-09-15 20:02:43,672 INFO L434 NwaCegarLoop]: 13 mSDtfsCounter, 58 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 400 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 446 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 400 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-09-15 20:02:43,672 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 81 Invalid, 446 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 400 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-09-15 20:02:43,673 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-09-15 20:02:43,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 121. [2024-09-15 20:02:43,749 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 78 states have (on average 1.0384615384615385) internal successors, (81), 80 states have internal predecessors, (81), 21 states have call successors, (21), 20 states have call predecessors, (21), 21 states have return successors, (25), 20 states have call predecessors, (25), 19 states have call successors, (25) [2024-09-15 20:02:43,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 127 transitions. [2024-09-15 20:02:43,750 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 127 transitions. Word has length 82 [2024-09-15 20:02:43,751 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-15 20:02:43,751 INFO L474 AbstractCegarLoop]: Abstraction has 121 states and 127 transitions. [2024-09-15 20:02:43,751 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 23 states have internal predecessors, (54), 14 states have call successors, (28), 6 states have call predecessors, (28), 7 states have return successors, (25), 11 states have call predecessors, (25), 13 states have call successors, (25) [2024-09-15 20:02:43,752 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:02:43,752 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 127 transitions. [2024-09-15 20:02:43,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2024-09-15 20:02:43,753 INFO L208 NwaCegarLoop]: Found error trace [2024-09-15 20:02:43,753 INFO L216 NwaCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-15 20:02:43,776 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-09-15 20:02:43,957 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-09-15 20:02:43,958 INFO L399 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-15 20:02:43,958 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-15 20:02:43,958 INFO L85 PathProgramCache]: Analyzing trace with hash 1385368131, now seen corresponding path program 2 times [2024-09-15 20:02:43,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-15 20:02:43,958 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1516399449] [2024-09-15 20:02:43,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-15 20:02:43,959 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-15 20:02:43,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-15 20:02:43,990 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [275602964] [2024-09-15 20:02:43,990 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-15 20:02:43,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-15 20:02:43,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-15 20:02:43,994 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-15 20:02:43,997 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-09-15 20:02:44,153 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-15 20:02:44,154 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-15 20:02:44,164 INFO L262 TraceCheckSpWp]: Trace formula consists of 420 conjuncts, 161 conjuncts are in the unsatisfiable core [2024-09-15 20:02:44,169 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-15 20:02:44,180 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:02:44,197 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:02:44,216 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-15 20:03:25,310 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 25 [2024-09-15 20:03:25,427 INFO L349 Elim1Store]: treesize reduction 12, result has 62.5 percent of original size [2024-09-15 20:03:25,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 31 treesize of output 42 [2024-09-15 20:03:25,546 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2024-09-15 20:03:25,546 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 25 [2024-09-15 20:03:25,598 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-09-15 20:03:25,823 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-15 20:03:25,823 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 31 treesize of output 23 [2024-09-15 20:03:27,271 INFO L134 CoverageAnalysis]: Checked inductivity of 234 backedges. 50 proven. 142 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2024-09-15 20:03:27,272 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-15 20:03:42,509 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-15 20:03:42,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1516399449] [2024-09-15 20:03:42,509 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-15 20:03:42,509 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [275602964] [2024-09-15 20:03:42,509 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [275602964] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-15 20:03:42,510 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-15 20:03:42,510 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [32] total 32 [2024-09-15 20:03:42,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [557831671] [2024-09-15 20:03:42,510 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-15 20:03:42,510 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2024-09-15 20:03:42,510 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-15 20:03:42,511 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2024-09-15 20:03:42,511 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=1323, Unknown=11, NotChecked=0, Total=1482 [2024-09-15 20:03:42,511 INFO L87 Difference]: Start difference. First operand 121 states and 127 transitions. Second operand has 32 states, 24 states have (on average 1.7916666666666667) internal successors, (43), 26 states have internal predecessors, (43), 13 states have call successors, (16), 6 states have call predecessors, (16), 8 states have return successors, (14), 9 states have call predecessors, (14), 12 states have call successors, (14) [2024-09-15 20:03:46,772 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-09-15 20:03:56,314 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-09-15 20:04:04,650 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-09-15 20:04:13,031 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-09-15 20:04:17,122 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-09-15 20:04:25,477 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0] [2024-09-15 20:04:29,608 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [0]