./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c --full-output --procedureinliner.inline.calls.to.implemented.procedures NEVER --traceabstraction.positions.where.we.compute.the.hoare.annotation All --witnessprinter.yaml.format.version 2.1 --witnessprinter.generate.graphml.witnesses false --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version ca4ee3dd Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/certificate-witnesses-artifact/automizer/data/config -Xmx15G -Xms4m -jar /storage/repos/certificate-witnesses-artifact/automizer/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/certificate-witnesses-artifact/automizer/data -tc /storage/repos/certificate-witnesses-artifact/automizer/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-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 5ace794fa35bd3dd49302fe61957917bbb7565f1b1f34293812fc47531868d51 --procedureinliner.inline.calls.to.implemented.procedures NEVER --traceabstraction.positions.where.we.compute.the.hoare.annotation All --witnessprinter.yaml.format.version 2.1 --witnessprinter.generate.graphml.witnesses false --- Real Ultimate output --- This is Ultimate 0.2.4-tmp.dk.referee-eval-ca4ee3d-m [2024-09-20 20:02:12,172 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-09-20 20:02:12,225 INFO L114 SettingsManager]: Loading settings from /storage/repos/certificate-witnesses-artifact/automizer/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-09-20 20:02:12,228 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-09-20 20:02:12,229 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-09-20 20:02:12,259 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-09-20 20:02:12,260 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-09-20 20:02:12,260 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-09-20 20:02:12,260 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-09-20 20:02:12,260 INFO L153 SettingsManager]: * Use memory slicer=true [2024-09-20 20:02:12,261 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-09-20 20:02:12,261 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-09-20 20:02:12,264 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-09-20 20:02:12,264 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-09-20 20:02:12,264 INFO L153 SettingsManager]: * Use SBE=true [2024-09-20 20:02:12,266 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-09-20 20:02:12,266 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-09-20 20:02:12,266 INFO L153 SettingsManager]: * sizeof long=4 [2024-09-20 20:02:12,267 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-09-20 20:02:12,267 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-09-20 20:02:12,267 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-09-20 20:02:12,271 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-09-20 20:02:12,271 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-09-20 20:02:12,271 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-09-20 20:02:12,271 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-09-20 20:02:12,271 INFO L153 SettingsManager]: * sizeof long double=12 [2024-09-20 20:02:12,271 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-09-20 20:02:12,272 INFO L153 SettingsManager]: * Use constant arrays=true [2024-09-20 20:02:12,272 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-09-20 20:02:12,272 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-09-20 20:02:12,272 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-09-20 20:02:12,272 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-09-20 20:02:12,272 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-20 20:02:12,272 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-09-20 20:02:12,273 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-09-20 20:02:12,273 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-09-20 20:02:12,273 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-09-20 20:02:12,273 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-09-20 20:02:12,273 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-09-20 20:02:12,273 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-09-20 20:02:12,273 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-09-20 20:02:12,274 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-09-20 20:02:12,275 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 -> 5ace794fa35bd3dd49302fe61957917bbb7565f1b1f34293812fc47531868d51 Applying setting for plugin de.uni_freiburg.informatik.ultimate.boogie.procedureinliner: Inline calls to implemented procedures -> NEVER Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Positions where we compute the Hoare Annotation -> All Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: YAML Format version -> 2.1 Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Generate GraphML witnesses -> false [2024-09-20 20:02:12,489 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-09-20 20:02:12,508 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-09-20 20:02:12,510 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-09-20 20:02:12,511 INFO L270 PluginConnector]: Initializing CDTParser... [2024-09-20 20:02:12,511 INFO L274 PluginConnector]: CDTParser initialized [2024-09-20 20:02:12,512 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/certificate-witnesses-artifact/automizer/../sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c [2024-09-20 20:02:13,730 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-09-20 20:02:13,886 INFO L384 CDTParser]: Found 1 translation units. [2024-09-20 20:02:13,886 INFO L180 CDTParser]: Scanning /storage/repos/certificate-witnesses-artifact/sv-benchmarks/c/recursified_nla-digbench/recursified_prodbin-ll.c [2024-09-20 20:02:13,892 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/certificate-witnesses-artifact/automizer/data/10c98f352/ccbedb2af57742b5aac54efa2854918c/FLAGc751b10a2 [2024-09-20 20:02:14,304 INFO L435 CDTParser]: Successfully deleted /storage/repos/certificate-witnesses-artifact/automizer/data/10c98f352/ccbedb2af57742b5aac54efa2854918c [2024-09-20 20:02:14,306 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-09-20 20:02:14,307 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-09-20 20:02:14,310 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-09-20 20:02:14,310 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-09-20 20:02:14,314 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-09-20 20:02:14,314 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,315 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4c707332 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14, skipping insertion in model container [2024-09-20 20:02:14,315 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,331 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-09-20 20:02:14,449 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_prodbin-ll.c[1073,1086] [2024-09-20 20:02:14,466 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-20 20:02:14,474 INFO L200 MainTranslator]: Completed pre-run [2024-09-20 20:02:14,483 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_prodbin-ll.c[1073,1086] [2024-09-20 20:02:14,489 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-09-20 20:02:14,502 INFO L204 MainTranslator]: Completed translation [2024-09-20 20:02:14,502 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14 WrapperNode [2024-09-20 20:02:14,505 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-09-20 20:02:14,506 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-09-20 20:02:14,506 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-09-20 20:02:14,510 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-09-20 20:02:14,515 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,521 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,526 INFO L138 Inliner]: procedures = 16, calls = 54, calls flagged for inlining = 0, calls inlined = 0, statements flattened = 0 [2024-09-20 20:02:14,527 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-09-20 20:02:14,527 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-09-20 20:02:14,527 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-09-20 20:02:14,528 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-09-20 20:02:14,536 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,537 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,538 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,552 INFO L175 MemorySlicer]: Split 29 memory accesses to 6 slices as follows [2, 5, 8, 5, 4, 5]. 28 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0]. The 9 writes are split as follows [0, 2, 3, 1, 1, 2]. [2024-09-20 20:02:14,553 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,553 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,563 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,565 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,566 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,567 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,568 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-09-20 20:02:14,569 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-09-20 20:02:14,569 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-09-20 20:02:14,569 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-09-20 20:02:14,570 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (1/1) ... [2024-09-20 20:02:14,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-09-20 20:02:14,583 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:02:14,608 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-20 20:02:14,619 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-20 20:02:14,654 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-09-20 20:02:14,654 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-09-20 20:02:14,655 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-09-20 20:02:14,655 INFO L130 BoogieDeclarations]: Found specification of procedure main [2024-09-20 20:02:14,655 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2024-09-20 20:02:14,655 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-09-20 20:02:14,655 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-09-20 20:02:14,655 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-09-20 20:02:14,655 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-09-20 20:02:14,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-09-20 20:02:14,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-09-20 20:02:14,656 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-09-20 20:02:14,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-09-20 20:02:14,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-09-20 20:02:14,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-09-20 20:02:14,656 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-09-20 20:02:14,657 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-09-20 20:02:14,657 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-09-20 20:02:14,657 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2024-09-20 20:02:14,657 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2024-09-20 20:02:14,657 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_0_to_40_0 [2024-09-20 20:02:14,657 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_0_to_40_0 [2024-09-20 20:02:14,657 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-09-20 20:02:14,657 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-09-20 20:02:14,658 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-09-20 20:02:14,658 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-09-20 20:02:14,658 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-09-20 20:02:14,658 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-09-20 20:02:14,658 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-09-20 20:02:14,660 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-09-20 20:02:14,660 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-09-20 20:02:14,660 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-09-20 20:02:14,660 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-09-20 20:02:14,731 INFO L242 CfgBuilder]: Building ICFG [2024-09-20 20:02:14,732 INFO L268 CfgBuilder]: Building CFG for each procedure with an implementation [2024-09-20 20:02:14,865 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-09-20 20:02:14,865 INFO L291 CfgBuilder]: Performing block encoding [2024-09-20 20:02:14,879 INFO L313 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-09-20 20:02:14,879 INFO L318 CfgBuilder]: Removed 1 assume(true) statements. [2024-09-20 20:02:14,880 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.09 08:02:14 BoogieIcfgContainer [2024-09-20 20:02:14,880 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-09-20 20:02:14,882 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-09-20 20:02:14,882 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-09-20 20:02:14,885 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-09-20 20:02:14,885 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.09 08:02:14" (1/3) ... [2024-09-20 20:02:14,885 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2be126b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.09 08:02:14, skipping insertion in model container [2024-09-20 20:02:14,886 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.09 08:02:14" (2/3) ... [2024-09-20 20:02:14,886 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2be126b4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.09 08:02:14, skipping insertion in model container [2024-09-20 20:02:14,886 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.09 08:02:14" (3/3) ... [2024-09-20 20:02:14,887 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_prodbin-ll.c [2024-09-20 20:02:14,899 INFO L209 ceAbstractionStarter]: Automizer settings: Hoare:All NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-09-20 20:02:14,900 INFO L149 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-09-20 20:02:14,942 INFO L335 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-09-20 20:02:14,947 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;@4b479ba0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-09-20 20:02:14,947 INFO L337 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-09-20 20:02:14,950 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.3) internal successors, (26), 22 states have internal predecessors, (26), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-09-20 20:02:14,957 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-09-20 20:02:14,957 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:02:14,958 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-20 20:02:14,958 INFO L399 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:02:14,962 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:14,962 INFO L85 PathProgramCache]: Analyzing trace with hash 574913788, now seen corresponding path program 1 times [2024-09-20 20:02:14,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:02:14,969 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2066425886] [2024-09-20 20:02:14,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:14,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:02:15,086 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:15,131 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-20 20:02:15,133 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:15,142 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-20 20:02:15,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:15,157 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-20 20:02:15,158 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:02:15,158 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2066425886] [2024-09-20 20:02:15,159 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2066425886] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-20 20:02:15,159 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-20 20:02:15,159 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-09-20 20:02:15,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1525398630] [2024-09-20 20:02:15,161 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-20 20:02:15,164 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-09-20 20:02:15,164 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:02:15,181 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-09-20 20:02:15,182 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-09-20 20:02:15,183 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.3) internal successors, (26), 22 states have internal predecessors, (26), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-09-20 20:02:15,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:02:15,205 INFO L93 Difference]: Finished difference Result 60 states and 75 transitions. [2024-09-20 20:02:15,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-09-20 20:02:15,207 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2024-09-20 20:02:15,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:02:15,212 INFO L225 Difference]: With dead ends: 60 [2024-09-20 20:02:15,212 INFO L226 Difference]: Without dead ends: 30 [2024-09-20 20:02:15,241 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-09-20 20:02:15,254 INFO L434 NwaCegarLoop]: 35 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-09-20 20:02:15,254 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 35 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-09-20 20:02:15,268 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2024-09-20 20:02:15,298 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2024-09-20 20:02:15,299 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 20 states have internal predecessors, (21), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-09-20 20:02:15,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 33 transitions. [2024-09-20 20:02:15,305 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 33 transitions. Word has length 18 [2024-09-20 20:02:15,305 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:02:15,305 INFO L474 AbstractCegarLoop]: Abstraction has 30 states and 33 transitions. [2024-09-20 20:02:15,308 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.5) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2024-09-20 20:02:15,309 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:15,309 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 33 transitions. [2024-09-20 20:02:15,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2024-09-20 20:02:15,309 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:02:15,309 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-20 20:02:15,309 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-09-20 20:02:15,310 INFO L399 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:02:15,310 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:15,310 INFO L85 PathProgramCache]: Analyzing trace with hash 1275978366, now seen corresponding path program 1 times [2024-09-20 20:02:15,310 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:02:15,310 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [860412478] [2024-09-20 20:02:15,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:15,310 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:02:15,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:02:15,370 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1393202742] [2024-09-20 20:02:15,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:15,371 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:02:15,371 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:02:15,373 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-20 20:02:15,374 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-20 20:02:15,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:15,479 INFO L262 TraceCheckSpWp]: Trace formula consists of 192 conjuncts, 75 conjuncts are in the unsatisfiable core [2024-09-20 20:02:15,490 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:02:15,541 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-20 20:02:15,545 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-20 20:02:15,556 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-20 20:02:15,565 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 11 [2024-09-20 20:02:15,572 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 11 [2024-09-20 20:02:15,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 19 treesize of output 11 [2024-09-20 20:02:15,658 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 15 treesize of output 7 [2024-09-20 20:02:15,663 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-20 20:02:15,666 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 15 treesize of output 7 [2024-09-20 20:02:15,702 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-20 20:02:15,702 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-09-20 20:02:15,703 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:02:15,703 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [860412478] [2024-09-20 20:02:15,703 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:02:15,703 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1393202742] [2024-09-20 20:02:15,703 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1393202742] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-20 20:02:15,704 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-20 20:02:15,704 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-09-20 20:02:15,705 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1751862998] [2024-09-20 20:02:15,706 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-20 20:02:15,707 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-09-20 20:02:15,707 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:02:15,708 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-09-20 20:02:15,709 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-09-20 20:02:15,709 INFO L87 Difference]: Start difference. First operand 30 states and 33 transitions. 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-20 20:02:15,870 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:02:15,870 INFO L93 Difference]: Finished difference Result 46 states and 51 transitions. [2024-09-20 20:02:15,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-09-20 20:02:15,871 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-20 20:02:15,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:02:15,872 INFO L225 Difference]: With dead ends: 46 [2024-09-20 20:02:15,872 INFO L226 Difference]: Without dead ends: 44 [2024-09-20 20:02:15,873 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 11 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-20 20:02:15,874 INFO L434 NwaCegarLoop]: 22 mSDtfsCounter, 16 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 101 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-20 20:02:15,876 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 139 Invalid, 101 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-20 20:02:15,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2024-09-20 20:02:15,885 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 41. [2024-09-20 20:02:15,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 28 states have internal predecessors, (30), 8 states have call successors, (8), 7 states have call predecessors, (8), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-09-20 20:02:15,887 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 45 transitions. [2024-09-20 20:02:15,888 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 45 transitions. Word has length 18 [2024-09-20 20:02:15,888 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:02:15,889 INFO L474 AbstractCegarLoop]: Abstraction has 41 states and 45 transitions. [2024-09-20 20:02:15,889 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-20 20:02:15,889 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:15,889 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2024-09-20 20:02:15,890 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-09-20 20:02:15,891 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:02:15,891 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, 1, 1, 1, 1] [2024-09-20 20:02:15,909 INFO L540 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2024-09-20 20:02:16,094 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:02:16,095 INFO L399 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:02:16,095 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:16,096 INFO L85 PathProgramCache]: Analyzing trace with hash 936628089, now seen corresponding path program 1 times [2024-09-20 20:02:16,096 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:02:16,096 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [60368446] [2024-09-20 20:02:16,097 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:16,097 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:02:16,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:16,528 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-20 20:02:16,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:16,531 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-20 20:02:16,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:16,557 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-20 20:02:16,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:16,616 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-20 20:02:16,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:16,621 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-20 20:02:16,622 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:02:16,622 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [60368446] [2024-09-20 20:02:16,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [60368446] provided 1 perfect and 0 imperfect interpolant sequences [2024-09-20 20:02:16,622 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-09-20 20:02:16,622 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2024-09-20 20:02:16,622 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1921428143] [2024-09-20 20:02:16,622 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-09-20 20:02:16,623 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-09-20 20:02:16,623 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:02:16,623 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-09-20 20:02:16,624 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2024-09-20 20:02:16,624 INFO L87 Difference]: Start difference. First operand 41 states and 45 transitions. Second operand has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 5 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-09-20 20:02:16,840 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:02:16,841 INFO L93 Difference]: Finished difference Result 52 states and 55 transitions. [2024-09-20 20:02:16,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-09-20 20:02:16,841 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 5 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 28 [2024-09-20 20:02:16,842 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:02:16,843 INFO L225 Difference]: With dead ends: 52 [2024-09-20 20:02:16,844 INFO L226 Difference]: Without dead ends: 42 [2024-09-20 20:02:16,844 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=283, Unknown=0, NotChecked=0, Total=342 [2024-09-20 20:02:16,846 INFO L434 NwaCegarLoop]: 14 mSDtfsCounter, 23 mSDsluCounter, 55 mSDsCounter, 0 mSdLazyCounter, 196 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 23 SdHoareTripleChecker+Valid, 69 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 196 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-09-20 20:02:16,848 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [23 Valid, 69 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 196 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-09-20 20:02:16,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2024-09-20 20:02:16,858 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2024-09-20 20:02:16,858 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 27 states have internal predecessors, (29), 8 states have call successors, (8), 7 states have call predecessors, (8), 6 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-09-20 20:02:16,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 44 transitions. [2024-09-20 20:02:16,861 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 44 transitions. Word has length 28 [2024-09-20 20:02:16,861 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:02:16,861 INFO L474 AbstractCegarLoop]: Abstraction has 41 states and 44 transitions. [2024-09-20 20:02:16,862 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 5 states have call successors, (6), 3 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-09-20 20:02:16,863 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:16,863 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 44 transitions. [2024-09-20 20:02:16,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-09-20 20:02:16,864 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:02:16,864 INFO L216 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:02:16,864 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-09-20 20:02:16,865 INFO L399 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:02:16,865 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:16,865 INFO L85 PathProgramCache]: Analyzing trace with hash -1861020597, now seen corresponding path program 1 times [2024-09-20 20:02:16,865 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:02:16,865 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1334983170] [2024-09-20 20:02:16,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:16,866 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:02:16,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:02:16,912 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [757401362] [2024-09-20 20:02:16,912 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:16,912 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:02:16,913 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:02:16,914 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-20 20:02:16,915 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-20 20:02:17,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:17,031 INFO L262 TraceCheckSpWp]: Trace formula consists of 280 conjuncts, 135 conjuncts are in the unsatisfiable core [2024-09-20 20:02:17,036 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:02:17,043 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-20 20:02:17,047 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-20 20:02:17,054 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 11 [2024-09-20 20:02:17,063 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 11 [2024-09-20 20:02:17,068 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-20 20:02:17,282 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 23 treesize of output 15 [2024-09-20 20:02:17,288 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 53 treesize of output 29 [2024-09-20 20:02:17,344 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 97 treesize of output 71 [2024-09-20 20:02:17,347 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 71 treesize of output 69 [2024-09-20 20:02:17,375 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 13 [2024-09-20 20:02:17,383 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 40 treesize of output 24 [2024-09-20 20:02:17,495 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-20 20:02:17,498 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-20 20:02:17,500 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-20 20:02:17,506 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-20 20:02:17,511 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 19 [2024-09-20 20:02:18,081 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-20 20:02:18,082 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:02:23,378 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-20 20:02:23,378 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:02:23,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1334983170] [2024-09-20 20:02:23,379 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:02:23,379 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [757401362] [2024-09-20 20:02:23,379 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [757401362] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-20 20:02:23,379 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-20 20:02:23,379 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 23 [2024-09-20 20:02:23,379 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1003049137] [2024-09-20 20:02:23,379 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-20 20:02:23,380 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-09-20 20:02:23,380 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:02:23,380 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-09-20 20:02:23,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=77, Invalid=429, Unknown=0, NotChecked=0, Total=506 [2024-09-20 20:02:23,381 INFO L87 Difference]: Start difference. First operand 41 states and 44 transitions. Second operand has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 18 states have internal predecessors, (32), 9 states have call successors, (11), 7 states have call predecessors, (11), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-09-20 20:02:28,972 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-20 20:02:35,626 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:02:35,626 INFO L93 Difference]: Finished difference Result 75 states and 87 transitions. [2024-09-20 20:02:35,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-09-20 20:02:35,626 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 18 states have internal predecessors, (32), 9 states have call successors, (11), 7 states have call predecessors, (11), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 30 [2024-09-20 20:02:35,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:02:35,628 INFO L225 Difference]: With dead ends: 75 [2024-09-20 20:02:35,628 INFO L226 Difference]: Without dead ends: 73 [2024-09-20 20:02:35,629 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 35 SyntacticMatches, 3 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 204 ImplicationChecksByTransitivity, 10.4s TimeCoverageRelationStatistics Valid=214, Invalid=1118, Unknown=0, NotChecked=0, Total=1332 [2024-09-20 20:02:35,629 INFO L434 NwaCegarLoop]: 21 mSDtfsCounter, 51 mSDsluCounter, 241 mSDsCounter, 0 mSdLazyCounter, 382 mSolverCounterSat, 18 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 262 SdHoareTripleChecker+Invalid, 401 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 382 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.6s IncrementalHoareTripleChecker+Time [2024-09-20 20:02:35,630 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 262 Invalid, 401 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 382 Invalid, 1 Unknown, 0 Unchecked, 6.6s Time] [2024-09-20 20:02:35,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-09-20 20:02:35,643 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 69. [2024-09-20 20:02:35,644 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 45 states have (on average 1.1555555555555554) internal successors, (52), 48 states have internal predecessors, (52), 12 states have call successors, (12), 10 states have call predecessors, (12), 11 states have return successors, (16), 10 states have call predecessors, (16), 10 states have call successors, (16) [2024-09-20 20:02:35,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 80 transitions. [2024-09-20 20:02:35,645 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 80 transitions. Word has length 30 [2024-09-20 20:02:35,645 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:02:35,645 INFO L474 AbstractCegarLoop]: Abstraction has 69 states and 80 transitions. [2024-09-20 20:02:35,645 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 19 states have (on average 1.6842105263157894) internal successors, (32), 18 states have internal predecessors, (32), 9 states have call successors, (11), 7 states have call predecessors, (11), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-09-20 20:02:35,645 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:35,645 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 80 transitions. [2024-09-20 20:02:35,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2024-09-20 20:02:35,646 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:02:35,646 INFO L216 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:02:35,662 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-09-20 20:02:35,847 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-20 20:02:35,847 INFO L399 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:02:35,847 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:35,848 INFO L85 PathProgramCache]: Analyzing trace with hash -1180962227, now seen corresponding path program 1 times [2024-09-20 20:02:35,848 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:02:35,848 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [480790011] [2024-09-20 20:02:35,848 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:35,848 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:02:35,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:02:35,884 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1970085475] [2024-09-20 20:02:35,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:35,884 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:02:35,884 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:02:35,886 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-20 20:02:35,887 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-20 20:02:35,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:35,969 INFO L262 TraceCheckSpWp]: Trace formula consists of 271 conjuncts, 133 conjuncts are in the unsatisfiable core [2024-09-20 20:02:35,974 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:02:35,980 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-20 20:02:35,982 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-20 20:02:36,004 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-20 20:02:36,008 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 11 [2024-09-20 20:02:36,012 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 11 [2024-09-20 20:02:36,257 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 105 treesize of output 77 [2024-09-20 20:02:36,260 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 77 treesize of output 73 [2024-09-20 20:02:36,267 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 11 [2024-09-20 20:02:36,275 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 29 treesize of output 17 [2024-09-20 20:02:36,363 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-20 20:02:36,365 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-20 20:02:36,370 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 38 treesize of output 22 [2024-09-20 20:02:36,373 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-20 20:02:36,472 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-20 20:02:36,472 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:02:37,910 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-20 20:02:37,911 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:02:37,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [480790011] [2024-09-20 20:02:37,911 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:02:37,911 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1970085475] [2024-09-20 20:02:37,911 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1970085475] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-20 20:02:37,911 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-20 20:02:37,911 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16] total 29 [2024-09-20 20:02:37,911 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [717855841] [2024-09-20 20:02:37,911 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-20 20:02:37,911 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 29 states [2024-09-20 20:02:37,911 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:02:37,912 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-09-20 20:02:37,913 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=720, Unknown=0, NotChecked=0, Total=812 [2024-09-20 20:02:37,913 INFO L87 Difference]: Start difference. First operand 69 states and 80 transitions. Second operand has 29 states, 23 states have (on average 1.565217391304348) internal successors, (36), 22 states have internal predecessors, (36), 11 states have call successors, (12), 7 states have call predecessors, (12), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-09-20 20:02:41,928 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-20 20:02:45,236 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:02:45,242 INFO L93 Difference]: Finished difference Result 120 states and 142 transitions. [2024-09-20 20:02:45,243 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2024-09-20 20:02:45,243 INFO L78 Accepts]: Start accepts. Automaton has has 29 states, 23 states have (on average 1.565217391304348) internal successors, (36), 22 states have internal predecessors, (36), 11 states have call successors, (12), 7 states have call predecessors, (12), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) Word has length 30 [2024-09-20 20:02:45,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:02:45,244 INFO L225 Difference]: With dead ends: 120 [2024-09-20 20:02:45,245 INFO L226 Difference]: Without dead ends: 118 [2024-09-20 20:02:45,245 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 29 SyntacticMatches, 3 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 408 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=321, Invalid=2129, Unknown=0, NotChecked=0, Total=2450 [2024-09-20 20:02:45,246 INFO L434 NwaCegarLoop]: 20 mSDtfsCounter, 54 mSDsluCounter, 259 mSDsCounter, 0 mSdLazyCounter, 593 mSolverCounterSat, 23 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 279 SdHoareTripleChecker+Invalid, 617 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 593 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.2s IncrementalHoareTripleChecker+Time [2024-09-20 20:02:45,246 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 279 Invalid, 617 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 593 Invalid, 1 Unknown, 0 Unchecked, 5.2s Time] [2024-09-20 20:02:45,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2024-09-20 20:02:45,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 110. [2024-09-20 20:02:45,284 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 73 states have (on average 1.1643835616438356) internal successors, (85), 79 states have internal predecessors, (85), 18 states have call successors, (18), 15 states have call predecessors, (18), 18 states have return successors, (27), 15 states have call predecessors, (27), 16 states have call successors, (27) [2024-09-20 20:02:45,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 130 transitions. [2024-09-20 20:02:45,289 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 130 transitions. Word has length 30 [2024-09-20 20:02:45,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:02:45,290 INFO L474 AbstractCegarLoop]: Abstraction has 110 states and 130 transitions. [2024-09-20 20:02:45,290 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 29 states, 23 states have (on average 1.565217391304348) internal successors, (36), 22 states have internal predecessors, (36), 11 states have call successors, (12), 7 states have call predecessors, (12), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2024-09-20 20:02:45,290 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:45,290 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 130 transitions. [2024-09-20 20:02:45,291 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-09-20 20:02:45,292 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:02:45,292 INFO L216 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:02:45,305 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-09-20 20:02:45,496 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-20 20:02:45,497 INFO L399 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:02:45,497 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:02:45,497 INFO L85 PathProgramCache]: Analyzing trace with hash -1303652198, now seen corresponding path program 1 times [2024-09-20 20:02:45,497 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:02:45,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1714064071] [2024-09-20 20:02:45,497 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:45,497 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:02:45,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:02:45,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1826861477] [2024-09-20 20:02:45,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:02:45,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:02:45,544 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:02:45,546 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-20 20:02:45,547 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-20 20:02:45,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:02:45,748 WARN L260 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 205 conjuncts are in the unsatisfiable core [2024-09-20 20:02:45,753 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:02:45,759 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-20 20:02:45,762 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-20 20:02:45,785 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-20 20:02:45,789 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 11 [2024-09-20 20:02:45,794 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 11 [2024-09-20 20:02:46,038 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 23 treesize of output 15 [2024-09-20 20:02:46,048 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 45 treesize of output 25 [2024-09-20 20:02:46,102 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 108 treesize of output 80 [2024-09-20 20:02:46,105 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 76 [2024-09-20 20:02:46,113 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 13 [2024-09-20 20:02:46,117 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 40 treesize of output 24 [2024-09-20 20:02:46,587 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-20 20:02:46,593 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 117 treesize of output 87 [2024-09-20 20:02:46,598 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 87 treesize of output 81 [2024-09-20 20:02:46,622 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 13 [2024-09-20 20:02:46,822 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-20 20:02:46,826 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-20 20:02:46,829 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-20 20:02:46,836 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-20 20:02:46,840 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 61 treesize of output 37 [2024-09-20 20:02:47,596 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-20 20:02:47,597 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:03:03,215 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-20 20:03:03,215 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:03:03,215 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1714064071] [2024-09-20 20:03:03,215 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:03:03,215 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1826861477] [2024-09-20 20:03:03,215 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1826861477] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-20 20:03:03,215 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-20 20:03:03,215 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 18] total 38 [2024-09-20 20:03:03,216 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [600946467] [2024-09-20 20:03:03,216 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-20 20:03:03,216 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 38 states [2024-09-20 20:03:03,216 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:03:03,216 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2024-09-20 20:03:03,217 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=162, Invalid=1244, Unknown=0, NotChecked=0, Total=1406 [2024-09-20 20:03:03,217 INFO L87 Difference]: Start difference. First operand 110 states and 130 transitions. Second operand has 38 states, 33 states have (on average 1.5454545454545454) internal successors, (51), 30 states have internal predecessors, (51), 12 states have call successors, (16), 10 states have call predecessors, (16), 4 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-09-20 20:03:21,016 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.10s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-09-20 20:03:54,000 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.10s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-09-20 20:04:01,961 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.60s for a HTC check with result VALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-09-20 20:04:07,208 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:04:07,208 INFO L93 Difference]: Finished difference Result 212 states and 260 transitions. [2024-09-20 20:04:07,210 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2024-09-20 20:04:07,211 INFO L78 Accepts]: Start accepts. Automaton has has 38 states, 33 states have (on average 1.5454545454545454) internal successors, (51), 30 states have internal predecessors, (51), 12 states have call successors, (16), 10 states have call predecessors, (16), 4 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 42 [2024-09-20 20:04:07,211 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:04:07,214 INFO L225 Difference]: With dead ends: 212 [2024-09-20 20:04:07,214 INFO L226 Difference]: Without dead ends: 208 [2024-09-20 20:04:07,215 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 44 SyntacticMatches, 4 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1229 ImplicationChecksByTransitivity, 61.1s TimeCoverageRelationStatistics Valid=743, Invalid=4957, Unknown=0, NotChecked=0, Total=5700 [2024-09-20 20:04:07,216 INFO L434 NwaCegarLoop]: 21 mSDtfsCounter, 138 mSDsluCounter, 321 mSDsCounter, 0 mSdLazyCounter, 1000 mSolverCounterSat, 59 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 17.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 139 SdHoareTripleChecker+Valid, 342 SdHoareTripleChecker+Invalid, 1060 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 59 IncrementalHoareTripleChecker+Valid, 1000 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 17.1s IncrementalHoareTripleChecker+Time [2024-09-20 20:04:07,216 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [139 Valid, 342 Invalid, 1060 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [59 Valid, 1000 Invalid, 1 Unknown, 0 Unchecked, 17.1s Time] [2024-09-20 20:04:07,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2024-09-20 20:04:07,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 199. [2024-09-20 20:04:07,329 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 199 states, 134 states have (on average 1.1865671641791045) internal successors, (159), 145 states have internal predecessors, (159), 31 states have call successors, (31), 25 states have call predecessors, (31), 33 states have return successors, (58), 28 states have call predecessors, (58), 28 states have call successors, (58) [2024-09-20 20:04:07,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 248 transitions. [2024-09-20 20:04:07,333 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 248 transitions. Word has length 42 [2024-09-20 20:04:07,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:04:07,333 INFO L474 AbstractCegarLoop]: Abstraction has 199 states and 248 transitions. [2024-09-20 20:04:07,334 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 38 states, 33 states have (on average 1.5454545454545454) internal successors, (51), 30 states have internal predecessors, (51), 12 states have call successors, (16), 10 states have call predecessors, (16), 4 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-09-20 20:04:07,334 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:07,334 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 248 transitions. [2024-09-20 20:04:07,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-09-20 20:04:07,335 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:04:07,335 INFO L216 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:04:07,350 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-09-20 20:04:07,535 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-20 20:04:07,536 INFO L399 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:04:07,537 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:07,538 INFO L85 PathProgramCache]: Analyzing trace with hash -1561008742, now seen corresponding path program 2 times [2024-09-20 20:04:07,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:04:07,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [767632305] [2024-09-20 20:04:07,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:04:07,538 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:04:07,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:04:07,566 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [489608196] [2024-09-20 20:04:07,566 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-20 20:04:07,566 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:07,566 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:04:07,568 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-20 20:04:07,568 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-20 20:04:07,896 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-20 20:04:07,896 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-20 20:04:07,900 WARN L260 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 202 conjuncts are in the unsatisfiable core [2024-09-20 20:04:07,904 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:04:07,908 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-20 20:04:07,910 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-20 20:04:07,932 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-20 20:04:07,936 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 11 [2024-09-20 20:04:07,940 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 11 [2024-09-20 20:04:08,175 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 29 treesize of output 17 [2024-09-20 20:04:08,180 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 105 treesize of output 77 [2024-09-20 20:04:08,183 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 77 treesize of output 73 [2024-09-20 20:04:08,514 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 23 treesize of output 15 [2024-09-20 20:04:08,522 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 47 treesize of output 27 [2024-09-20 20:04:08,581 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-20 20:04:08,591 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 99 treesize of output 73 [2024-09-20 20:04:08,599 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 73 treesize of output 71 [2024-09-20 20:04:08,759 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 25 treesize of output 17 [2024-09-20 20:04:08,761 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 29 [2024-09-20 20:04:08,771 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 22 [2024-09-20 20:04:08,774 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 30 treesize of output 18 [2024-09-20 20:04:08,779 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-20 20:04:08,904 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-09-20 20:04:08,905 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:04:17,838 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 10 proven. 8 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-20 20:04:17,838 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:04:17,839 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [767632305] [2024-09-20 20:04:17,839 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:04:17,842 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [489608196] [2024-09-20 20:04:17,842 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [489608196] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-20 20:04:17,842 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-09-20 20:04:17,842 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 17] total 36 [2024-09-20 20:04:17,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1605060460] [2024-09-20 20:04:17,842 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-09-20 20:04:17,843 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2024-09-20 20:04:17,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:04:17,843 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2024-09-20 20:04:17,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=1113, Unknown=0, NotChecked=0, Total=1260 [2024-09-20 20:04:17,844 INFO L87 Difference]: Start difference. First operand 199 states and 248 transitions. Second operand has 36 states, 31 states have (on average 1.6451612903225807) internal successors, (51), 28 states have internal predecessors, (51), 12 states have call successors, (16), 10 states have call predecessors, (16), 4 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-09-20 20:04:36,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:04:36,068 INFO L93 Difference]: Finished difference Result 281 states and 353 transitions. [2024-09-20 20:04:36,069 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2024-09-20 20:04:36,069 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 31 states have (on average 1.6451612903225807) internal successors, (51), 28 states have internal predecessors, (51), 12 states have call successors, (16), 10 states have call predecessors, (16), 4 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) Word has length 42 [2024-09-20 20:04:36,069 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:04:36,073 INFO L225 Difference]: With dead ends: 281 [2024-09-20 20:04:36,073 INFO L226 Difference]: Without dead ends: 269 [2024-09-20 20:04:36,074 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 45 SyntacticMatches, 4 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 690 ImplicationChecksByTransitivity, 21.2s TimeCoverageRelationStatistics Valid=473, Invalid=3309, Unknown=0, NotChecked=0, Total=3782 [2024-09-20 20:04:36,074 INFO L434 NwaCegarLoop]: 23 mSDtfsCounter, 75 mSDsluCounter, 354 mSDsCounter, 0 mSdLazyCounter, 995 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 76 SdHoareTripleChecker+Valid, 377 SdHoareTripleChecker+Invalid, 1017 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 995 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.0s IncrementalHoareTripleChecker+Time [2024-09-20 20:04:36,076 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [76 Valid, 377 Invalid, 1017 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 995 Invalid, 0 Unknown, 0 Unchecked, 5.0s Time] [2024-09-20 20:04:36,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states. [2024-09-20 20:04:36,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 260. [2024-09-20 20:04:36,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 260 states, 176 states have (on average 1.1875) internal successors, (209), 191 states have internal predecessors, (209), 41 states have call successors, (41), 32 states have call predecessors, (41), 42 states have return successors, (80), 36 states have call predecessors, (80), 38 states have call successors, (80) [2024-09-20 20:04:36,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 260 states to 260 states and 330 transitions. [2024-09-20 20:04:36,176 INFO L78 Accepts]: Start accepts. Automaton has 260 states and 330 transitions. Word has length 42 [2024-09-20 20:04:36,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:04:36,179 INFO L474 AbstractCegarLoop]: Abstraction has 260 states and 330 transitions. [2024-09-20 20:04:36,179 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 31 states have (on average 1.6451612903225807) internal successors, (51), 28 states have internal predecessors, (51), 12 states have call successors, (16), 10 states have call predecessors, (16), 4 states have return successors, (7), 6 states have call predecessors, (7), 6 states have call successors, (7) [2024-09-20 20:04:36,179 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:36,182 INFO L276 IsEmpty]: Start isEmpty. Operand 260 states and 330 transitions. [2024-09-20 20:04:36,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-09-20 20:04:36,184 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:04:36,184 INFO L216 NwaCegarLoop]: trace histogram [3, 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-20 20:04:36,193 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-09-20 20:04:36,384 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable6 [2024-09-20 20:04:36,387 INFO L399 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:04:36,388 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:36,388 INFO L85 PathProgramCache]: Analyzing trace with hash 549162052, now seen corresponding path program 1 times [2024-09-20 20:04:36,388 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:04:36,388 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1336392196] [2024-09-20 20:04:36,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:04:36,388 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:04:36,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:04:36,421 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [666901371] [2024-09-20 20:04:36,421 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:04:36,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:36,421 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:04:36,424 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-20 20:04:36,425 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-20 20:04:36,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:36,516 INFO L262 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 90 conjuncts are in the unsatisfiable core [2024-09-20 20:04:36,519 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:04:36,524 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-20 20:04:36,544 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-20 20:04:36,547 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 11 [2024-09-20 20:04:36,566 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 11 [2024-09-20 20:04:36,585 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-20 20:04:36,593 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-20 20:04:37,147 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 47 treesize of output 31 [2024-09-20 20:04:37,150 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 24 [2024-09-20 20:04:37,157 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-20 20:04:37,159 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 23 treesize of output 15 [2024-09-20 20:04:37,198 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-20 20:04:37,199 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 15 treesize of output 7 [2024-09-20 20:04:37,210 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:04:37,210 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 31 [2024-09-20 20:04:37,274 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-09-20 20:04:37,274 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:04:37,946 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:04:37,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1336392196] [2024-09-20 20:04:37,946 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:04:37,946 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [666901371] [2024-09-20 20:04:37,946 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [666901371] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-20 20:04:37,946 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-20 20:04:37,946 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2024-09-20 20:04:37,947 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [499094035] [2024-09-20 20:04:37,947 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-20 20:04:37,947 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2024-09-20 20:04:37,947 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:04:37,948 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-09-20 20:04:37,948 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=770, Unknown=0, NotChecked=0, Total=870 [2024-09-20 20:04:37,948 INFO L87 Difference]: Start difference. First operand 260 states and 330 transitions. Second operand has 23 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 18 states have internal predecessors, (25), 7 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-09-20 20:04:41,968 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-20 20:04:42,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:04:42,616 INFO L93 Difference]: Finished difference Result 270 states and 343 transitions. [2024-09-20 20:04:42,616 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-09-20 20:04:42,616 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 18 states have internal predecessors, (25), 7 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 42 [2024-09-20 20:04:42,616 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:04:42,618 INFO L225 Difference]: With dead ends: 270 [2024-09-20 20:04:42,618 INFO L226 Difference]: Without dead ends: 260 [2024-09-20 20:04:42,618 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 301 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=143, Invalid=1117, Unknown=0, NotChecked=0, Total=1260 [2024-09-20 20:04:42,619 INFO L434 NwaCegarLoop]: 14 mSDtfsCounter, 27 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 410 mSolverCounterSat, 13 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 424 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 410 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.4s IncrementalHoareTripleChecker+Time [2024-09-20 20:04:42,619 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 102 Invalid, 424 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 410 Invalid, 1 Unknown, 0 Unchecked, 4.4s Time] [2024-09-20 20:04:42,619 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 260 states. [2024-09-20 20:04:42,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 260 to 256. [2024-09-20 20:04:42,712 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 173 states have (on average 1.1849710982658959) internal successors, (205), 189 states have internal predecessors, (205), 41 states have call successors, (41), 31 states have call predecessors, (41), 41 states have return successors, (83), 35 states have call predecessors, (83), 39 states have call successors, (83) [2024-09-20 20:04:42,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 329 transitions. [2024-09-20 20:04:42,713 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 329 transitions. Word has length 42 [2024-09-20 20:04:42,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:04:42,714 INFO L474 AbstractCegarLoop]: Abstraction has 256 states and 329 transitions. [2024-09-20 20:04:42,714 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 18 states have internal predecessors, (25), 7 states have call successors, (8), 5 states have call predecessors, (8), 5 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2024-09-20 20:04:42,714 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:42,714 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 329 transitions. [2024-09-20 20:04:42,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-09-20 20:04:42,716 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:04:42,716 INFO L216 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:04:42,729 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-20 20:04:42,920 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:42,921 INFO L399 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:04:42,921 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:42,921 INFO L85 PathProgramCache]: Analyzing trace with hash 953923471, now seen corresponding path program 2 times [2024-09-20 20:04:42,921 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:04:42,921 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1185625421] [2024-09-20 20:04:42,922 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:04:42,922 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:04:42,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:04:42,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [923499382] [2024-09-20 20:04:42,960 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-20 20:04:42,960 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:42,960 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:04:42,961 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-20 20:04:42,962 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-20 20:04:43,093 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-20 20:04:43,093 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-20 20:04:43,096 INFO L262 TraceCheckSpWp]: Trace formula consists of 393 conjuncts, 139 conjuncts are in the unsatisfiable core [2024-09-20 20:04:43,100 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:04:43,105 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-20 20:04:43,126 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 11 [2024-09-20 20:04:43,130 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 11 [2024-09-20 20:04:43,135 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-20 20:04:43,156 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-20 20:04:43,159 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-20 20:04:44,217 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 29 treesize of output 21 [2024-09-20 20:04:44,220 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2024-09-20 20:04:44,224 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 64 treesize of output 46 [2024-09-20 20:04:44,227 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 37 [2024-09-20 20:04:44,289 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:04:44,289 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 52 treesize of output 44 [2024-09-20 20:04:44,300 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-20 20:04:44,303 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-20 20:04:44,379 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 2 proven. 24 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-09-20 20:04:44,379 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:04:46,322 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:04:46,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1185625421] [2024-09-20 20:04:46,322 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:04:46,322 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [923499382] [2024-09-20 20:04:46,322 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [923499382] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-20 20:04:46,322 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-20 20:04:46,323 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2024-09-20 20:04:46,323 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1437620525] [2024-09-20 20:04:46,323 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-20 20:04:46,324 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-09-20 20:04:46,324 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:04:46,324 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-09-20 20:04:46,324 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=1005, Unknown=0, NotChecked=0, Total=1122 [2024-09-20 20:04:46,325 INFO L87 Difference]: Start difference. First operand 256 states and 329 transitions. Second operand has 27 states, 22 states have (on average 1.3636363636363635) internal successors, (30), 22 states have internal predecessors, (30), 8 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-09-20 20:04:50,346 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-20 20:04:51,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:04:51,324 INFO L93 Difference]: Finished difference Result 270 states and 360 transitions. [2024-09-20 20:04:51,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-09-20 20:04:51,325 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 22 states have (on average 1.3636363636363635) internal successors, (30), 22 states have internal predecessors, (30), 8 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 56 [2024-09-20 20:04:51,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:04:51,327 INFO L225 Difference]: With dead ends: 270 [2024-09-20 20:04:51,327 INFO L226 Difference]: Without dead ends: 258 [2024-09-20 20:04:51,328 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 414 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=161, Invalid=1399, Unknown=0, NotChecked=0, Total=1560 [2024-09-20 20:04:51,328 INFO L434 NwaCegarLoop]: 15 mSDtfsCounter, 21 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 581 mSolverCounterSat, 8 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 590 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 581 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2024-09-20 20:04:51,328 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [24 Valid, 137 Invalid, 590 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 581 Invalid, 1 Unknown, 0 Unchecked, 4.6s Time] [2024-09-20 20:04:51,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 258 states. [2024-09-20 20:04:51,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 258 to 256. [2024-09-20 20:04:51,435 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 173 states have (on average 1.1791907514450868) internal successors, (204), 188 states have internal predecessors, (204), 41 states have call successors, (41), 31 states have call predecessors, (41), 41 states have return successors, (100), 36 states have call predecessors, (100), 39 states have call successors, (100) [2024-09-20 20:04:51,437 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 345 transitions. [2024-09-20 20:04:51,437 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 345 transitions. Word has length 56 [2024-09-20 20:04:51,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:04:51,438 INFO L474 AbstractCegarLoop]: Abstraction has 256 states and 345 transitions. [2024-09-20 20:04:51,438 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 22 states have (on average 1.3636363636363635) internal successors, (30), 22 states have internal predecessors, (30), 8 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-09-20 20:04:51,438 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:51,438 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 345 transitions. [2024-09-20 20:04:51,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-09-20 20:04:51,439 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:04:51,439 INFO L216 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:04:51,461 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-09-20 20:04:51,639 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:51,640 INFO L399 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:04:51,640 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:51,640 INFO L85 PathProgramCache]: Analyzing trace with hash -851514863, now seen corresponding path program 1 times [2024-09-20 20:04:51,640 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:04:51,640 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [451990821] [2024-09-20 20:04:51,640 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:04:51,640 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:04:51,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,254 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-20 20:04:52,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,256 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-20 20:04:52,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,263 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-20 20:04:52,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,573 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-20 20:04:52,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,575 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-20 20:04:52,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,816 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-20 20:04:52,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,820 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-20 20:04:52,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,881 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-20 20:04:52,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,885 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 22 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-09-20 20:04:52,885 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:04:52,885 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [451990821] [2024-09-20 20:04:52,886 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [451990821] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-20 20:04:52,886 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [196071841] [2024-09-20 20:04:52,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:04:52,886 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:52,886 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:04:52,887 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-20 20:04:52,888 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-20 20:04:52,982 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:04:52,983 INFO L262 TraceCheckSpWp]: Trace formula consists of 384 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-09-20 20:04:52,987 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:04:53,024 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 13 [2024-09-20 20:04:53,028 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 13 [2024-09-20 20:04:53,361 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 20 proven. 6 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-09-20 20:04:53,362 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:04:54,105 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 22 proven. 8 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-09-20 20:04:54,106 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [196071841] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-20 20:04:54,106 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-20 20:04:54,106 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14, 16] total 36 [2024-09-20 20:04:54,106 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [268781723] [2024-09-20 20:04:54,106 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-20 20:04:54,107 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 36 states [2024-09-20 20:04:54,108 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:04:54,110 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2024-09-20 20:04:54,110 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=198, Invalid=1062, Unknown=0, NotChecked=0, Total=1260 [2024-09-20 20:04:54,111 INFO L87 Difference]: Start difference. First operand 256 states and 345 transitions. Second operand has 36 states, 33 states have (on average 1.7878787878787878) internal successors, (59), 32 states have internal predecessors, (59), 10 states have call successors, (17), 6 states have call predecessors, (17), 7 states have return successors, (13), 8 states have call predecessors, (13), 9 states have call successors, (13) [2024-09-20 20:04:54,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:04:54,784 INFO L93 Difference]: Finished difference Result 278 states and 461 transitions. [2024-09-20 20:04:54,784 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-09-20 20:04:54,784 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 33 states have (on average 1.7878787878787878) internal successors, (59), 32 states have internal predecessors, (59), 10 states have call successors, (17), 6 states have call predecessors, (17), 7 states have return successors, (13), 8 states have call predecessors, (13), 9 states have call successors, (13) Word has length 56 [2024-09-20 20:04:54,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:04:54,786 INFO L225 Difference]: With dead ends: 278 [2024-09-20 20:04:54,786 INFO L226 Difference]: Without dead ends: 248 [2024-09-20 20:04:54,787 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 105 SyntacticMatches, 3 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 560 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=368, Invalid=1702, Unknown=0, NotChecked=0, Total=2070 [2024-09-20 20:04:54,787 INFO L434 NwaCegarLoop]: 14 mSDtfsCounter, 56 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 545 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 57 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 594 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 545 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-09-20 20:04:54,788 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [57 Valid, 99 Invalid, 594 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 545 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-09-20 20:04:54,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2024-09-20 20:04:54,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 242. [2024-09-20 20:04:54,902 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 242 states, 166 states have (on average 1.1566265060240963) internal successors, (192), 176 states have internal predecessors, (192), 41 states have call successors, (41), 31 states have call predecessors, (41), 34 states have return successors, (93), 34 states have call predecessors, (93), 39 states have call successors, (93) [2024-09-20 20:04:54,903 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 242 states to 242 states and 326 transitions. [2024-09-20 20:04:54,904 INFO L78 Accepts]: Start accepts. Automaton has 242 states and 326 transitions. Word has length 56 [2024-09-20 20:04:54,904 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:04:54,904 INFO L474 AbstractCegarLoop]: Abstraction has 242 states and 326 transitions. [2024-09-20 20:04:54,904 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 36 states, 33 states have (on average 1.7878787878787878) internal successors, (59), 32 states have internal predecessors, (59), 10 states have call successors, (17), 6 states have call predecessors, (17), 7 states have return successors, (13), 8 states have call predecessors, (13), 9 states have call successors, (13) [2024-09-20 20:04:54,904 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:54,905 INFO L276 IsEmpty]: Start isEmpty. Operand 242 states and 326 transitions. [2024-09-20 20:04:54,906 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-09-20 20:04:54,906 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:04:54,906 INFO L216 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:04:54,918 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-09-20 20:04:55,110 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,9 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:55,111 INFO L399 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:04:55,111 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:04:55,112 INFO L85 PathProgramCache]: Analyzing trace with hash 109917969, now seen corresponding path program 2 times [2024-09-20 20:04:55,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:04:55,112 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1587073930] [2024-09-20 20:04:55,112 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:04:55,112 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:04:55,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:04:55,143 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [641766921] [2024-09-20 20:04:55,143 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-09-20 20:04:55,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:04:55,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:04:55,147 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-20 20:04:55,148 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-20 20:04:55,278 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-09-20 20:04:55,279 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-20 20:04:55,281 INFO L262 TraceCheckSpWp]: Trace formula consists of 384 conjuncts, 133 conjuncts are in the unsatisfiable core [2024-09-20 20:04:55,285 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:04:55,290 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-20 20:04:55,310 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-20 20:04:55,313 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 11 [2024-09-20 20:04:55,319 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 11 [2024-09-20 20:04:55,337 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-20 20:04:55,344 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-20 20:04:56,363 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 61 treesize of output 43 [2024-09-20 20:04:56,366 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 43 treesize of output 34 [2024-09-20 20:04:56,378 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 29 treesize of output 21 [2024-09-20 20:04:56,381 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 17 [2024-09-20 20:04:56,430 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-20 20:04:56,431 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-20 20:04:56,439 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:04:56,439 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 49 treesize of output 41 [2024-09-20 20:04:56,534 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 2 proven. 24 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-09-20 20:04:56,534 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:04:58,103 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:04:58,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1587073930] [2024-09-20 20:04:58,104 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-09-20 20:04:58,104 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [641766921] [2024-09-20 20:04:58,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [641766921] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-20 20:04:58,104 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-09-20 20:04:58,104 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2024-09-20 20:04:58,104 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [559390671] [2024-09-20 20:04:58,104 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-09-20 20:04:58,104 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-09-20 20:04:58,104 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:04:58,105 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-09-20 20:04:58,105 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=1003, Unknown=0, NotChecked=0, Total=1122 [2024-09-20 20:04:58,106 INFO L87 Difference]: Start difference. First operand 242 states and 326 transitions. Second operand has 27 states, 22 states have (on average 1.3636363636363635) internal successors, (30), 22 states have internal predecessors, (30), 8 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-09-20 20:05:02,165 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-20 20:05:03,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:05:03,131 INFO L93 Difference]: Finished difference Result 252 states and 353 transitions. [2024-09-20 20:05:03,132 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-09-20 20:05:03,132 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 22 states have (on average 1.3636363636363635) internal successors, (30), 22 states have internal predecessors, (30), 8 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Word has length 56 [2024-09-20 20:05:03,132 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:05:03,134 INFO L225 Difference]: With dead ends: 252 [2024-09-20 20:05:03,134 INFO L226 Difference]: Without dead ends: 240 [2024-09-20 20:05:03,134 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 397 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=163, Invalid=1397, Unknown=0, NotChecked=0, Total=1560 [2024-09-20 20:05:03,135 INFO L434 NwaCegarLoop]: 17 mSDtfsCounter, 21 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 682 mSolverCounterSat, 11 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 694 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 682 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.7s IncrementalHoareTripleChecker+Time [2024-09-20 20:05:03,135 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 157 Invalid, 694 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 682 Invalid, 1 Unknown, 0 Unchecked, 4.7s Time] [2024-09-20 20:05:03,135 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 240 states. [2024-09-20 20:05:03,235 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 240 to 238. [2024-09-20 20:05:03,236 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 238 states, 164 states have (on average 1.1524390243902438) internal successors, (189), 173 states have internal predecessors, (189), 41 states have call successors, (41), 31 states have call predecessors, (41), 32 states have return successors, (91), 33 states have call predecessors, (91), 39 states have call successors, (91) [2024-09-20 20:05:03,237 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 238 states to 238 states and 321 transitions. [2024-09-20 20:05:03,237 INFO L78 Accepts]: Start accepts. Automaton has 238 states and 321 transitions. Word has length 56 [2024-09-20 20:05:03,237 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:05:03,237 INFO L474 AbstractCegarLoop]: Abstraction has 238 states and 321 transitions. [2024-09-20 20:05:03,238 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 22 states have (on average 1.3636363636363635) internal successors, (30), 22 states have internal predecessors, (30), 8 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2024-09-20 20:05:03,238 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:05:03,238 INFO L276 IsEmpty]: Start isEmpty. Operand 238 states and 321 transitions. [2024-09-20 20:05:03,238 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2024-09-20 20:05:03,238 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:05:03,239 INFO L216 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:05:03,251 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-09-20 20:05:03,442 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2024-09-20 20:05:03,443 INFO L399 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:05:03,443 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:05:03,443 INFO L85 PathProgramCache]: Analyzing trace with hash -1695520365, now seen corresponding path program 1 times [2024-09-20 20:05:03,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:05:03,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2118312037] [2024-09-20 20:05:03,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:05:03,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:05:03,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:03,868 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2024-09-20 20:05:03,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:03,871 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2024-09-20 20:05:03,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:03,903 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-20 20:05:03,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:04,284 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-20 20:05:04,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:04,287 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-20 20:05:04,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:04,455 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-20 20:05:04,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:04,457 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 11 [2024-09-20 20:05:04,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:04,506 INFO L381 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-09-20 20:05:04,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:04,509 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-09-20 20:05:04,510 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-09-20 20:05:04,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2118312037] [2024-09-20 20:05:04,510 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2118312037] provided 0 perfect and 1 imperfect interpolant sequences [2024-09-20 20:05:04,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [486197678] [2024-09-20 20:05:04,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:05:04,510 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:05:04,510 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:05:04,511 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-20 20:05:04,513 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-20 20:05:04,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-09-20 20:05:04,623 INFO L262 TraceCheckSpWp]: Trace formula consists of 375 conjuncts, 59 conjuncts are in the unsatisfiable core [2024-09-20 20:05:04,625 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:05:04,637 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-20 20:05:04,640 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-09-20 20:05:05,197 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-09-20 20:05:05,198 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2024-09-20 20:05:07,516 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 24 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-09-20 20:05:07,517 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [486197678] provided 0 perfect and 2 imperfect interpolant sequences [2024-09-20 20:05:07,517 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-09-20 20:05:07,517 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 20, 24] total 48 [2024-09-20 20:05:07,517 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [846537807] [2024-09-20 20:05:07,517 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-09-20 20:05:07,518 INFO L551 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2024-09-20 20:05:07,518 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-09-20 20:05:07,519 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2024-09-20 20:05:07,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=279, Invalid=1977, Unknown=0, NotChecked=0, Total=2256 [2024-09-20 20:05:07,519 INFO L87 Difference]: Start difference. First operand 238 states and 321 transitions. Second operand has 48 states, 38 states have (on average 1.5526315789473684) internal successors, (59), 41 states have internal predecessors, (59), 16 states have call successors, (18), 7 states have call predecessors, (18), 10 states have return successors, (16), 13 states have call predecessors, (16), 15 states have call successors, (16) [2024-09-20 20:05:08,951 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-09-20 20:05:08,951 INFO L93 Difference]: Finished difference Result 250 states and 340 transitions. [2024-09-20 20:05:08,952 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-09-20 20:05:08,952 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 38 states have (on average 1.5526315789473684) internal successors, (59), 41 states have internal predecessors, (59), 16 states have call successors, (18), 7 states have call predecessors, (18), 10 states have return successors, (16), 13 states have call predecessors, (16), 15 states have call successors, (16) Word has length 56 [2024-09-20 20:05:08,952 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-09-20 20:05:08,953 INFO L225 Difference]: With dead ends: 250 [2024-09-20 20:05:08,954 INFO L226 Difference]: Without dead ends: 226 [2024-09-20 20:05:08,955 INFO L433 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 96 SyntacticMatches, 1 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1126 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=506, Invalid=3400, Unknown=0, NotChecked=0, Total=3906 [2024-09-20 20:05:08,955 INFO L434 NwaCegarLoop]: 14 mSDtfsCounter, 46 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 677 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 102 SdHoareTripleChecker+Invalid, 716 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 677 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2024-09-20 20:05:08,955 INFO L435 NwaCegarLoop]: SdHoareTripleChecker [46 Valid, 102 Invalid, 716 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 677 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2024-09-20 20:05:08,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2024-09-20 20:05:09,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 224. [2024-09-20 20:05:09,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 224 states, 156 states have (on average 1.1474358974358974) internal successors, (179), 164 states have internal predecessors, (179), 41 states have call successors, (41), 31 states have call predecessors, (41), 26 states have return successors, (79), 28 states have call predecessors, (79), 39 states have call successors, (79) [2024-09-20 20:05:09,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 224 states to 224 states and 299 transitions. [2024-09-20 20:05:09,058 INFO L78 Accepts]: Start accepts. Automaton has 224 states and 299 transitions. Word has length 56 [2024-09-20 20:05:09,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-09-20 20:05:09,059 INFO L474 AbstractCegarLoop]: Abstraction has 224 states and 299 transitions. [2024-09-20 20:05:09,059 INFO L475 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 38 states have (on average 1.5526315789473684) internal successors, (59), 41 states have internal predecessors, (59), 16 states have call successors, (18), 7 states have call predecessors, (18), 10 states have return successors, (16), 13 states have call predecessors, (16), 15 states have call successors, (16) [2024-09-20 20:05:09,059 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:05:09,059 INFO L276 IsEmpty]: Start isEmpty. Operand 224 states and 299 transitions. [2024-09-20 20:05:09,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2024-09-20 20:05:09,060 INFO L208 NwaCegarLoop]: Found error trace [2024-09-20 20:05:09,060 INFO L216 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-09-20 20:05:09,074 INFO L552 MonitoredProcess]: [MP /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-09-20 20:05:09,264 WARN L456 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/certificate-witnesses-artifact/automizer/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2024-09-20 20:05:09,265 INFO L399 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-09-20 20:05:09,265 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2024-09-20 20:05:09,265 INFO L85 PathProgramCache]: Analyzing trace with hash 1850912182, now seen corresponding path program 3 times [2024-09-20 20:05:09,265 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-09-20 20:05:09,265 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [872896064] [2024-09-20 20:05:09,265 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-09-20 20:05:09,265 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-09-20 20:05:09,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-09-20 20:05:09,309 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [904043318] [2024-09-20 20:05:09,309 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-09-20 20:05:09,309 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-09-20 20:05:09,310 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/certificate-witnesses-artifact/automizer/z3 [2024-09-20 20:05:09,312 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-20 20:05:09,320 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-20 20:05:09,558 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-09-20 20:05:09,559 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-09-20 20:05:09,563 INFO L262 TraceCheckSpWp]: Trace formula consists of 438 conjuncts, 182 conjuncts are in the unsatisfiable core [2024-09-20 20:05:09,568 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2024-09-20 20:05:09,584 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 13 [2024-09-20 20:05:09,593 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 13 [2024-09-20 20:05:09,843 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 47 treesize of output 35 [2024-09-20 20:05:09,877 INFO L349 Elim1Store]: treesize reduction 18, result has 60.9 percent of original size [2024-09-20 20:05:09,878 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 83 treesize of output 82 [2024-09-20 20:05:31,859 INFO L349 Elim1Store]: treesize reduction 18, result has 60.9 percent of original size [2024-09-20 20:05:31,860 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 154 treesize of output 141 [2024-09-20 20:05:31,967 INFO L349 Elim1Store]: treesize reduction 12, result has 60.0 percent of original size [2024-09-20 20:05:31,967 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 239 treesize of output 218 [2024-09-20 20:05:32,163 INFO L349 Elim1Store]: treesize reduction 35, result has 34.0 percent of original size [2024-09-20 20:05:32,164 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 272 treesize of output 275 [2024-09-20 20:05:32,279 INFO L349 Elim1Store]: treesize reduction 16, result has 55.6 percent of original size [2024-09-20 20:05:32,279 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 180 treesize of output 175 [2024-09-20 20:05:50,579 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:05:50,580 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 10 select indices, 10 select index equivalence classes, 0 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 45 case distinctions, treesize of input 2075 treesize of output 2387 [2024-09-20 20:05:53,586 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:05:53,587 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 13 select indices, 13 select index equivalence classes, 0 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 78 case distinctions, treesize of input 1875 treesize of output 2739 [2024-09-20 20:05:55,052 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:05:55,053 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 13 select indices, 13 select index equivalence classes, 0 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 78 case distinctions, treesize of input 1807 treesize of output 2671 [2024-09-20 20:05:56,750 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:05:56,751 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 13 select indices, 13 select index equivalence classes, 0 disjoint index pairs (out of 78 index pairs), introduced 13 new quantified variables, introduced 78 case distinctions, treesize of input 1739 treesize of output 2603 [2024-09-20 20:05:57,996 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-09-20 20:05:57,997 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 9 select indices, 9 select index equivalence classes, 0 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 36 case distinctions, treesize of input 1693 treesize of output 1965