./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_hard-ll.c --full-output --procedureinliner.inline.calls.to.implemented.procedures NEVER --traceabstraction.positions.where.we.compute.the.hoare.annotation All --traceabstraction.encode.modifies.clause.in.ensures.clause.of.contracts true --witnessprinter.yaml.format.version 2.1 --witnessprinter.generate.graphml.witnesses false --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version fb1cb0b9 Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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_hard-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 dfbeed813c4c61f00fa3f37e016718a299be7911d54e721c8910a31480a25397 --procedureinliner.inline.calls.to.implemented.procedures NEVER --traceabstraction.positions.where.we.compute.the.hoare.annotation All --traceabstraction.encode.modifies.clause.in.ensures.clause.of.contracts true --witnessprinter.yaml.format.version 2.1 --witnessprinter.generate.graphml.witnesses false --- Real Ultimate output --- This is Ultimate 0.2.4-tmp.dk.referee-eval-fb1cb0b-m [2024-09-25 11:36:22,849 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-09-25 11:36:22,926 INFO L114 SettingsManager]: Loading settings from /storage/repos/certificate-witnesses-artifact/automizer/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-09-25 11:36:22,931 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-09-25 11:36:22,932 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-09-25 11:36:22,962 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-09-25 11:36:22,962 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-09-25 11:36:22,963 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-09-25 11:36:22,963 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-09-25 11:36:22,964 INFO L153 SettingsManager]: * Use memory slicer=true [2024-09-25 11:36:22,964 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-09-25 11:36:22,964 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-09-25 11:36:22,965 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-09-25 11:36:22,965 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-09-25 11:36:22,969 INFO L153 SettingsManager]: * Use SBE=true [2024-09-25 11:36:22,969 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-09-25 11:36:22,970 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-09-25 11:36:22,970 INFO L153 SettingsManager]: * sizeof long=4 [2024-09-25 11:36:22,970 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-09-25 11:36:22,970 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-09-25 11:36:22,971 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-09-25 11:36:22,971 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-09-25 11:36:22,971 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-09-25 11:36:22,975 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-09-25 11:36:22,975 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-09-25 11:36:22,975 INFO L153 SettingsManager]: * sizeof long double=12 [2024-09-25 11:36:22,975 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-09-25 11:36:22,976 INFO L153 SettingsManager]: * Use constant arrays=true [2024-09-25 11:36:22,976 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-09-25 11:36:22,976 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-09-25 11:36:22,976 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-09-25 11:36:22,976 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-09-25 11:36:22,977 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-25 11:36:22,977 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-09-25 11:36:22,977 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-09-25 11:36:22,977 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-09-25 11:36:22,978 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-09-25 11:36:22,978 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-09-25 11:36:22,978 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-09-25 11:36:22,978 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-09-25 11:36:22,979 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-09-25 11:36:22,979 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-09-25 11:36:22,980 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 -> dfbeed813c4c61f00fa3f37e016718a299be7911d54e721c8910a31480a25397 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.plugins.generator.traceabstraction: Encode 'modifies' clause in 'ensures' clause of contracts -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: YAML Format version -> 2.1 Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Generate GraphML witnesses -> false [2024-09-25 11:36:23,316 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-09-25 11:36:23,342 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-09-25 11:36:23,345 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-09-25 11:36:23,346 INFO L270 PluginConnector]: Initializing CDTParser... [2024-09-25 11:36:23,347 INFO L274 PluginConnector]: CDTParser initialized [2024-09-25 11:36:23,348 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/certificate-witnesses-artifact/automizer/../sv-benchmarks/c/recursified_nla-digbench/recursified_hard-ll.c [2024-09-25 11:36:24,795 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-09-25 11:36:25,013 INFO L384 CDTParser]: Found 1 translation units. [2024-09-25 11:36:25,016 INFO L180 CDTParser]: Scanning /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursified_nla-digbench/recursified_hard-ll.c [2024-09-25 11:36:25,026 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/certificate-witnesses-artifact/automizer/data/9a979ff5e/cf4e7e26478f42f787800d2246e2835a/FLAG4f46f9a8d [2024-09-25 11:36:25,380 INFO L435 CDTParser]: Successfully deleted /storage/repos/certificate-witnesses-artifact/automizer/data/9a979ff5e/cf4e7e26478f42f787800d2246e2835a [2024-09-25 11:36:25,382 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-09-25 11:36:25,383 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-09-25 11:36:25,384 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-09-25 11:36:25,385 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-09-25 11:36:25,389 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-09-25 11:36:25,389 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,390 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4cfa22cf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25, skipping insertion in model container [2024-09-25 11:36:25,390 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,407 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-09-25 11:36:25,546 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_hard-ll.c[1083,1096] [2024-09-25 11:36:25,570 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-25 11:36:25,581 INFO L200 MainTranslator]: Completed pre-run [2024-09-25 11:36:25,591 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_hard-ll.c[1083,1096] [2024-09-25 11:36:25,607 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-25 11:36:25,623 INFO L204 MainTranslator]: Completed translation [2024-09-25 11:36:25,624 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25 WrapperNode [2024-09-25 11:36:25,624 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-09-25 11:36:25,625 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-09-25 11:36:25,625 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-09-25 11:36:25,625 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-09-25 11:36:25,631 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,637 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,643 INFO L138 Inliner]: procedures = 17, calls = 84, calls flagged for inlining = 0, calls inlined = 0, statements flattened = 0 [2024-09-25 11:36:25,644 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-09-25 11:36:25,644 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-09-25 11:36:25,645 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-09-25 11:36:25,645 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-09-25 11:36:25,659 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,659 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,663 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,680 INFO L175 MemorySlicer]: Split 49 memory accesses to 7 slices as follows [6, 2, 5, 9, 8, 7, 12]. 24 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [0, 2, 0, 0, 0, 0, 0]. The 12 writes are split as follows [2, 0, 1, 3, 2, 1, 3]. [2024-09-25 11:36:25,681 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,681 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,693 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,697 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,702 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,703 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,708 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-09-25 11:36:25,709 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-09-25 11:36:25,709 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-09-25 11:36:25,709 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-09-25 11:36:25,710 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (1/1) ... [2024-09-25 11:36:25,715 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-25 11:36:25,725 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:36:25,741 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-25 11:36:25,744 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-25 11:36:25,797 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-09-25 11:36:25,797 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-09-25 11:36:25,797 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-09-25 11:36:25,797 INFO L130 BoogieDeclarations]: Found specification of procedure main [2024-09-25 11:36:25,797 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2024-09-25 11:36:25,798 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-09-25 11:36:25,798 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_41_to_51_0 [2024-09-25 11:36:25,800 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_41_to_51_0 [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-09-25 11:36:25,800 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_31_to_38_0 [2024-09-25 11:36:25,801 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_31_to_38_0 [2024-09-25 11:36:25,801 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-09-25 11:36:25,801 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-09-25 11:36:25,801 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-09-25 11:36:25,801 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-09-25 11:36:25,801 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-09-25 11:36:25,802 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-09-25 11:36:25,802 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2024-09-25 11:36:25,803 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2024-09-25 11:36:25,803 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2024-09-25 11:36:25,803 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-09-25 11:36:25,803 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-09-25 11:36:25,804 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-09-25 11:36:25,804 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-09-25 11:36:25,804 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-09-25 11:36:25,804 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-09-25 11:36:25,804 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-09-25 11:36:25,804 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-09-25 11:36:25,805 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2024-09-25 11:36:25,806 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-09-25 11:36:25,806 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-09-25 11:36:25,806 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-09-25 11:36:25,933 INFO L241 CfgBuilder]: Building ICFG [2024-09-25 11:36:25,934 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2024-09-25 11:36:26,249 INFO L? ?]: Removed 9 outVars from TransFormulas that were not future-live. [2024-09-25 11:36:26,249 INFO L290 CfgBuilder]: Performing block encoding [2024-09-25 11:36:26,271 INFO L312 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-09-25 11:36:26,271 INFO L317 CfgBuilder]: Removed 2 assume(true) statements. [2024-09-25 11:36:26,271 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.09 11:36:26 BoogieIcfgContainer [2024-09-25 11:36:26,271 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-09-25 11:36:26,275 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-09-25 11:36:26,276 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-09-25 11:36:26,278 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-09-25 11:36:26,279 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 25.09 11:36:25" (1/3) ... [2024-09-25 11:36:26,279 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4415afe1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.09 11:36:26, skipping insertion in model container [2024-09-25 11:36:26,279 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 25.09 11:36:25" (2/3) ... [2024-09-25 11:36:26,280 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4415afe1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.09 11:36:26, skipping insertion in model container [2024-09-25 11:36:26,281 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.09 11:36:26" (3/3) ... [2024-09-25 11:36:26,282 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_hard-ll.c [2024-09-25 11:36:26,297 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:All NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-09-25 11:36:26,298 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-09-25 11:36:26,357 INFO L335 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-09-25 11:36:26,365 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;@abc25d0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-09-25 11:36:26,365 INFO L337 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-09-25 11:36:26,369 INFO L276 IsEmpty]: Start isEmpty. Operand has 50 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 31 states have internal predecessors, (36), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2024-09-25 11:36:26,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-09-25 11:36:26,376 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:36:26,376 INFO L216 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:36:26,377 INFO L399 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:36:26,381 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:26,383 INFO L85 PathProgramCache]: Analyzing trace with hash -261209268, now seen corresponding path program 1 times [2024-09-25 11:36:26,391 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:36:26,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1382637087] [2024-09-25 11:36:26,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:26,392 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:36:26,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:27,110 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-25 11:36:27,113 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:27,125 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-25 11:36:27,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:27,137 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-25 11:36:27,138 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:36:27,138 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1382637087] [2024-09-25 11:36:27,139 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1382637087] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-25 11:36:27,142 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-25 11:36:27,142 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-09-25 11:36:27,144 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1663464075] [2024-09-25 11:36:27,146 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-25 11:36:27,153 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-25 11:36:27,153 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:36:27,177 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-25 11:36:27,178 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-09-25 11:36:27,181 INFO L87 Difference]: Start difference. First operand has 50 states, 28 states have (on average 1.2857142857142858) internal successors, (36), 31 states have internal predecessors, (36), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-09-25 11:36:27,416 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:36:27,418 INFO L93 Difference]: Finished difference Result 96 states and 134 transitions. [2024-09-25 11:36:27,420 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-09-25 11:36:27,421 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-09-25 11:36:27,425 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:36:27,439 INFO L225 Difference]: With dead ends: 96 [2024-09-25 11:36:27,439 INFO L226 Difference]: Without dead ends: 50 [2024-09-25 11:36:27,446 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 6 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-25 11:36:27,453 INFO L434 NwaCegarLoop]: 51 mSDtfsCounter, 18 mSDsluCounter, 245 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 296 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-25 11:36:27,454 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 296 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-25 11:36:27,470 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2024-09-25 11:36:27,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 50. [2024-09-25 11:36:27,500 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 29 states have (on average 1.1379310344827587) internal successors, (33), 32 states have internal predecessors, (33), 14 states have call successors, (14), 7 states have call predecessors, (14), 6 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-09-25 11:36:27,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 59 transitions. [2024-09-25 11:36:27,506 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 59 transitions. Word has length 18 [2024-09-25 11:36:27,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:36:27,507 INFO L474 AbstractCegarLoop]: Abstraction has 50 states and 59 transitions. [2024-09-25 11:36:27,507 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 6 states have internal predecessors, (11), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-09-25 11:36:27,508 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:27,508 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 59 transitions. [2024-09-25 11:36:27,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-09-25 11:36:27,526 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:36:27,527 INFO L216 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:36:27,527 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-09-25 11:36:27,527 INFO L399 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:36:27,528 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:27,528 INFO L85 PathProgramCache]: Analyzing trace with hash 249081250, now seen corresponding path program 1 times [2024-09-25 11:36:27,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:36:27,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1350493110] [2024-09-25 11:36:27,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:27,528 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:36:27,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:28,069 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-25 11:36:28,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:28,074 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-25 11:36:28,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:28,076 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-25 11:36:28,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:28,082 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-25 11:36:28,082 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:36:28,083 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1350493110] [2024-09-25 11:36:28,083 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1350493110] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-25 11:36:28,084 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-25 11:36:28,084 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-09-25 11:36:28,084 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [598499715] [2024-09-25 11:36:28,084 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-25 11:36:28,086 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-25 11:36:28,086 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:36:28,087 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-25 11:36:28,088 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-09-25 11:36:28,088 INFO L87 Difference]: Start difference. First operand 50 states and 59 transitions. Second operand has 8 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 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-25 11:36:28,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:36:28,266 INFO L93 Difference]: Finished difference Result 56 states and 64 transitions. [2024-09-25 11:36:28,266 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-09-25 11:36:28,267 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 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-25 11:36:28,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:36:28,268 INFO L225 Difference]: With dead ends: 56 [2024-09-25 11:36:28,268 INFO L226 Difference]: Without dead ends: 54 [2024-09-25 11:36:28,269 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 8 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-25 11:36:28,270 INFO L434 NwaCegarLoop]: 50 mSDtfsCounter, 17 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 99 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 279 SdHoareTripleChecker+Invalid, 108 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 99 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-25 11:36:28,270 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 279 Invalid, 108 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 99 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-25 11:36:28,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-09-25 11:36:28,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-09-25 11:36:28,280 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 32 states have (on average 1.125) internal successors, (36), 35 states have internal predecessors, (36), 14 states have call successors, (14), 8 states have call predecessors, (14), 7 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-09-25 11:36:28,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 62 transitions. [2024-09-25 11:36:28,282 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 62 transitions. Word has length 24 [2024-09-25 11:36:28,282 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:36:28,283 INFO L474 AbstractCegarLoop]: Abstraction has 54 states and 62 transitions. [2024-09-25 11:36:28,283 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.5) internal successors, (15), 6 states have internal predecessors, (15), 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-25 11:36:28,283 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:28,283 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 62 transitions. [2024-09-25 11:36:28,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-09-25 11:36:28,284 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:36:28,284 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, 1, 1, 1, 1, 1, 1] [2024-09-25 11:36:28,284 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-09-25 11:36:28,285 INFO L399 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:36:28,285 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:28,285 INFO L85 PathProgramCache]: Analyzing trace with hash 1395279990, now seen corresponding path program 1 times [2024-09-25 11:36:28,285 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:36:28,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [503268250] [2024-09-25 11:36:28,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:28,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:36:28,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:36:28,316 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [188557415] [2024-09-25 11:36:28,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:28,317 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:36:28,317 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:36:28,320 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-25 11:36:28,322 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-25 11:36:28,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:28,504 INFO L262 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-09-25 11:36:28,514 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:36:28,546 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-25 11:36:28,554 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 17 treesize of output 13 [2024-09-25 11:36:28,562 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-25 11:36:28,912 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-09-25 11:36:28,917 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2024-09-25 11:36:28,967 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-25 11:36:28,969 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:36:29,151 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-25 11:36:29,151 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:36:29,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [503268250] [2024-09-25 11:36:29,152 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:36:29,152 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [188557415] [2024-09-25 11:36:29,153 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [188557415] provided 1 perfect and 1 imperfect interpolant sequences [2024-09-25 11:36:29,153 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:36:29,153 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2024-09-25 11:36:29,153 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [278467654] [2024-09-25 11:36:29,153 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-25 11:36:29,154 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-25 11:36:29,154 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:36:29,154 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-25 11:36:29,155 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-09-25 11:36:29,155 INFO L87 Difference]: Start difference. First operand 54 states and 62 transitions. Second operand has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-09-25 11:36:29,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:36:29,433 INFO L93 Difference]: Finished difference Result 65 states and 75 transitions. [2024-09-25 11:36:29,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-09-25 11:36:29,435 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2024-09-25 11:36:29,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:36:29,438 INFO L225 Difference]: With dead ends: 65 [2024-09-25 11:36:29,439 INFO L226 Difference]: Without dead ends: 63 [2024-09-25 11:36:29,440 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 43 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-25 11:36:29,441 INFO L434 NwaCegarLoop]: 49 mSDtfsCounter, 15 mSDsluCounter, 222 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 15 SdHoareTripleChecker+Valid, 271 SdHoareTripleChecker+Invalid, 122 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-25 11:36:29,442 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [15 Valid, 271 Invalid, 122 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-25 11:36:29,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-09-25 11:36:29,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 58. [2024-09-25 11:36:29,469 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 35 states have (on average 1.1142857142857143) internal successors, (39), 38 states have internal predecessors, (39), 14 states have call successors, (14), 9 states have call predecessors, (14), 8 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-09-25 11:36:29,470 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 65 transitions. [2024-09-25 11:36:29,471 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 65 transitions. Word has length 30 [2024-09-25 11:36:29,471 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:36:29,471 INFO L474 AbstractCegarLoop]: Abstraction has 58 states and 65 transitions. [2024-09-25 11:36:29,472 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 4 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-09-25 11:36:29,472 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:29,472 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 65 transitions. [2024-09-25 11:36:29,473 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-09-25 11:36:29,473 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:36:29,474 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:36:29,483 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-09-25 11:36:29,678 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:36:29,679 INFO L399 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:36:29,679 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:29,679 INFO L85 PathProgramCache]: Analyzing trace with hash -127824258, now seen corresponding path program 1 times [2024-09-25 11:36:29,680 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:36:29,680 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1944625703] [2024-09-25 11:36:29,680 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:29,680 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:36:29,718 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:36:29,719 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [412261342] [2024-09-25 11:36:29,719 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:29,719 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:36:29,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:36:29,721 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-25 11:36:29,725 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-25 11:36:29,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:29,852 INFO L262 TraceCheckSpWp]: Trace formula consists of 310 conjuncts, 89 conjuncts are in the unsatisfiable core [2024-09-25 11:36:29,857 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:36:29,866 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-25 11:36:29,876 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-25 11:36:29,883 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 17 treesize of output 13 [2024-09-25 11:36:29,893 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2024-09-25 11:36:29,903 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-25 11:36:30,660 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 28 treesize of output 16 [2024-09-25 11:36:30,849 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:36:30,851 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 34 treesize of output 34 [2024-09-25 11:36:30,882 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:36:30,882 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 33 treesize of output 29 [2024-09-25 11:36:30,975 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 3 proven. 9 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-09-25 11:36:30,975 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:36:31,670 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:36:31,670 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1944625703] [2024-09-25 11:36:31,670 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:36:31,670 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [412261342] [2024-09-25 11:36:31,670 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [412261342] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:36:31,670 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:36:31,670 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2024-09-25 11:36:31,671 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1040095043] [2024-09-25 11:36:31,671 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:36:31,673 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-09-25 11:36:31,674 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:36:31,674 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-09-25 11:36:31,675 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=435, Unknown=0, NotChecked=0, Total=506 [2024-09-25 11:36:31,675 INFO L87 Difference]: Start difference. First operand 58 states and 65 transitions. Second operand has 18 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 14 states have internal predecessors, (24), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2024-09-25 11:36:33,225 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:36:33,226 INFO L93 Difference]: Finished difference Result 104 states and 128 transitions. [2024-09-25 11:36:33,226 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-09-25 11:36:33,226 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 14 states have internal predecessors, (24), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) Word has length 42 [2024-09-25 11:36:33,227 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:36:33,229 INFO L225 Difference]: With dead ends: 104 [2024-09-25 11:36:33,229 INFO L226 Difference]: Without dead ends: 102 [2024-09-25 11:36:33,230 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 25 SyntacticMatches, 3 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 241 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=179, Invalid=1153, Unknown=0, NotChecked=0, Total=1332 [2024-09-25 11:36:33,230 INFO L434 NwaCegarLoop]: 30 mSDtfsCounter, 60 mSDsluCounter, 234 mSDsCounter, 0 mSdLazyCounter, 599 mSolverCounterSat, 35 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 634 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 599 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-09-25 11:36:33,231 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 264 Invalid, 634 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 599 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-09-25 11:36:33,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-09-25 11:36:33,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 99. [2024-09-25 11:36:33,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 60 states have (on average 1.15) internal successors, (69), 65 states have internal predecessors, (69), 23 states have call successors, (23), 13 states have call predecessors, (23), 15 states have return successors, (32), 21 states have call predecessors, (32), 20 states have call successors, (32) [2024-09-25 11:36:33,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 124 transitions. [2024-09-25 11:36:33,269 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 124 transitions. Word has length 42 [2024-09-25 11:36:33,270 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:36:33,270 INFO L474 AbstractCegarLoop]: Abstraction has 99 states and 124 transitions. [2024-09-25 11:36:33,270 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 14 states have (on average 1.7142857142857142) internal successors, (24), 14 states have internal predecessors, (24), 7 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2024-09-25 11:36:33,270 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:33,270 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 124 transitions. [2024-09-25 11:36:33,271 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-09-25 11:36:33,271 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:36:33,272 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:36:33,287 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-25 11:36:33,472 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:36:33,472 INFO L399 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:36:33,473 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:33,473 INFO L85 PathProgramCache]: Analyzing trace with hash -782540599, now seen corresponding path program 1 times [2024-09-25 11:36:33,473 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:36:33,473 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [165630827] [2024-09-25 11:36:33,473 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:33,473 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:36:33,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:36:33,512 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [376885945] [2024-09-25 11:36:33,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:33,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:36:33,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:36:33,514 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-25 11:36:33,516 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-25 11:36:33,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:33,651 INFO L262 TraceCheckSpWp]: Trace formula consists of 325 conjuncts, 65 conjuncts are in the unsatisfiable core [2024-09-25 11:36:33,654 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:36:33,658 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-25 11:36:33,662 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-25 11:36:33,666 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 17 treesize of output 13 [2024-09-25 11:36:33,679 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 13 treesize of output 9 [2024-09-25 11:36:33,891 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-09-25 11:36:33,894 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2024-09-25 11:36:33,932 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-25 11:36:33,932 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:36:34,292 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:36:34,292 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [165630827] [2024-09-25 11:36:34,292 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:36:34,293 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [376885945] [2024-09-25 11:36:34,293 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [376885945] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:36:34,293 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:36:34,293 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2024-09-25 11:36:34,293 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [671945457] [2024-09-25 11:36:34,293 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:36:34,294 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-09-25 11:36:34,294 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:36:34,295 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-09-25 11:36:34,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=201, Unknown=0, NotChecked=0, Total=240 [2024-09-25 11:36:34,295 INFO L87 Difference]: Start difference. First operand 99 states and 124 transitions. Second operand has 11 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (10), 5 states have call predecessors, (10), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-09-25 11:36:34,912 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:36:34,912 INFO L93 Difference]: Finished difference Result 153 states and 178 transitions. [2024-09-25 11:36:34,913 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-09-25 11:36:34,913 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (10), 5 states have call predecessors, (10), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 48 [2024-09-25 11:36:34,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:36:34,915 INFO L225 Difference]: With dead ends: 153 [2024-09-25 11:36:34,915 INFO L226 Difference]: Without dead ends: 151 [2024-09-25 11:36:34,916 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 51 SyntacticMatches, 3 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-09-25 11:36:34,916 INFO L434 NwaCegarLoop]: 26 mSDtfsCounter, 65 mSDsluCounter, 107 mSDsCounter, 0 mSdLazyCounter, 306 mSolverCounterSat, 41 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 70 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 349 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 306 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-09-25 11:36:34,917 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [70 Valid, 133 Invalid, 349 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 306 Invalid, 2 Unknown, 0 Unchecked, 0.4s Time] [2024-09-25 11:36:34,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2024-09-25 11:36:34,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 149. [2024-09-25 11:36:34,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 94 states have (on average 1.127659574468085) internal successors, (106), 99 states have internal predecessors, (106), 30 states have call successors, (30), 21 states have call predecessors, (30), 24 states have return successors, (39), 28 states have call predecessors, (39), 26 states have call successors, (39) [2024-09-25 11:36:34,964 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 175 transitions. [2024-09-25 11:36:34,965 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 175 transitions. Word has length 48 [2024-09-25 11:36:34,965 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:36:34,965 INFO L474 AbstractCegarLoop]: Abstraction has 149 states and 175 transitions. [2024-09-25 11:36:34,965 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (10), 5 states have call predecessors, (10), 3 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2024-09-25 11:36:34,966 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:34,966 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 175 transitions. [2024-09-25 11:36:34,967 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2024-09-25 11:36:34,967 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:36:34,967 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:36:34,984 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-09-25 11:36:35,171 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:36:35,172 INFO L399 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:36:35,172 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:36:35,172 INFO L85 PathProgramCache]: Analyzing trace with hash -1885035655, now seen corresponding path program 1 times [2024-09-25 11:36:35,172 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:36:35,172 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1813610664] [2024-09-25 11:36:35,173 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:35,173 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:36:35,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:36:35,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [564718195] [2024-09-25 11:36:35,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:36:35,217 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:36:35,217 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:36:35,219 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-25 11:36:35,221 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-25 11:36:35,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:36:35,356 INFO L262 TraceCheckSpWp]: Trace formula consists of 348 conjuncts, 61 conjuncts are in the unsatisfiable core [2024-09-25 11:36:35,361 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:36:35,365 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-25 11:36:35,383 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-25 11:36:35,387 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 17 treesize of output 13 [2024-09-25 11:36:35,396 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2024-09-25 11:36:35,414 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-25 11:36:35,840 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:36:35,840 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 40 treesize of output 40 [2024-09-25 11:36:35,849 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-25 11:36:36,095 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:36:36,096 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 47 treesize of output 43 [2024-09-25 11:36:36,106 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:36:36,107 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 35 treesize of output 35 [2024-09-25 11:36:36,122 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 24 treesize of output 12 [2024-09-25 11:36:36,189 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 34 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-09-25 11:36:36,190 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:36:48,585 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:36:48,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1813610664] [2024-09-25 11:36:48,585 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:36:48,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [564718195] [2024-09-25 11:36:48,585 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [564718195] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:36:48,585 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:36:48,586 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2024-09-25 11:36:48,586 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [640973184] [2024-09-25 11:36:48,586 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:36:48,587 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-09-25 11:36:48,587 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:36:48,587 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-09-25 11:36:48,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=220, Unknown=4, NotChecked=0, Total=272 [2024-09-25 11:36:48,588 INFO L87 Difference]: Start difference. First operand 149 states and 175 transitions. Second operand has 15 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2024-09-25 11:36:52,631 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-09-25 11:36:56,671 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-09-25 11:37:00,929 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-09-25 11:37:09,590 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-09-25 11:37:13,599 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-09-25 11:37:13,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:37:13,659 INFO L93 Difference]: Finished difference Result 192 states and 219 transitions. [2024-09-25 11:37:13,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-09-25 11:37:13,660 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) Word has length 58 [2024-09-25 11:37:13,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:37:13,662 INFO L225 Difference]: With dead ends: 192 [2024-09-25 11:37:13,662 INFO L226 Difference]: Without dead ends: 188 [2024-09-25 11:37:13,663 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 71 GetRequests, 45 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 16.8s TimeCoverageRelationStatistics Valid=108, Invalid=487, Unknown=5, NotChecked=0, Total=600 [2024-09-25 11:37:13,664 INFO L434 NwaCegarLoop]: 30 mSDtfsCounter, 78 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 441 mSolverCounterSat, 43 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 20.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 86 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 491 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 441 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.7s IncrementalHoareTripleChecker+Time [2024-09-25 11:37:13,664 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [86 Valid, 183 Invalid, 491 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 441 Invalid, 7 Unknown, 0 Unchecked, 20.7s Time] [2024-09-25 11:37:13,665 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2024-09-25 11:37:13,730 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 178. [2024-09-25 11:37:13,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 178 states, 113 states have (on average 1.1327433628318584) internal successors, (128), 118 states have internal predecessors, (128), 37 states have call successors, (37), 25 states have call predecessors, (37), 27 states have return successors, (41), 35 states have call predecessors, (41), 31 states have call successors, (41) [2024-09-25 11:37:13,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 178 states to 178 states and 206 transitions. [2024-09-25 11:37:13,733 INFO L78 Accepts]: Start accepts. Automaton has 178 states and 206 transitions. Word has length 58 [2024-09-25 11:37:13,733 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:37:13,733 INFO L474 AbstractCegarLoop]: Abstraction has 178 states and 206 transitions. [2024-09-25 11:37:13,733 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 2.230769230769231) internal successors, (29), 12 states have internal predecessors, (29), 6 states have call successors, (11), 6 states have call predecessors, (11), 5 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2024-09-25 11:37:13,734 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:13,734 INFO L276 IsEmpty]: Start isEmpty. Operand 178 states and 206 transitions. [2024-09-25 11:37:13,735 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2024-09-25 11:37:13,735 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:37:13,735 INFO L216 NwaCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:37:13,752 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-09-25 11:37:13,935 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-25 11:37:13,936 INFO L399 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:37:13,936 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:13,936 INFO L85 PathProgramCache]: Analyzing trace with hash -1428903809, now seen corresponding path program 1 times [2024-09-25 11:37:13,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:37:13,936 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [833943562] [2024-09-25 11:37:13,936 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:13,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:37:13,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,240 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-25 11:37:14,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,243 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-25 11:37:14,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,258 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-25 11:37:14,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,306 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-25 11:37:14,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,313 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-25 11:37:14,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,318 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-25 11:37:14,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,322 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 38 [2024-09-25 11:37:14,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,326 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2024-09-25 11:37:14,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:14,331 INFO L134 CoverageAnalysis]: Checked inductivity of 53 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-09-25 11:37:14,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:37:14,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [833943562] [2024-09-25 11:37:14,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [833943562] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-25 11:37:14,333 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-25 11:37:14,333 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-09-25 11:37:14,333 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1496914204] [2024-09-25 11:37:14,334 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-25 11:37:14,335 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-25 11:37:14,335 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:37:14,335 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-25 11:37:14,336 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-09-25 11:37:14,336 INFO L87 Difference]: Start difference. First operand 178 states and 206 transitions. Second operand has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 5 states have call successors, (12), 4 states have call predecessors, (12), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2024-09-25 11:37:14,641 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:37:14,641 INFO L93 Difference]: Finished difference Result 182 states and 210 transitions. [2024-09-25 11:37:14,642 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-09-25 11:37:14,642 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 5 states have call successors, (12), 4 states have call predecessors, (12), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 59 [2024-09-25 11:37:14,643 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:37:14,644 INFO L225 Difference]: With dead ends: 182 [2024-09-25 11:37:14,644 INFO L226 Difference]: Without dead ends: 134 [2024-09-25 11:37:14,645 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2024-09-25 11:37:14,646 INFO L434 NwaCegarLoop]: 29 mSDtfsCounter, 40 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 222 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-09-25 11:37:14,646 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 110 Invalid, 222 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 199 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-25 11:37:14,651 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 134 states. [2024-09-25 11:37:14,709 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 134 to 132. [2024-09-25 11:37:14,709 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 84 states have (on average 1.0952380952380953) internal successors, (92), 87 states have internal predecessors, (92), 27 states have call successors, (27), 20 states have call predecessors, (27), 20 states have return successors, (28), 25 states have call predecessors, (28), 23 states have call successors, (28) [2024-09-25 11:37:14,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 147 transitions. [2024-09-25 11:37:14,710 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 147 transitions. Word has length 59 [2024-09-25 11:37:14,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:37:14,711 INFO L474 AbstractCegarLoop]: Abstraction has 132 states and 147 transitions. [2024-09-25 11:37:14,711 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 6 states have internal predecessors, (27), 5 states have call successors, (12), 4 states have call predecessors, (12), 2 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2024-09-25 11:37:14,712 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:14,712 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 147 transitions. [2024-09-25 11:37:14,713 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2024-09-25 11:37:14,713 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:37:14,714 INFO L216 NwaCegarLoop]: trace histogram [7, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:37:14,714 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-09-25 11:37:14,715 INFO L399 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:37:14,715 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:14,715 INFO L85 PathProgramCache]: Analyzing trace with hash 2096548347, now seen corresponding path program 1 times [2024-09-25 11:37:14,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:37:14,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [801450303] [2024-09-25 11:37:14,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:14,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:37:14,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,403 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-25 11:37:15,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,407 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-25 11:37:15,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,422 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-25 11:37:15,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,609 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-25 11:37:15,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,626 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-25 11:37:15,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,631 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-25 11:37:15,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,658 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 35 [2024-09-25 11:37:15,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,699 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-25 11:37:15,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,704 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-25 11:37:15,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,708 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 54 [2024-09-25 11:37:15,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:15,714 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2024-09-25 11:37:15,714 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:37:15,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [801450303] [2024-09-25 11:37:15,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [801450303] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-25 11:37:15,714 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-25 11:37:15,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14] imperfect sequences [] total 14 [2024-09-25 11:37:15,715 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1102773353] [2024-09-25 11:37:15,715 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-25 11:37:15,715 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2024-09-25 11:37:15,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:37:15,716 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2024-09-25 11:37:15,717 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2024-09-25 11:37:15,717 INFO L87 Difference]: Start difference. First operand 132 states and 147 transitions. Second operand has 14 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 4 states have call predecessors, (10), 6 states have call successors, (10) [2024-09-25 11:37:16,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:37:16,323 INFO L93 Difference]: Finished difference Result 136 states and 151 transitions. [2024-09-25 11:37:16,324 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-09-25 11:37:16,324 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 4 states have call predecessors, (10), 6 states have call successors, (10) Word has length 64 [2024-09-25 11:37:16,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:37:16,325 INFO L225 Difference]: With dead ends: 136 [2024-09-25 11:37:16,325 INFO L226 Difference]: Without dead ends: 104 [2024-09-25 11:37:16,326 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=77, Invalid=343, Unknown=0, NotChecked=0, Total=420 [2024-09-25 11:37:16,326 INFO L434 NwaCegarLoop]: 19 mSDtfsCounter, 37 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 425 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 464 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 425 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-09-25 11:37:16,327 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 117 Invalid, 464 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 425 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-09-25 11:37:16,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2024-09-25 11:37:16,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 102. [2024-09-25 11:37:16,383 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 64 states have (on average 1.109375) internal successors, (71), 67 states have internal predecessors, (71), 22 states have call successors, (22), 15 states have call predecessors, (22), 15 states have return successors, (23), 20 states have call predecessors, (23), 19 states have call successors, (23) [2024-09-25 11:37:16,384 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 116 transitions. [2024-09-25 11:37:16,385 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 116 transitions. Word has length 64 [2024-09-25 11:37:16,385 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:37:16,385 INFO L474 AbstractCegarLoop]: Abstraction has 102 states and 116 transitions. [2024-09-25 11:37:16,386 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 11 states have internal predecessors, (27), 7 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 4 states have call predecessors, (10), 6 states have call successors, (10) [2024-09-25 11:37:16,386 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:16,386 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 116 transitions. [2024-09-25 11:37:16,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2024-09-25 11:37:16,387 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:37:16,387 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:37:16,387 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-09-25 11:37:16,387 INFO L399 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:37:16,389 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:16,389 INFO L85 PathProgramCache]: Analyzing trace with hash 46413415, now seen corresponding path program 1 times [2024-09-25 11:37:16,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:37:16,389 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [660886189] [2024-09-25 11:37:16,389 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:16,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:37:16,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:37:16,436 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [137817682] [2024-09-25 11:37:16,436 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:16,436 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:37:16,436 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:37:16,438 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-25 11:37:16,439 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-25 11:37:16,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:16,598 INFO L262 TraceCheckSpWp]: Trace formula consists of 416 conjuncts, 60 conjuncts are in the unsatisfiable core [2024-09-25 11:37:16,606 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:37:16,612 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-25 11:37:16,616 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-25 11:37:16,621 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 17 treesize of output 13 [2024-09-25 11:37:17,009 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-09-25 11:37:17,012 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 9 [2024-09-25 11:37:17,050 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 71 trivial. 0 not checked. [2024-09-25 11:37:17,050 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:37:17,238 INFO L134 CoverageAnalysis]: Checked inductivity of 83 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 71 trivial. 0 not checked. [2024-09-25 11:37:17,238 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:37:17,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [660886189] [2024-09-25 11:37:17,238 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:37:17,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [137817682] [2024-09-25 11:37:17,239 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [137817682] provided 1 perfect and 1 imperfect interpolant sequences [2024-09-25 11:37:17,239 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:37:17,239 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 11 [2024-09-25 11:37:17,239 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [520678066] [2024-09-25 11:37:17,239 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-25 11:37:17,240 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-25 11:37:17,240 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:37:17,240 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-25 11:37:17,240 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2024-09-25 11:37:17,240 INFO L87 Difference]: Start difference. First operand 102 states and 116 transitions. Second operand has 8 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 3 states have call successors, (10), 3 states have call predecessors, (10), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-09-25 11:37:17,506 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:37:17,507 INFO L93 Difference]: Finished difference Result 113 states and 128 transitions. [2024-09-25 11:37:17,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-09-25 11:37:17,507 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 3 states have call successors, (10), 3 states have call predecessors, (10), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 66 [2024-09-25 11:37:17,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:37:17,509 INFO L225 Difference]: With dead ends: 113 [2024-09-25 11:37:17,509 INFO L226 Difference]: Without dead ends: 111 [2024-09-25 11:37:17,509 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 120 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2024-09-25 11:37:17,510 INFO L434 NwaCegarLoop]: 50 mSDtfsCounter, 19 mSDsluCounter, 253 mSDsCounter, 0 mSdLazyCounter, 118 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 303 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-25 11:37:17,510 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 303 Invalid, 126 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 118 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-09-25 11:37:17,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2024-09-25 11:37:17,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 106. [2024-09-25 11:37:17,547 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 67 states have (on average 1.1044776119402986) internal successors, (74), 70 states have internal predecessors, (74), 22 states have call successors, (22), 16 states have call predecessors, (22), 16 states have return successors, (23), 20 states have call predecessors, (23), 19 states have call successors, (23) [2024-09-25 11:37:17,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 119 transitions. [2024-09-25 11:37:17,549 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 119 transitions. Word has length 66 [2024-09-25 11:37:17,549 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:37:17,549 INFO L474 AbstractCegarLoop]: Abstraction has 106 states and 119 transitions. [2024-09-25 11:37:17,549 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 3.6666666666666665) internal successors, (22), 6 states have internal predecessors, (22), 3 states have call successors, (10), 3 states have call predecessors, (10), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-09-25 11:37:17,549 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:17,550 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 119 transitions. [2024-09-25 11:37:17,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-09-25 11:37:17,550 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:37:17,551 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:37:17,568 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-09-25 11:37:17,754 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,6 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:37:17,755 INFO L399 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:37:17,755 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:17,756 INFO L85 PathProgramCache]: Analyzing trace with hash 1617999346, now seen corresponding path program 1 times [2024-09-25 11:37:17,756 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:37:17,756 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [244246665] [2024-09-25 11:37:17,756 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:17,756 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:37:17,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:37:17,843 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [772237456] [2024-09-25 11:37:17,843 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:17,843 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:37:17,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:37:17,846 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-25 11:37:17,848 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-25 11:37:18,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:18,016 INFO L262 TraceCheckSpWp]: Trace formula consists of 431 conjuncts, 114 conjuncts are in the unsatisfiable core [2024-09-25 11:37:18,020 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:37:18,025 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-25 11:37:18,169 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 8 treesize of output 1 [2024-09-25 11:37:18,177 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-09-25 11:37:22,547 WARN L876 $PredicateComparison]: unable to prove that (exists ((v_func_to_recursive_line_41_to_51_0_~B.offset_BEFORE_CALL_3 Int) (v_func_to_recursive_line_41_to_51_0_~p.base_BEFORE_CALL_3 Int) (v_func_to_recursive_line_41_to_51_0_~d.offset_BEFORE_CALL_3 Int) (v_func_to_recursive_line_41_to_51_0_~p.offset_BEFORE_CALL_3 Int) (v_func_to_recursive_line_41_to_51_0_~B.base_BEFORE_CALL_3 Int) (v_func_to_recursive_line_41_to_51_0_~d.base_BEFORE_CALL_3 Int)) (= (select (select |c_#memory_int#6| v_func_to_recursive_line_41_to_51_0_~d.base_BEFORE_CALL_3) v_func_to_recursive_line_41_to_51_0_~d.offset_BEFORE_CALL_3) (* (mod (select (select |c_#memory_int#5| v_func_to_recursive_line_41_to_51_0_~B.base_BEFORE_CALL_3) v_func_to_recursive_line_41_to_51_0_~B.offset_BEFORE_CALL_3) 4294967296) (select (select |c_#memory_int#3| v_func_to_recursive_line_41_to_51_0_~p.base_BEFORE_CALL_3) v_func_to_recursive_line_41_to_51_0_~p.offset_BEFORE_CALL_3)))) is different from true [2024-09-25 11:37:22,628 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2024-09-25 11:37:22,633 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-25 11:37:22,636 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-25 11:37:22,697 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 53 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 5 not checked. [2024-09-25 11:37:22,697 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:37:47,929 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:37:47,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [244246665] [2024-09-25 11:37:47,929 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:37:47,929 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [772237456] [2024-09-25 11:37:47,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [772237456] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:37:47,929 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:37:47,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2024-09-25 11:37:47,930 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2084330111] [2024-09-25 11:37:47,930 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:37:47,930 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-09-25 11:37:47,931 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:37:47,931 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-09-25 11:37:47,931 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=288, Unknown=5, NotChecked=34, Total=380 [2024-09-25 11:37:47,932 INFO L87 Difference]: Start difference. First operand 106 states and 119 transitions. Second operand has 17 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (11), 7 states have call predecessors, (11), 5 states have call successors, (11) [2024-09-25 11:37:53,040 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:37:53,040 INFO L93 Difference]: Finished difference Result 130 states and 145 transitions. [2024-09-25 11:37:53,041 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-09-25 11:37:53,041 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (11), 7 states have call predecessors, (11), 5 states have call successors, (11) Word has length 72 [2024-09-25 11:37:53,041 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:37:53,042 INFO L225 Difference]: With dead ends: 130 [2024-09-25 11:37:53,043 INFO L226 Difference]: Without dead ends: 128 [2024-09-25 11:37:53,043 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 73 SyntacticMatches, 3 SemanticMatches, 32 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 33.1s TimeCoverageRelationStatistics Valid=150, Invalid=904, Unknown=6, NotChecked=62, Total=1122 [2024-09-25 11:37:53,044 INFO L434 NwaCegarLoop]: 25 mSDtfsCounter, 52 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 491 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 609 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 491 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 78 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-09-25 11:37:53,044 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 172 Invalid, 609 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 491 Invalid, 0 Unknown, 78 Unchecked, 0.6s Time] [2024-09-25 11:37:53,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-09-25 11:37:53,080 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 125. [2024-09-25 11:37:53,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 125 states, 80 states have (on average 1.1) internal successors, (88), 83 states have internal predecessors, (88), 24 states have call successors, (24), 19 states have call predecessors, (24), 20 states have return successors, (27), 22 states have call predecessors, (27), 21 states have call successors, (27) [2024-09-25 11:37:53,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 139 transitions. [2024-09-25 11:37:53,082 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 139 transitions. Word has length 72 [2024-09-25 11:37:53,082 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:37:53,083 INFO L474 AbstractCegarLoop]: Abstraction has 125 states and 139 transitions. [2024-09-25 11:37:53,083 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 14 states have (on average 2.5) internal successors, (35), 13 states have internal predecessors, (35), 7 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (11), 7 states have call predecessors, (11), 5 states have call successors, (11) [2024-09-25 11:37:53,083 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:53,083 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 139 transitions. [2024-09-25 11:37:53,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2024-09-25 11:37:53,084 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:37:53,085 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:37:53,105 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-25 11:37:53,285 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-09-25 11:37:53,286 INFO L399 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:37:53,286 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:53,286 INFO L85 PathProgramCache]: Analyzing trace with hash -797681310, now seen corresponding path program 1 times [2024-09-25 11:37:53,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:37:53,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863853067] [2024-09-25 11:37:53,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:53,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:37:53,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,509 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-25 11:37:53,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,511 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-25 11:37:53,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,520 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-25 11:37:53,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,667 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-25 11:37:53,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,670 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-25 11:37:53,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,674 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-25 11:37:53,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,678 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-09-25 11:37:53,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,712 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-25 11:37:53,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,715 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-25 11:37:53,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,718 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-09-25 11:37:53,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,736 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 59 [2024-09-25 11:37:53,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,814 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-25 11:37:53,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,821 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-09-25 11:37:53,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,829 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-09-25 11:37:53,830 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:37:53,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863853067] [2024-09-25 11:37:53,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [863853067] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:37:53,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1610867271] [2024-09-25 11:37:53,830 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:53,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:37:53,831 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:37:53,832 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-25 11:37:53,833 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-25 11:37:53,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:53,978 INFO L262 TraceCheckSpWp]: Trace formula consists of 454 conjuncts, 38 conjuncts are in the unsatisfiable core [2024-09-25 11:37:53,981 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:37:53,985 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-25 11:37:54,135 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-25 11:37:54,248 INFO L134 CoverageAnalysis]: Checked inductivity of 139 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-09-25 11:37:54,249 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:37:54,580 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1610867271] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:37:54,580 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-25 11:37:54,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 19 [2024-09-25 11:37:54,581 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1635318593] [2024-09-25 11:37:54,581 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-25 11:37:54,581 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-09-25 11:37:54,581 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:37:54,582 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-09-25 11:37:54,582 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=418, Unknown=0, NotChecked=0, Total=506 [2024-09-25 11:37:54,582 INFO L87 Difference]: Start difference. First operand 125 states and 139 transitions. Second operand has 19 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 15 states have internal predecessors, (46), 11 states have call successors, (21), 5 states have call predecessors, (21), 6 states have return successors, (19), 10 states have call predecessors, (19), 10 states have call successors, (19) [2024-09-25 11:37:55,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:37:55,243 INFO L93 Difference]: Finished difference Result 138 states and 156 transitions. [2024-09-25 11:37:55,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-09-25 11:37:55,243 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 15 states have internal predecessors, (46), 11 states have call successors, (21), 5 states have call predecessors, (21), 6 states have return successors, (19), 10 states have call predecessors, (19), 10 states have call successors, (19) Word has length 82 [2024-09-25 11:37:55,244 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:37:55,245 INFO L225 Difference]: With dead ends: 138 [2024-09-25 11:37:55,245 INFO L226 Difference]: Without dead ends: 126 [2024-09-25 11:37:55,246 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 125 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 176 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=153, Invalid=659, Unknown=0, NotChecked=0, Total=812 [2024-09-25 11:37:55,246 INFO L434 NwaCegarLoop]: 22 mSDtfsCounter, 68 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 713 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 765 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 713 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-09-25 11:37:55,247 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 141 Invalid, 765 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 713 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-09-25 11:37:55,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-09-25 11:37:55,285 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 123. [2024-09-25 11:37:55,285 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 79 states have (on average 1.0886075949367089) internal successors, (86), 81 states have internal predecessors, (86), 24 states have call successors, (24), 19 states have call predecessors, (24), 19 states have return successors, (26), 22 states have call predecessors, (26), 21 states have call successors, (26) [2024-09-25 11:37:55,286 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 136 transitions. [2024-09-25 11:37:55,286 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 136 transitions. Word has length 82 [2024-09-25 11:37:55,287 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:37:55,287 INFO L474 AbstractCegarLoop]: Abstraction has 123 states and 136 transitions. [2024-09-25 11:37:55,287 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 14 states have (on average 3.2857142857142856) internal successors, (46), 15 states have internal predecessors, (46), 11 states have call successors, (21), 5 states have call predecessors, (21), 6 states have return successors, (19), 10 states have call predecessors, (19), 10 states have call successors, (19) [2024-09-25 11:37:55,288 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:55,288 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 136 transitions. [2024-09-25 11:37:55,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-09-25 11:37:55,289 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:37:55,289 INFO L216 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:37:55,306 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-09-25 11:37:55,489 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,8 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:37:55,490 INFO L399 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:37:55,490 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:37:55,490 INFO L85 PathProgramCache]: Analyzing trace with hash -2080657482, now seen corresponding path program 1 times [2024-09-25 11:37:55,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:37:55,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1125166413] [2024-09-25 11:37:55,490 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:55,490 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:37:55,561 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:37:55,563 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1593726241] [2024-09-25 11:37:55,564 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:37:55,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:37:55,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:37:55,566 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-25 11:37:55,569 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-25 11:37:55,787 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-25 11:37:55,792 INFO L262 TraceCheckSpWp]: Trace formula consists of 528 conjuncts, 200 conjuncts are in the unsatisfiable core [2024-09-25 11:37:55,798 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:37:55,808 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-25 11:37:55,811 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-25 11:37:55,845 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-25 11:37:55,851 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 17 treesize of output 13 [2024-09-25 11:37:55,861 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-25 11:37:55,870 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 17 treesize of output 13 [2024-09-25 11:37:55,920 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 13 treesize of output 9 [2024-09-25 11:37:56,829 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-25 11:37:56,846 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 19 [2024-09-25 11:37:57,733 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 100 treesize of output 57 [2024-09-25 11:37:57,753 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-25 11:37:57,898 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-09-25 11:37:57,898 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-25 11:37:57,963 INFO L349 Elim1Store]: treesize reduction 22, result has 56.0 percent of original size [2024-09-25 11:37:57,963 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 50 treesize of output 59 [2024-09-25 11:37:58,004 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 33 treesize of output 25 [2024-09-25 11:37:58,451 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:37:58,451 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 110 treesize of output 162 [2024-09-25 11:37:58,534 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:37:58,534 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 94 treesize of output 178 [2024-09-25 11:37:58,696 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:37:58,697 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 39 treesize of output 35 [2024-09-25 11:37:58,792 INFO L134 CoverageAnalysis]: Checked inductivity of 142 backedges. 48 proven. 29 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-09-25 11:37:58,793 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:38:02,015 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:38:02,015 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1125166413] [2024-09-25 11:38:02,015 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:38:02,015 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1593726241] [2024-09-25 11:38:02,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1593726241] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:38:02,016 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:38:02,016 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2024-09-25 11:38:02,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1362212836] [2024-09-25 11:38:02,016 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:38:02,016 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-09-25 11:38:02,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:38:02,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-09-25 11:38:02,017 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=896, Unknown=0, NotChecked=0, Total=992 [2024-09-25 11:38:02,017 INFO L87 Difference]: Start difference. First operand 123 states and 136 transitions. Second operand has 23 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 11 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-09-25 11:38:04,607 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:38:04,608 INFO L93 Difference]: Finished difference Result 165 states and 192 transitions. [2024-09-25 11:38:04,610 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-09-25 11:38:04,610 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 11 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) Word has length 83 [2024-09-25 11:38:04,610 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:38:04,612 INFO L225 Difference]: With dead ends: 165 [2024-09-25 11:38:04,612 INFO L226 Difference]: Without dead ends: 163 [2024-09-25 11:38:04,612 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 75 SyntacticMatches, 5 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 407 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=153, Invalid=1407, Unknown=0, NotChecked=0, Total=1560 [2024-09-25 11:38:04,613 INFO L434 NwaCegarLoop]: 37 mSDtfsCounter, 56 mSDsluCounter, 301 mSDsCounter, 0 mSdLazyCounter, 902 mSolverCounterSat, 32 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 338 SdHoareTripleChecker+Invalid, 938 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 902 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2024-09-25 11:38:04,613 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 338 Invalid, 938 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 902 Invalid, 4 Unknown, 0 Unchecked, 1.7s Time] [2024-09-25 11:38:04,614 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2024-09-25 11:38:04,682 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 159. [2024-09-25 11:38:04,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 159 states, 103 states have (on average 1.0970873786407767) internal successors, (113), 105 states have internal predecessors, (113), 30 states have call successors, (30), 24 states have call predecessors, (30), 25 states have return successors, (38), 29 states have call predecessors, (38), 27 states have call successors, (38) [2024-09-25 11:38:04,684 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 181 transitions. [2024-09-25 11:38:04,684 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 181 transitions. Word has length 83 [2024-09-25 11:38:04,685 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:38:04,685 INFO L474 AbstractCegarLoop]: Abstraction has 159 states and 181 transitions. [2024-09-25 11:38:04,685 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 18 states have (on average 2.0555555555555554) internal successors, (37), 18 states have internal predecessors, (37), 11 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (12), 8 states have call predecessors, (12), 8 states have call successors, (12) [2024-09-25 11:38:04,685 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:04,686 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 181 transitions. [2024-09-25 11:38:04,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2024-09-25 11:38:04,688 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:38:04,688 INFO L216 NwaCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:38:04,700 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-09-25 11:38:04,888 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,9 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:38:04,889 INFO L399 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:38:04,889 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:04,889 INFO L85 PathProgramCache]: Analyzing trace with hash -1725790163, now seen corresponding path program 2 times [2024-09-25 11:38:04,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:38:04,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2050171027] [2024-09-25 11:38:04,889 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:38:04,889 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:38:04,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:38:05,001 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [495742749] [2024-09-25 11:38:05,002 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-25 11:38:05,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:38:05,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:38:05,004 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-25 11:38:05,006 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-25 11:38:05,451 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-25 11:38:05,451 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-25 11:38:05,462 INFO L262 TraceCheckSpWp]: Trace formula consists of 634 conjuncts, 242 conjuncts are in the unsatisfiable core [2024-09-25 11:38:05,469 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:38:05,480 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-25 11:38:05,484 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-25 11:38:05,517 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 17 treesize of output 13 [2024-09-25 11:38:05,526 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-25 11:38:05,538 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-25 11:38:05,553 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 17 treesize of output 13 [2024-09-25 11:38:05,589 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 13 treesize of output 9 [2024-09-25 11:38:07,059 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-25 11:38:07,069 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 19 [2024-09-25 11:38:08,010 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 100 treesize of output 57 [2024-09-25 11:38:08,023 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-25 11:38:08,125 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-09-25 11:38:08,125 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-25 11:38:08,172 INFO L349 Elim1Store]: treesize reduction 22, result has 56.0 percent of original size [2024-09-25 11:38:08,172 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 50 treesize of output 59 [2024-09-25 11:38:08,177 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 35 treesize of output 27 [2024-09-25 11:38:08,571 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:38:08,572 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 112 treesize of output 164 [2024-09-25 11:38:08,665 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:38:08,666 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 180 treesize of output 252 [2024-09-25 11:38:08,695 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:38:08,696 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 113 treesize of output 97 [2024-09-25 11:38:08,980 INFO L134 CoverageAnalysis]: Checked inductivity of 279 backedges. 72 proven. 48 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-09-25 11:38:08,981 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:38:14,460 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:38:14,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2050171027] [2024-09-25 11:38:14,461 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:38:14,461 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [495742749] [2024-09-25 11:38:14,461 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [495742749] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:38:14,461 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:38:14,461 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2024-09-25 11:38:14,461 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1762932488] [2024-09-25 11:38:14,461 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:38:14,462 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-09-25 11:38:14,462 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:38:14,462 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-09-25 11:38:14,463 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=1083, Unknown=0, NotChecked=0, Total=1190 [2024-09-25 11:38:14,463 INFO L87 Difference]: Start difference. First operand 159 states and 181 transitions. Second operand has 25 states, 19 states have (on average 2.0526315789473686) internal successors, (39), 20 states have internal predecessors, (39), 12 states have call successors, (17), 7 states have call predecessors, (17), 7 states have return successors, (13), 9 states have call predecessors, (13), 9 states have call successors, (13) [2024-09-25 11:38:18,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:38:18,297 INFO L93 Difference]: Finished difference Result 201 states and 237 transitions. [2024-09-25 11:38:18,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2024-09-25 11:38:18,298 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 19 states have (on average 2.0526315789473686) internal successors, (39), 20 states have internal predecessors, (39), 12 states have call successors, (17), 7 states have call predecessors, (17), 7 states have return successors, (13), 9 states have call predecessors, (13), 9 states have call successors, (13) Word has length 107 [2024-09-25 11:38:18,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:38:18,300 INFO L225 Difference]: With dead ends: 201 [2024-09-25 11:38:18,300 INFO L226 Difference]: Without dead ends: 199 [2024-09-25 11:38:18,300 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 96 SyntacticMatches, 5 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 507 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=164, Invalid=1642, Unknown=0, NotChecked=0, Total=1806 [2024-09-25 11:38:18,301 INFO L434 NwaCegarLoop]: 46 mSDtfsCounter, 50 mSDsluCounter, 485 mSDsCounter, 0 mSdLazyCounter, 1543 mSolverCounterSat, 27 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 531 SdHoareTripleChecker+Invalid, 1572 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 1543 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.7s IncrementalHoareTripleChecker+Time [2024-09-25 11:38:18,302 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 531 Invalid, 1572 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 1543 Invalid, 2 Unknown, 0 Unchecked, 2.7s Time] [2024-09-25 11:38:18,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 199 states. [2024-09-25 11:38:18,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 199 to 161. [2024-09-25 11:38:18,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 161 states, 104 states have (on average 1.0961538461538463) internal successors, (114), 106 states have internal predecessors, (114), 30 states have call successors, (30), 24 states have call predecessors, (30), 26 states have return successors, (40), 30 states have call predecessors, (40), 27 states have call successors, (40) [2024-09-25 11:38:18,376 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 161 states to 161 states and 184 transitions. [2024-09-25 11:38:18,376 INFO L78 Accepts]: Start accepts. Automaton has 161 states and 184 transitions. Word has length 107 [2024-09-25 11:38:18,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:38:18,377 INFO L474 AbstractCegarLoop]: Abstraction has 161 states and 184 transitions. [2024-09-25 11:38:18,377 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 19 states have (on average 2.0526315789473686) internal successors, (39), 20 states have internal predecessors, (39), 12 states have call successors, (17), 7 states have call predecessors, (17), 7 states have return successors, (13), 9 states have call predecessors, (13), 9 states have call successors, (13) [2024-09-25 11:38:18,377 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:18,377 INFO L276 IsEmpty]: Start isEmpty. Operand 161 states and 184 transitions. [2024-09-25 11:38:18,378 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-09-25 11:38:18,379 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:38:18,379 INFO L216 NwaCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:38:18,388 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-09-25 11:38:18,579 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2024-09-25 11:38:18,580 INFO L399 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:38:18,580 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:18,580 INFO L85 PathProgramCache]: Analyzing trace with hash 138469860, now seen corresponding path program 3 times [2024-09-25 11:38:18,580 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:38:18,580 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1250872323] [2024-09-25 11:38:18,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:38:18,580 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:38:18,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:38:18,673 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2074852449] [2024-09-25 11:38:18,673 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-09-25 11:38:18,673 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:38:18,674 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:38:18,675 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-25 11:38:18,677 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-25 11:38:19,314 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-09-25 11:38:19,314 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-25 11:38:19,321 INFO L262 TraceCheckSpWp]: Trace formula consists of 665 conjuncts, 309 conjuncts are in the unsatisfiable core [2024-09-25 11:38:19,329 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:38:19,341 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-25 11:38:19,353 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-25 11:38:19,427 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-25 11:38:19,439 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 17 treesize of output 13 [2024-09-25 11:38:19,448 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 17 treesize of output 13 [2024-09-25 11:38:19,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-25 11:38:19,509 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 13 treesize of output 9 [2024-09-25 11:38:21,468 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 19 [2024-09-25 11:38:21,498 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-25 11:38:22,505 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-25 11:38:22,521 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 100 treesize of output 57 [2024-09-25 11:38:22,654 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 39 treesize of output 31 [2024-09-25 11:38:22,679 INFO L349 Elim1Store]: treesize reduction 22, result has 47.6 percent of original size [2024-09-25 11:38:22,679 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 52 treesize of output 55 [2024-09-25 11:38:22,733 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-25 11:38:22,747 INFO L349 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2024-09-25 11:38:22,748 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-25 11:38:23,060 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:38:23,060 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 94 treesize of output 102 [2024-09-25 11:38:23,095 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:38:23,095 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 82 treesize of output 98 [2024-09-25 11:38:23,104 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:38:23,104 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 41 treesize of output 33 [2024-09-25 11:38:23,260 INFO L134 CoverageAnalysis]: Checked inductivity of 464 backedges. 96 proven. 85 refuted. 0 times theorem prover too weak. 283 trivial. 0 not checked. [2024-09-25 11:38:23,260 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:38:28,057 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:38:28,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1250872323] [2024-09-25 11:38:28,058 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:38:28,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2074852449] [2024-09-25 11:38:28,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2074852449] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:38:28,058 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:38:28,058 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2024-09-25 11:38:28,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [405843127] [2024-09-25 11:38:28,058 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:38:28,058 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-09-25 11:38:28,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:38:28,059 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-09-25 11:38:28,060 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=1290, Unknown=0, NotChecked=0, Total=1406 [2024-09-25 11:38:28,060 INFO L87 Difference]: Start difference. First operand 161 states and 184 transitions. Second operand has 26 states, 20 states have (on average 2.25) internal successors, (45), 21 states have internal predecessors, (45), 12 states have call successors, (20), 7 states have call predecessors, (20), 8 states have return successors, (17), 10 states have call predecessors, (17), 9 states have call successors, (17) [2024-09-25 11:38:31,421 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:38:31,421 INFO L93 Difference]: Finished difference Result 203 states and 240 transitions. [2024-09-25 11:38:31,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-09-25 11:38:31,422 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 20 states have (on average 2.25) internal successors, (45), 21 states have internal predecessors, (45), 12 states have call successors, (20), 7 states have call predecessors, (20), 8 states have return successors, (17), 10 states have call predecessors, (17), 9 states have call successors, (17) Word has length 131 [2024-09-25 11:38:31,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:38:31,424 INFO L225 Difference]: With dead ends: 203 [2024-09-25 11:38:31,424 INFO L226 Difference]: Without dead ends: 201 [2024-09-25 11:38:31,424 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 119 SyntacticMatches, 3 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 557 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=175, Invalid=1895, Unknown=0, NotChecked=0, Total=2070 [2024-09-25 11:38:31,425 INFO L434 NwaCegarLoop]: 56 mSDtfsCounter, 60 mSDsluCounter, 475 mSDsCounter, 0 mSdLazyCounter, 1273 mSolverCounterSat, 32 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 531 SdHoareTripleChecker+Invalid, 1306 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 1273 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-09-25 11:38:31,425 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 531 Invalid, 1306 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 1273 Invalid, 1 Unknown, 0 Unchecked, 2.0s Time] [2024-09-25 11:38:31,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 201 states. [2024-09-25 11:38:31,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 201 to 163. [2024-09-25 11:38:31,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 105 states have (on average 1.0952380952380953) internal successors, (115), 107 states have internal predecessors, (115), 30 states have call successors, (30), 24 states have call predecessors, (30), 27 states have return successors, (42), 31 states have call predecessors, (42), 27 states have call successors, (42) [2024-09-25 11:38:31,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 187 transitions. [2024-09-25 11:38:31,544 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 187 transitions. Word has length 131 [2024-09-25 11:38:31,544 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:38:31,545 INFO L474 AbstractCegarLoop]: Abstraction has 163 states and 187 transitions. [2024-09-25 11:38:31,545 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 20 states have (on average 2.25) internal successors, (45), 21 states have internal predecessors, (45), 12 states have call successors, (20), 7 states have call predecessors, (20), 8 states have return successors, (17), 10 states have call predecessors, (17), 9 states have call successors, (17) [2024-09-25 11:38:31,545 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:31,545 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 187 transitions. [2024-09-25 11:38:31,546 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-09-25 11:38:31,547 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:38:31,547 INFO L216 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:38:31,557 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-09-25 11:38:31,747 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2024-09-25 11:38:31,748 INFO L399 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:38:31,748 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:31,748 INFO L85 PathProgramCache]: Analyzing trace with hash 24492033, now seen corresponding path program 4 times [2024-09-25 11:38:31,748 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:38:31,748 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [188812992] [2024-09-25 11:38:31,748 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:38:31,748 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:38:31,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:38:31,806 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1354660108] [2024-09-25 11:38:31,806 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-09-25 11:38:31,806 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:38:31,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:38:31,808 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-25 11:38:31,811 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-25 11:38:32,061 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-09-25 11:38:32,062 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-25 11:38:32,066 INFO L262 TraceCheckSpWp]: Trace formula consists of 543 conjuncts, 167 conjuncts are in the unsatisfiable core [2024-09-25 11:38:32,071 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:38:32,080 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-25 11:38:32,102 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 17 treesize of output 13 [2024-09-25 11:38:32,109 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-25 11:38:32,127 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 13 treesize of output 9 [2024-09-25 11:38:32,357 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-25 11:38:32,577 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-25 11:38:32,590 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 42 treesize of output 26 [2024-09-25 11:38:32,599 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2024-09-25 11:38:33,067 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-25 11:38:33,074 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 115 treesize of output 68 [2024-09-25 11:38:33,320 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 13 [2024-09-25 11:38:33,322 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 14 [2024-09-25 11:38:33,394 INFO L134 CoverageAnalysis]: Checked inductivity of 178 backedges. 74 proven. 54 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-09-25 11:38:33,394 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:38:34,773 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 27 treesize of output 19 [2024-09-25 11:38:36,192 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:38:36,192 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [188812992] [2024-09-25 11:38:36,192 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:38:36,192 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1354660108] [2024-09-25 11:38:36,192 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1354660108] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:38:36,192 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:38:36,192 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2024-09-25 11:38:36,193 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1463176563] [2024-09-25 11:38:36,193 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:38:36,193 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-09-25 11:38:36,193 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:38:36,193 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-09-25 11:38:36,194 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=96, Invalid=1026, Unknown=0, NotChecked=0, Total=1122 [2024-09-25 11:38:36,194 INFO L87 Difference]: Start difference. First operand 163 states and 187 transitions. Second operand has 24 states, 20 states have (on average 2.2) internal successors, (44), 19 states have internal predecessors, (44), 10 states have call successors, (17), 7 states have call predecessors, (17), 6 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) [2024-09-25 11:38:38,524 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:38:38,524 INFO L93 Difference]: Finished difference Result 240 states and 275 transitions. [2024-09-25 11:38:38,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2024-09-25 11:38:38,525 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 20 states have (on average 2.2) internal successors, (44), 19 states have internal predecessors, (44), 10 states have call successors, (17), 7 states have call predecessors, (17), 6 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) Word has length 89 [2024-09-25 11:38:38,525 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:38:38,527 INFO L225 Difference]: With dead ends: 240 [2024-09-25 11:38:38,527 INFO L226 Difference]: Without dead ends: 238 [2024-09-25 11:38:38,528 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 87 SyntacticMatches, 4 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 553 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=241, Invalid=2621, Unknown=0, NotChecked=0, Total=2862 [2024-09-25 11:38:38,529 INFO L434 NwaCegarLoop]: 25 mSDtfsCounter, 50 mSDsluCounter, 208 mSDsCounter, 0 mSdLazyCounter, 1196 mSolverCounterSat, 33 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 54 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 1230 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 1196 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2024-09-25 11:38:38,529 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [54 Valid, 233 Invalid, 1230 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 1196 Invalid, 1 Unknown, 0 Unchecked, 1.0s Time] [2024-09-25 11:38:38,529 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 238 states. [2024-09-25 11:38:38,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 238 to 226. [2024-09-25 11:38:38,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 226 states, 147 states have (on average 1.0952380952380953) internal successors, (161), 150 states have internal predecessors, (161), 41 states have call successors, (41), 34 states have call predecessors, (41), 37 states have return successors, (58), 41 states have call predecessors, (58), 37 states have call successors, (58) [2024-09-25 11:38:38,660 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 226 states to 226 states and 260 transitions. [2024-09-25 11:38:38,661 INFO L78 Accepts]: Start accepts. Automaton has 226 states and 260 transitions. Word has length 89 [2024-09-25 11:38:38,661 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:38:38,661 INFO L474 AbstractCegarLoop]: Abstraction has 226 states and 260 transitions. [2024-09-25 11:38:38,661 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 20 states have (on average 2.2) internal successors, (44), 19 states have internal predecessors, (44), 10 states have call successors, (17), 7 states have call predecessors, (17), 6 states have return successors, (13), 8 states have call predecessors, (13), 8 states have call successors, (13) [2024-09-25 11:38:38,661 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:38,661 INFO L276 IsEmpty]: Start isEmpty. Operand 226 states and 260 transitions. [2024-09-25 11:38:38,663 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 156 [2024-09-25 11:38:38,663 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:38:38,663 INFO L216 NwaCegarLoop]: trace histogram [18, 17, 17, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:38:38,681 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-09-25 11:38:38,863 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2024-09-25 11:38:38,864 INFO L399 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:38:38,864 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:38:38,864 INFO L85 PathProgramCache]: Analyzing trace with hash -1960678181, now seen corresponding path program 5 times [2024-09-25 11:38:38,864 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:38:38,864 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2069964774] [2024-09-25 11:38:38,864 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:38:38,864 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:38:38,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:38:38,996 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [189118231] [2024-09-25 11:38:38,997 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-09-25 11:38:38,997 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:38:38,997 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:38:38,998 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-25 11:38:39,000 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-09-25 11:38:40,923 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2024-09-25 11:38:40,923 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-25 11:38:40,932 INFO L262 TraceCheckSpWp]: Trace formula consists of 846 conjuncts, 361 conjuncts are in the unsatisfiable core [2024-09-25 11:38:40,941 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:38:40,958 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-25 11:38:40,962 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-25 11:38:40,989 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 17 treesize of output 13 [2024-09-25 11:38:41,005 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 17 treesize of output 13 [2024-09-25 11:38:41,015 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-25 11:38:41,048 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 13 treesize of output 9 [2024-09-25 11:39:20,155 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-09-25 11:39:33,411 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-25 11:39:33,432 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 44 treesize of output 28 [2024-09-25 11:39:34,761 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-25 11:39:34,788 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 113 treesize of output 66 [2024-09-25 11:39:35,031 INFO L349 Elim1Store]: treesize reduction 84, result has 49.4 percent of original size [2024-09-25 11:39:35,031 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 9 case distinctions, treesize of input 40 treesize of output 101 [2024-09-25 11:39:35,083 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 39 treesize of output 31 [2024-09-25 11:39:35,105 INFO L349 Elim1Store]: treesize reduction 22, result has 47.6 percent of original size [2024-09-25 11:39:35,105 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 84 treesize of output 79 [2024-09-25 11:39:35,537 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:39:35,537 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 134 treesize of output 126 [2024-09-25 11:39:35,548 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 103 treesize of output 83 [2024-09-25 11:39:35,586 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:39:35,587 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 78 treesize of output 102 [2024-09-25 11:39:35,803 INFO L134 CoverageAnalysis]: Checked inductivity of 697 backedges. 239 proven. 218 refuted. 0 times theorem prover too weak. 240 trivial. 0 not checked. [2024-09-25 11:39:35,803 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:39:40,190 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 8 treesize of output 4 [2024-09-25 11:39:44,672 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-25 11:39:44,672 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2069964774] [2024-09-25 11:39:44,672 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-25 11:39:44,673 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [189118231] [2024-09-25 11:39:44,673 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [189118231] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-25 11:39:44,673 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-25 11:39:44,673 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [44] total 44 [2024-09-25 11:39:44,673 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [945042353] [2024-09-25 11:39:44,673 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-25 11:39:44,674 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2024-09-25 11:39:44,674 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-25 11:39:44,675 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2024-09-25 11:39:44,675 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=256, Invalid=2604, Unknown=2, NotChecked=0, Total=2862 [2024-09-25 11:39:44,676 INFO L87 Difference]: Start difference. First operand 226 states and 260 transitions. Second operand has 44 states, 35 states have (on average 1.8) internal successors, (63), 36 states have internal predecessors, (63), 18 states have call successors, (25), 11 states have call predecessors, (25), 11 states have return successors, (21), 13 states have call predecessors, (21), 15 states have call successors, (21) [2024-09-25 11:39:52,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-25 11:39:52,094 INFO L93 Difference]: Finished difference Result 278 states and 327 transitions. [2024-09-25 11:39:52,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2024-09-25 11:39:52,096 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 35 states have (on average 1.8) internal successors, (63), 36 states have internal predecessors, (63), 18 states have call successors, (25), 11 states have call predecessors, (25), 11 states have return successors, (21), 13 states have call predecessors, (21), 15 states have call successors, (21) Word has length 155 [2024-09-25 11:39:52,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-25 11:39:52,098 INFO L225 Difference]: With dead ends: 278 [2024-09-25 11:39:52,098 INFO L226 Difference]: Without dead ends: 276 [2024-09-25 11:39:52,100 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 100 SyntacticMatches, 30 SemanticMatches, 72 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2209 ImplicationChecksByTransitivity, 58.5s TimeCoverageRelationStatistics Valid=500, Invalid=4900, Unknown=2, NotChecked=0, Total=5402 [2024-09-25 11:39:52,100 INFO L434 NwaCegarLoop]: 58 mSDtfsCounter, 77 mSDsluCounter, 693 mSDsCounter, 0 mSdLazyCounter, 2181 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 80 SdHoareTripleChecker+Valid, 751 SdHoareTripleChecker+Invalid, 2234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 2181 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.9s IncrementalHoareTripleChecker+Time [2024-09-25 11:39:52,101 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [80 Valid, 751 Invalid, 2234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 2181 Invalid, 0 Unknown, 0 Unchecked, 3.9s Time] [2024-09-25 11:39:52,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 276 states. [2024-09-25 11:39:52,298 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 276 to 262. [2024-09-25 11:39:52,298 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 262 states, 171 states have (on average 1.0994152046783625) internal successors, (188), 174 states have internal predecessors, (188), 47 states have call successors, (47), 39 states have call predecessors, (47), 43 states have return successors, (70), 48 states have call predecessors, (70), 43 states have call successors, (70) [2024-09-25 11:39:52,299 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 262 states to 262 states and 305 transitions. [2024-09-25 11:39:52,300 INFO L78 Accepts]: Start accepts. Automaton has 262 states and 305 transitions. Word has length 155 [2024-09-25 11:39:52,300 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-25 11:39:52,301 INFO L474 AbstractCegarLoop]: Abstraction has 262 states and 305 transitions. [2024-09-25 11:39:52,301 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 35 states have (on average 1.8) internal successors, (63), 36 states have internal predecessors, (63), 18 states have call successors, (25), 11 states have call predecessors, (25), 11 states have return successors, (21), 13 states have call predecessors, (21), 15 states have call successors, (21) [2024-09-25 11:39:52,301 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:39:52,301 INFO L276 IsEmpty]: Start isEmpty. Operand 262 states and 305 transitions. [2024-09-25 11:39:52,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2024-09-25 11:39:52,302 INFO L208 NwaCegarLoop]: Found error trace [2024-09-25 11:39:52,302 INFO L216 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-25 11:39:52,314 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-09-25 11:39:52,503 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2024-09-25 11:39:52,503 INFO L399 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-25 11:39:52,504 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-25 11:39:52,504 INFO L85 PathProgramCache]: Analyzing trace with hash -81781960, now seen corresponding path program 6 times [2024-09-25 11:39:52,504 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-25 11:39:52,504 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1447923564] [2024-09-25 11:39:52,504 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-25 11:39:52,504 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-25 11:39:52,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-25 11:39:52,586 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1723425743] [2024-09-25 11:39:52,587 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-09-25 11:39:52,587 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-25 11:39:52,587 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-25 11:39:52,588 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-09-25 11:39:52,590 INFO L327 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-09-25 11:39:53,103 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2024-09-25 11:39:53,104 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-25 11:39:53,108 INFO L262 TraceCheckSpWp]: Trace formula consists of 580 conjuncts, 190 conjuncts are in the unsatisfiable core [2024-09-25 11:39:53,113 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-25 11:39:53,128 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-25 11:39:53,189 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 17 treesize of output 13 [2024-09-25 11:39:53,206 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-25 11:39:53,246 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 13 treesize of output 9 [2024-09-25 11:39:54,055 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-25 11:39:54,068 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 19 [2024-09-25 11:39:54,532 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-25 11:39:54,541 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 100 treesize of output 57 [2024-09-25 11:39:54,825 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-25 11:39:54,831 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-25 11:39:54,831 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 37 treesize of output 29 [2024-09-25 11:39:54,894 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 108 proven. 60 refuted. 0 times theorem prover too weak. 159 trivial. 0 not checked. [2024-09-25 11:39:54,894 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-25 11:40:01,734 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 20 treesize of output 16 [2024-09-25 11:40:01,747 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