./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/ldv-consumption/linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/ldv-consumption/linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-64bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E --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 Taipan --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 3aefe7c24f7dbfd113682bd81b91ef3b049ad438c933de49acd0f78d1e093848 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 02:42:02,351 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 02:42:02,457 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-64bit-Taipan_Default.epf [2024-11-14 02:42:02,470 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 02:42:02,470 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 02:42:02,496 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 02:42:02,497 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 02:42:02,497 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 02:42:02,498 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 02:42:02,498 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 02:42:02,498 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 02:42:02,498 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 02:42:02,499 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 02:42:02,499 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 02:42:02,499 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 02:42:02,499 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 02:42:02,499 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 02:42:02,499 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 02:42:02,499 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 02:42:02,500 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 02:42:02,500 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 02:42:02,500 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 02:42:02,500 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 02:42:02,501 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 02:42:02,501 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 02:42:02,501 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 02:42:02,501 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 02:42:02,501 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 02:42:02,501 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 02:42:02,502 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 02:42:02,502 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 02:42:02,502 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 02:42:02,502 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 02:42:02,502 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 02:42:02,502 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 02:42:02,503 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:42:02,503 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 02:42:02,503 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 02:42:02,503 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 02:42:02,503 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 02:42:02,503 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 02:42:02,504 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 02:42:02,504 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 02:42:02,504 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 02:42:02,504 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES 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 -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E 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 -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 3aefe7c24f7dbfd113682bd81b91ef3b049ad438c933de49acd0f78d1e093848 [2024-11-14 02:42:02,872 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 02:42:02,885 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 02:42:02,891 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 02:42:02,893 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 02:42:02,893 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 02:42:02,895 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/ldv-consumption/linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i Unable to find full path for "g++" [2024-11-14 02:42:05,001 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 02:42:05,573 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 02:42:05,577 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/sv-benchmarks/c/ldv-consumption/linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i [2024-11-14 02:42:05,616 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/data/61c6c65c8/37b3179d3ac047b084cff76b0fdc58a6/FLAGaf5abab55 [2024-11-14 02:42:05,631 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/data/61c6c65c8/37b3179d3ac047b084cff76b0fdc58a6 [2024-11-14 02:42:05,634 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 02:42:05,636 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 02:42:05,638 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:05,638 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 02:42:05,642 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 02:42:05,644 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:05" (1/1) ... [2024-11-14 02:42:05,647 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7b1d24b1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:05, skipping insertion in model container [2024-11-14 02:42:05,647 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 02:42:05" (1/1) ... [2024-11-14 02:42:05,751 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 02:42:07,029 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/sv-benchmarks/c/ldv-consumption/linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i[133672,133685] [2024-11-14 02:42:07,128 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:07,148 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 02:42:07,324 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ volatile (".pushsection .smp_locks,\"a\"\n.balign 4\n.long 671f - .\n.popsection\n671:\n\tlock; bts %1,%0": "+m" (*((long volatile *)addr)): "Ir" (nr): "memory"); [3073] [2024-11-14 02:42:07,326 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ volatile ("bt %2,%1\n\tsbb %0,%0": "=r" (oldbit): "m" (*((unsigned long *)addr)), "Ir" (nr)); [3087-3088] [2024-11-14 02:42:07,327 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movb %%gs:%P1,%0": "=q" (pfo_ret__): "p" (& current_task)); [3102] [2024-11-14 02:42:07,327 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movw %%gs:%P1,%0": "=r" (pfo_ret__): "p" (& current_task)); [3105] [2024-11-14 02:42:07,327 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movl %%gs:%P1,%0": "=r" (pfo_ret__): "p" (& current_task)); [3108] [2024-11-14 02:42:07,328 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movq %%gs:%P1,%0": "=r" (pfo_ret__): "p" (& current_task)); [3111] [2024-11-14 02:42:07,330 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movb %%gs:%P1,%0": "=q" (pfo_ret__): "p" (& kernel_stack)); [3173] [2024-11-14 02:42:07,331 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movw %%gs:%P1,%0": "=r" (pfo_ret__): "p" (& kernel_stack)); [3176] [2024-11-14 02:42:07,332 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movl %%gs:%P1,%0": "=r" (pfo_ret__): "p" (& kernel_stack)); [3179] [2024-11-14 02:42:07,333 WARN L75 lationResultReporter]: Unsoundness Warning: Ignoring inline assembler instruction C: __asm__ ("movq %%gs:%P1,%0": "=r" (pfo_ret__): "p" (& kernel_stack)); [3182] [2024-11-14 02:42:07,463 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/sv-benchmarks/c/ldv-consumption/linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i[133672,133685] [2024-11-14 02:42:07,486 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 02:42:07,560 INFO L204 MainTranslator]: Completed translation [2024-11-14 02:42:07,560 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07 WrapperNode [2024-11-14 02:42:07,561 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 02:42:07,562 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:07,563 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 02:42:07,563 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 02:42:07,570 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,644 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,795 INFO L138 Inliner]: procedures = 191, calls = 833, calls flagged for inlining = 89, calls inlined = 75, statements flattened = 2352 [2024-11-14 02:42:07,795 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 02:42:07,796 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 02:42:07,796 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 02:42:07,797 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 02:42:07,805 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,806 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,829 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,829 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,927 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,949 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,968 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:07,983 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:08,006 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 02:42:08,007 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 02:42:08,009 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 02:42:08,009 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 02:42:08,010 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (1/1) ... [2024-11-14 02:42:08,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 02:42:08,040 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:08,059 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 02:42:08,065 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 02:42:08,096 INFO L130 BoogieDeclarations]: Found specification of procedure write~unchecked~int [2024-11-14 02:42:08,096 INFO L130 BoogieDeclarations]: Found specification of procedure input_event_size [2024-11-14 02:42:08,096 INFO L138 BoogieDeclarations]: Found implementation of procedure input_event_size [2024-11-14 02:42:08,097 INFO L130 BoogieDeclarations]: Found specification of procedure read~unchecked~$Pointer$ [2024-11-14 02:42:08,097 INFO L130 BoogieDeclarations]: Found specification of procedure write~unchecked~$Pointer$ [2024-11-14 02:42:08,097 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2024-11-14 02:42:08,097 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_mutex_lock_interruptible_mutex_of_uinput_device [2024-11-14 02:42:08,097 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_mutex_lock_interruptible_mutex_of_uinput_device [2024-11-14 02:42:08,097 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memcpy [2024-11-14 02:42:08,098 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memcpy [2024-11-14 02:42:08,099 INFO L130 BoogieDeclarations]: Found specification of procedure variable_test_bit [2024-11-14 02:42:08,099 INFO L138 BoogieDeclarations]: Found implementation of procedure variable_test_bit [2024-11-14 02:42:08,099 INFO L130 BoogieDeclarations]: Found specification of procedure get_current [2024-11-14 02:42:08,099 INFO L138 BoogieDeclarations]: Found implementation of procedure get_current [2024-11-14 02:42:08,099 INFO L130 BoogieDeclarations]: Found specification of procedure uinput_request_done [2024-11-14 02:42:08,100 INFO L138 BoogieDeclarations]: Found implementation of procedure uinput_request_done [2024-11-14 02:42:08,100 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_malloc [2024-11-14 02:42:08,100 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_malloc [2024-11-14 02:42:08,101 INFO L130 BoogieDeclarations]: Found specification of procedure constant_test_bit [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure constant_test_bit [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure kfree [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure kfree [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure input_abs_get_flat [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure input_abs_get_flat [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_unlock [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_unlock [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure copy_to_user [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure copy_to_user [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_error [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_error [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure input_alloc_absinfo [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure input_alloc_absinfo [2024-11-14 02:42:08,102 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_check_return_value [2024-11-14 02:42:08,102 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_check_return_value [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure ldv__builtin_expect [2024-11-14 02:42:08,103 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv__builtin_expect [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure uinput_request_find [2024-11-14 02:42:08,103 INFO L138 BoogieDeclarations]: Found implementation of procedure uinput_request_find [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_mutex_unlock_mutex_of_uinput_device [2024-11-14 02:42:08,103 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_mutex_unlock_mutex_of_uinput_device [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure uinput_allocate_device [2024-11-14 02:42:08,103 INFO L138 BoogieDeclarations]: Found implementation of procedure uinput_allocate_device [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure copy_from_user [2024-11-14 02:42:08,103 INFO L138 BoogieDeclarations]: Found implementation of procedure copy_from_user [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure uinput_ioctl_handler [2024-11-14 02:42:08,103 INFO L138 BoogieDeclarations]: Found implementation of procedure uinput_ioctl_handler [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-14 02:42:08,103 INFO L130 BoogieDeclarations]: Found specification of procedure __bad_percpu_size [2024-11-14 02:42:08,103 INFO L138 BoogieDeclarations]: Found implementation of procedure __bad_percpu_size [2024-11-14 02:42:08,104 INFO L130 BoogieDeclarations]: Found specification of procedure uinput_ff_upload_from_user [2024-11-14 02:42:08,104 INFO L138 BoogieDeclarations]: Found implementation of procedure uinput_ff_upload_from_user [2024-11-14 02:42:08,104 INFO L130 BoogieDeclarations]: Found specification of procedure uinput_destroy_device [2024-11-14 02:42:08,104 INFO L138 BoogieDeclarations]: Found implementation of procedure uinput_destroy_device [2024-11-14 02:42:08,104 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2024-11-14 02:42:08,104 INFO L130 BoogieDeclarations]: Found specification of procedure input_abs_get_max [2024-11-14 02:42:08,104 INFO L138 BoogieDeclarations]: Found implementation of procedure input_abs_get_max [2024-11-14 02:42:08,104 INFO L130 BoogieDeclarations]: Found specification of procedure __wake_up [2024-11-14 02:42:08,104 INFO L138 BoogieDeclarations]: Found implementation of procedure __wake_up [2024-11-14 02:42:08,104 INFO L130 BoogieDeclarations]: Found specification of procedure PTR_ERR [2024-11-14 02:42:08,108 INFO L138 BoogieDeclarations]: Found implementation of procedure PTR_ERR [2024-11-14 02:42:08,108 INFO L130 BoogieDeclarations]: Found specification of procedure signal_pending [2024-11-14 02:42:08,108 INFO L138 BoogieDeclarations]: Found implementation of procedure signal_pending [2024-11-14 02:42:08,108 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_lock_interruptible [2024-11-14 02:42:08,108 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_lock_interruptible [2024-11-14 02:42:08,108 INFO L130 BoogieDeclarations]: Found specification of procedure input_abs_get_min [2024-11-14 02:42:08,108 INFO L138 BoogieDeclarations]: Found implementation of procedure input_abs_get_min [2024-11-14 02:42:08,108 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure is_compat_task [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure is_compat_task [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure might_fault [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure might_fault [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure prepare_to_wait [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure prepare_to_wait [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure printk [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure printk [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure kzalloc [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure kzalloc [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure spin_lock [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure spin_lock [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure __init_waitqueue_head [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure __init_waitqueue_head [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure set_bit [2024-11-14 02:42:08,109 INFO L138 BoogieDeclarations]: Found implementation of procedure set_bit [2024-11-14 02:42:08,109 INFO L130 BoogieDeclarations]: Found specification of procedure spin_unlock [2024-11-14 02:42:08,110 INFO L138 BoogieDeclarations]: Found implementation of procedure spin_unlock [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_handler_precall [2024-11-14 02:42:08,110 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_handler_precall [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure schedule [2024-11-14 02:42:08,110 INFO L138 BoogieDeclarations]: Found implementation of procedure schedule [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure read~unchecked~int [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure _copy_from_user [2024-11-14 02:42:08,110 INFO L138 BoogieDeclarations]: Found implementation of procedure _copy_from_user [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure finish_wait [2024-11-14 02:42:08,110 INFO L138 BoogieDeclarations]: Found implementation of procedure finish_wait [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 02:42:08,110 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 02:42:08,110 INFO L130 BoogieDeclarations]: Found specification of procedure IS_ERR [2024-11-14 02:42:08,110 INFO L138 BoogieDeclarations]: Found implementation of procedure IS_ERR [2024-11-14 02:42:08,760 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 02:42:08,763 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 02:42:17,691 INFO L? ?]: Removed 1026 outVars from TransFormulas that were not future-live. [2024-11-14 02:42:17,691 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 02:42:18,416 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 02:42:18,417 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-14 02:42:18,417 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:42:18 BoogieIcfgContainer [2024-11-14 02:42:18,417 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 02:42:18,420 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 02:42:18,421 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 02:42:18,426 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 02:42:18,426 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 02:42:05" (1/3) ... [2024-11-14 02:42:18,427 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@134e5471 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:42:18, skipping insertion in model container [2024-11-14 02:42:18,427 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 02:42:07" (2/3) ... [2024-11-14 02:42:18,428 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@134e5471 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 02:42:18, skipping insertion in model container [2024-11-14 02:42:18,428 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 02:42:18" (3/3) ... [2024-11-14 02:42:18,430 INFO L112 eAbstractionObserver]: Analyzing ICFG linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i [2024-11-14 02:42:18,451 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 02:42:18,453 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG linux-3.8-rc1-32_7a-drivers--input--misc--uinput.ko-ldv_main0.cil.out.i that has 45 procedures, 546 locations, 1 initial locations, 3 loop locations, and 1 error locations. [2024-11-14 02:42:18,598 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 02:42:18,619 INFO L333 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=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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;@4d66c974, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 02:42:18,619 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-14 02:42:18,627 INFO L276 IsEmpty]: Start isEmpty. Operand has 546 states, 358 states have (on average 1.3966480446927374) internal successors, (500), 372 states have internal predecessors, (500), 142 states have call successors, (142), 44 states have call predecessors, (142), 44 states have return successors, (142), 140 states have call predecessors, (142), 142 states have call successors, (142) [2024-11-14 02:42:18,640 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2024-11-14 02:42:18,641 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:18,641 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:18,642 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:18,649 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:18,649 INFO L85 PathProgramCache]: Analyzing trace with hash -1731376332, now seen corresponding path program 1 times [2024-11-14 02:42:18,658 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:18,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1508301802] [2024-11-14 02:42:18,660 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:18,660 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:19,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:19,331 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:19,332 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:19,332 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1508301802] [2024-11-14 02:42:19,333 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1508301802] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:19,333 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:19,333 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:42:19,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [262527184] [2024-11-14 02:42:19,335 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:19,339 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:42:19,340 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:19,360 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:42:19,361 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:19,364 INFO L87 Difference]: Start difference. First operand has 546 states, 358 states have (on average 1.3966480446927374) internal successors, (500), 372 states have internal predecessors, (500), 142 states have call successors, (142), 44 states have call predecessors, (142), 44 states have return successors, (142), 140 states have call predecessors, (142), 142 states have call successors, (142) Second operand has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:42:20,937 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.56s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:21,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:21,671 INFO L93 Difference]: Finished difference Result 1086 states and 1568 transitions. [2024-11-14 02:42:21,672 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:42:21,673 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 10 [2024-11-14 02:42:21,674 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:21,686 INFO L225 Difference]: With dead ends: 1086 [2024-11-14 02:42:21,687 INFO L226 Difference]: Without dead ends: 542 [2024-11-14 02:42:21,698 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:21,703 INFO L432 NwaCegarLoop]: 685 mSDtfsCounter, 771 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 771 SdHoareTripleChecker+Valid, 685 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:21,704 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [771 Valid, 685 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2024-11-14 02:42:21,725 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 542 states. [2024-11-14 02:42:21,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 542 to 542. [2024-11-14 02:42:21,831 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 542 states, 357 states have (on average 1.3893557422969187) internal successors, (496), 368 states have internal predecessors, (496), 141 states have call successors, (141), 44 states have call predecessors, (141), 43 states have return successors, (137), 135 states have call predecessors, (137), 137 states have call successors, (137) [2024-11-14 02:42:21,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 542 states to 542 states and 774 transitions. [2024-11-14 02:42:21,849 INFO L78 Accepts]: Start accepts. Automaton has 542 states and 774 transitions. Word has length 10 [2024-11-14 02:42:21,853 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:21,853 INFO L471 AbstractCegarLoop]: Abstraction has 542 states and 774 transitions. [2024-11-14 02:42:21,853 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.3333333333333335) internal successors, (7), 3 states have internal predecessors, (7), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:42:21,854 INFO L276 IsEmpty]: Start isEmpty. Operand 542 states and 774 transitions. [2024-11-14 02:42:21,855 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2024-11-14 02:42:21,855 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:21,855 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:21,855 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 02:42:21,855 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:21,858 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:21,858 INFO L85 PathProgramCache]: Analyzing trace with hash -2133381690, now seen corresponding path program 1 times [2024-11-14 02:42:21,858 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:21,858 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [266348238] [2024-11-14 02:42:21,858 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:21,858 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:22,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:22,282 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:22,286 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:22,286 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [266348238] [2024-11-14 02:42:22,287 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [266348238] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:22,287 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:22,287 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:42:22,287 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [628957306] [2024-11-14 02:42:22,287 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:22,288 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:42:22,289 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:22,289 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:42:22,290 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:22,290 INFO L87 Difference]: Start difference. First operand 542 states and 774 transitions. Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:42:23,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:23,684 INFO L93 Difference]: Finished difference Result 544 states and 775 transitions. [2024-11-14 02:42:23,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:42:23,685 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2024-11-14 02:42:23,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:23,692 INFO L225 Difference]: With dead ends: 544 [2024-11-14 02:42:23,692 INFO L226 Difference]: Without dead ends: 541 [2024-11-14 02:42:23,693 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:23,694 INFO L432 NwaCegarLoop]: 682 mSDtfsCounter, 766 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 766 SdHoareTripleChecker+Valid, 682 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:23,695 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [766 Valid, 682 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-14 02:42:23,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 541 states. [2024-11-14 02:42:23,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 541 to 541. [2024-11-14 02:42:23,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 541 states, 357 states have (on average 1.3865546218487395) internal successors, (495), 367 states have internal predecessors, (495), 140 states have call successors, (140), 44 states have call predecessors, (140), 43 states have return successors, (137), 135 states have call predecessors, (137), 137 states have call successors, (137) [2024-11-14 02:42:23,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 541 states to 541 states and 772 transitions. [2024-11-14 02:42:23,776 INFO L78 Accepts]: Start accepts. Automaton has 541 states and 772 transitions. Word has length 11 [2024-11-14 02:42:23,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:23,776 INFO L471 AbstractCegarLoop]: Abstraction has 541 states and 772 transitions. [2024-11-14 02:42:23,776 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 3 states have internal predecessors, (8), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:42:23,777 INFO L276 IsEmpty]: Start isEmpty. Operand 541 states and 772 transitions. [2024-11-14 02:42:23,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2024-11-14 02:42:23,777 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:23,778 INFO L215 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:23,778 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 02:42:23,779 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:23,780 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:23,780 INFO L85 PathProgramCache]: Analyzing trace with hash -1710641033, now seen corresponding path program 1 times [2024-11-14 02:42:23,780 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:23,780 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2134828737] [2024-11-14 02:42:23,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:23,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:24,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:24,108 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-14 02:42:24,108 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:24,109 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2134828737] [2024-11-14 02:42:24,109 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2134828737] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:24,109 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:24,109 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:42:24,109 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1044204655] [2024-11-14 02:42:24,109 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:24,110 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:42:24,110 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:24,110 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:42:24,110 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:24,111 INFO L87 Difference]: Start difference. First operand 541 states and 772 transitions. Second operand has 3 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:42:25,257 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.15s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:26,265 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:26,265 INFO L93 Difference]: Finished difference Result 701 states and 989 transitions. [2024-11-14 02:42:26,266 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:42:26,266 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2024-11-14 02:42:26,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:26,280 INFO L225 Difference]: With dead ends: 701 [2024-11-14 02:42:26,281 INFO L226 Difference]: Without dead ends: 691 [2024-11-14 02:42:26,281 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:26,282 INFO L432 NwaCegarLoop]: 686 mSDtfsCounter, 259 mSDsluCounter, 630 mSDsCounter, 0 mSdLazyCounter, 176 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 259 SdHoareTripleChecker+Valid, 1316 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 176 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:26,283 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [259 Valid, 1316 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 176 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-14 02:42:26,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 691 states. [2024-11-14 02:42:26,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 691 to 691. [2024-11-14 02:42:26,355 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 691 states, 452 states have (on average 1.3716814159292035) internal successors, (620), 467 states have internal predecessors, (620), 176 states have call successors, (176), 64 states have call predecessors, (176), 62 states have return successors, (177), 168 states have call predecessors, (177), 173 states have call successors, (177) [2024-11-14 02:42:26,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 691 states to 691 states and 973 transitions. [2024-11-14 02:42:26,369 INFO L78 Accepts]: Start accepts. Automaton has 691 states and 973 transitions. Word has length 12 [2024-11-14 02:42:26,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:26,369 INFO L471 AbstractCegarLoop]: Abstraction has 691 states and 973 transitions. [2024-11-14 02:42:26,369 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.0) internal successors, (9), 3 states have internal predecessors, (9), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-14 02:42:26,370 INFO L276 IsEmpty]: Start isEmpty. Operand 691 states and 973 transitions. [2024-11-14 02:42:26,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-14 02:42:26,376 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:26,376 INFO L215 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, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:26,377 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-14 02:42:26,377 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:26,377 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:26,381 INFO L85 PathProgramCache]: Analyzing trace with hash 1940394133, now seen corresponding path program 1 times [2024-11-14 02:42:26,381 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:26,381 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [362441200] [2024-11-14 02:42:26,382 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:26,382 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:26,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:26,810 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 02:42:26,810 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:26,810 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [362441200] [2024-11-14 02:42:26,810 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [362441200] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:26,810 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:26,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-14 02:42:26,810 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1555575442] [2024-11-14 02:42:26,811 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:26,811 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-14 02:42:26,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:26,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-14 02:42:26,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:26,812 INFO L87 Difference]: Start difference. First operand 691 states and 973 transitions. Second operand has 3 states, 3 states have (on average 8.0) internal successors, (24), 3 states have internal predecessors, (24), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 02:42:27,966 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.15s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:28,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:28,861 INFO L93 Difference]: Finished difference Result 1431 states and 2032 transitions. [2024-11-14 02:42:28,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-14 02:42:28,862 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 8.0) internal successors, (24), 3 states have internal predecessors, (24), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 35 [2024-11-14 02:42:28,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:28,871 INFO L225 Difference]: With dead ends: 1431 [2024-11-14 02:42:28,871 INFO L226 Difference]: Without dead ends: 744 [2024-11-14 02:42:28,877 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-14 02:42:28,880 INFO L432 NwaCegarLoop]: 683 mSDtfsCounter, 34 mSDsluCounter, 659 mSDsCounter, 0 mSdLazyCounter, 191 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 1342 SdHoareTripleChecker+Invalid, 196 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 191 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:28,883 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 1342 Invalid, 196 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 191 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-14 02:42:28,885 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 744 states. [2024-11-14 02:42:28,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 744 to 737. [2024-11-14 02:42:28,975 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 737 states, 488 states have (on average 1.375) internal successors, (671), 503 states have internal predecessors, (671), 186 states have call successors, (186), 64 states have call predecessors, (186), 62 states have return successors, (191), 178 states have call predecessors, (191), 183 states have call successors, (191) [2024-11-14 02:42:28,983 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 737 states to 737 states and 1048 transitions. [2024-11-14 02:42:28,985 INFO L78 Accepts]: Start accepts. Automaton has 737 states and 1048 transitions. Word has length 35 [2024-11-14 02:42:28,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:28,986 INFO L471 AbstractCegarLoop]: Abstraction has 737 states and 1048 transitions. [2024-11-14 02:42:28,986 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 8.0) internal successors, (24), 3 states have internal predecessors, (24), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-14 02:42:28,987 INFO L276 IsEmpty]: Start isEmpty. Operand 737 states and 1048 transitions. [2024-11-14 02:42:28,989 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2024-11-14 02:42:28,993 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:28,993 INFO L215 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:28,993 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2024-11-14 02:42:28,994 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:28,994 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:28,994 INFO L85 PathProgramCache]: Analyzing trace with hash -1943168451, now seen corresponding path program 1 times [2024-11-14 02:42:28,994 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:28,994 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [459867031] [2024-11-14 02:42:28,994 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:28,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:29,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:29,869 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 02:42:29,870 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:29,870 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [459867031] [2024-11-14 02:42:29,870 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [459867031] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:29,870 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:29,870 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 02:42:29,870 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1892332976] [2024-11-14 02:42:29,870 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:29,871 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 02:42:29,871 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:29,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 02:42:29,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:42:29,873 INFO L87 Difference]: Start difference. First operand 737 states and 1048 transitions. Second operand has 6 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-14 02:42:32,036 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.16s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:34,553 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.22s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:36,286 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:36,286 INFO L93 Difference]: Finished difference Result 816 states and 1138 transitions. [2024-11-14 02:42:36,288 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 02:42:36,288 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 44 [2024-11-14 02:42:36,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:36,295 INFO L225 Difference]: With dead ends: 816 [2024-11-14 02:42:36,295 INFO L226 Difference]: Without dead ends: 813 [2024-11-14 02:42:36,297 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:42:36,298 INFO L432 NwaCegarLoop]: 681 mSDtfsCounter, 395 mSDsluCounter, 1485 mSDsCounter, 0 mSdLazyCounter, 411 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 395 SdHoareTripleChecker+Valid, 2166 SdHoareTripleChecker+Invalid, 412 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 411 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.3s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:36,298 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [395 Valid, 2166 Invalid, 412 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 411 Invalid, 0 Unknown, 0 Unchecked, 6.3s Time] [2024-11-14 02:42:36,300 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 813 states. [2024-11-14 02:42:36,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 813 to 813. [2024-11-14 02:42:36,386 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 813 states, 536 states have (on average 1.3694029850746268) internal successors, (734), 553 states have internal predecessors, (734), 198 states have call successors, (198), 81 states have call predecessors, (198), 78 states have return successors, (203), 190 states have call predecessors, (203), 195 states have call successors, (203) [2024-11-14 02:42:36,394 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 813 states to 813 states and 1135 transitions. [2024-11-14 02:42:36,395 INFO L78 Accepts]: Start accepts. Automaton has 813 states and 1135 transitions. Word has length 44 [2024-11-14 02:42:36,395 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:36,395 INFO L471 AbstractCegarLoop]: Abstraction has 813 states and 1135 transitions. [2024-11-14 02:42:36,396 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 6.4) internal successors, (32), 5 states have internal predecessors, (32), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2024-11-14 02:42:36,396 INFO L276 IsEmpty]: Start isEmpty. Operand 813 states and 1135 transitions. [2024-11-14 02:42:36,398 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-14 02:42:36,399 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:36,400 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:36,400 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2024-11-14 02:42:36,400 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:36,401 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:36,401 INFO L85 PathProgramCache]: Analyzing trace with hash -1428407110, now seen corresponding path program 1 times [2024-11-14 02:42:36,401 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:36,401 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [542933157] [2024-11-14 02:42:36,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:36,401 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:36,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:37,329 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-14 02:42:37,329 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:37,329 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [542933157] [2024-11-14 02:42:37,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [542933157] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:37,330 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:37,330 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-14 02:42:37,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [267868125] [2024-11-14 02:42:37,330 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:37,330 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-14 02:42:37,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:37,331 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-14 02:42:37,331 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-14 02:42:37,331 INFO L87 Difference]: Start difference. First operand 813 states and 1135 transitions. Second operand has 7 states, 6 states have (on average 5.0) internal successors, (30), 6 states have internal predecessors, (30), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-14 02:42:38,420 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.09s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:40,465 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.04s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:41,767 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.30s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:42,916 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.15s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:47,235 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:47,236 INFO L93 Difference]: Finished difference Result 992 states and 1388 transitions. [2024-11-14 02:42:47,236 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-14 02:42:47,237 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 5.0) internal successors, (30), 6 states have internal predecessors, (30), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 46 [2024-11-14 02:42:47,237 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:47,246 INFO L225 Difference]: With dead ends: 992 [2024-11-14 02:42:47,247 INFO L226 Difference]: Without dead ends: 982 [2024-11-14 02:42:47,248 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2024-11-14 02:42:47,249 INFO L432 NwaCegarLoop]: 471 mSDtfsCounter, 477 mSDsluCounter, 1460 mSDsCounter, 0 mSdLazyCounter, 1342 mSolverCounterSat, 178 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 560 SdHoareTripleChecker+Valid, 1931 SdHoareTripleChecker+Invalid, 1520 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 178 IncrementalHoareTripleChecker+Valid, 1342 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.7s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:47,250 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [560 Valid, 1931 Invalid, 1520 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [178 Valid, 1342 Invalid, 0 Unknown, 0 Unchecked, 9.7s Time] [2024-11-14 02:42:47,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 982 states. [2024-11-14 02:42:47,338 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 982 to 957. [2024-11-14 02:42:47,341 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 957 states, 634 states have (on average 1.3722397476340693) internal successors, (870), 654 states have internal predecessors, (870), 229 states have call successors, (229), 96 states have call predecessors, (229), 93 states have return successors, (234), 221 states have call predecessors, (234), 226 states have call successors, (234) [2024-11-14 02:42:47,351 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 957 states to 957 states and 1333 transitions. [2024-11-14 02:42:47,354 INFO L78 Accepts]: Start accepts. Automaton has 957 states and 1333 transitions. Word has length 46 [2024-11-14 02:42:47,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:47,354 INFO L471 AbstractCegarLoop]: Abstraction has 957 states and 1333 transitions. [2024-11-14 02:42:47,356 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 5.0) internal successors, (30), 6 states have internal predecessors, (30), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-14 02:42:47,357 INFO L276 IsEmpty]: Start isEmpty. Operand 957 states and 1333 transitions. [2024-11-14 02:42:47,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-14 02:42:47,362 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:47,362 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:47,362 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-14 02:42:47,363 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:47,363 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:47,363 INFO L85 PathProgramCache]: Analyzing trace with hash -1341718069, now seen corresponding path program 1 times [2024-11-14 02:42:47,363 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:47,363 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [734767849] [2024-11-14 02:42:47,363 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:47,363 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:47,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:47,789 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-14 02:42:47,790 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:47,790 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [734767849] [2024-11-14 02:42:47,791 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [734767849] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:47,791 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:47,791 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 02:42:47,791 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [794200009] [2024-11-14 02:42:47,791 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:47,792 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 02:42:47,792 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:47,792 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 02:42:47,793 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:42:47,793 INFO L87 Difference]: Start difference. First operand 957 states and 1333 transitions. Second operand has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-14 02:42:51,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:51,890 INFO L93 Difference]: Finished difference Result 1919 states and 2674 transitions. [2024-11-14 02:42:51,891 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 02:42:51,891 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 57 [2024-11-14 02:42:51,893 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:51,902 INFO L225 Difference]: With dead ends: 1919 [2024-11-14 02:42:51,902 INFO L226 Difference]: Without dead ends: 960 [2024-11-14 02:42:51,908 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 02:42:51,909 INFO L432 NwaCegarLoop]: 680 mSDtfsCounter, 0 mSDsluCounter, 1357 mSDsCounter, 0 mSdLazyCounter, 275 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 2037 SdHoareTripleChecker+Invalid, 275 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 275 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.0s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:51,910 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 2037 Invalid, 275 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 275 Invalid, 0 Unknown, 0 Unchecked, 4.0s Time] [2024-11-14 02:42:51,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 960 states. [2024-11-14 02:42:52,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 960 to 960. [2024-11-14 02:42:52,006 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 960 states, 636 states have (on average 1.3679245283018868) internal successors, (870), 656 states have internal predecessors, (870), 230 states have call successors, (230), 96 states have call predecessors, (230), 93 states have return successors, (235), 222 states have call predecessors, (235), 227 states have call successors, (235) [2024-11-14 02:42:52,014 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 960 states to 960 states and 1335 transitions. [2024-11-14 02:42:52,015 INFO L78 Accepts]: Start accepts. Automaton has 960 states and 1335 transitions. Word has length 57 [2024-11-14 02:42:52,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:52,016 INFO L471 AbstractCegarLoop]: Abstraction has 960 states and 1335 transitions. [2024-11-14 02:42:52,016 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 9.25) internal successors, (37), 4 states have internal predecessors, (37), 3 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-14 02:42:52,016 INFO L276 IsEmpty]: Start isEmpty. Operand 960 states and 1335 transitions. [2024-11-14 02:42:52,021 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2024-11-14 02:42:52,025 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:52,025 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:52,025 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-14 02:42:52,025 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:52,026 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:52,026 INFO L85 PathProgramCache]: Analyzing trace with hash 1719559012, now seen corresponding path program 1 times [2024-11-14 02:42:52,026 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:52,026 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1411136258] [2024-11-14 02:42:52,026 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:52,027 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:52,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:52,810 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-14 02:42:52,810 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:52,811 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1411136258] [2024-11-14 02:42:52,811 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1411136258] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 02:42:52,811 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 02:42:52,811 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-14 02:42:52,811 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [943573293] [2024-11-14 02:42:52,811 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 02:42:52,812 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-14 02:42:52,812 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 02:42:52,813 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-14 02:42:52,813 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:42:52,813 INFO L87 Difference]: Start difference. First operand 960 states and 1335 transitions. Second operand has 6 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 3 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 1 states have call successors, (10) [2024-11-14 02:42:56,736 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.41s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-14 02:42:57,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 02:42:57,978 INFO L93 Difference]: Finished difference Result 999 states and 1387 transitions. [2024-11-14 02:42:57,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 02:42:57,978 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 3 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 1 states have call successors, (10) Word has length 65 [2024-11-14 02:42:57,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 02:42:57,986 INFO L225 Difference]: With dead ends: 999 [2024-11-14 02:42:57,986 INFO L226 Difference]: Without dead ends: 996 [2024-11-14 02:42:57,987 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2024-11-14 02:42:57,988 INFO L432 NwaCegarLoop]: 722 mSDtfsCounter, 114 mSDsluCounter, 1957 mSDsCounter, 0 mSdLazyCounter, 386 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 114 SdHoareTripleChecker+Valid, 2679 SdHoareTripleChecker+Invalid, 402 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 386 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.1s IncrementalHoareTripleChecker+Time [2024-11-14 02:42:57,988 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [114 Valid, 2679 Invalid, 402 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 386 Invalid, 0 Unknown, 0 Unchecked, 5.1s Time] [2024-11-14 02:42:57,990 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 996 states. [2024-11-14 02:42:58,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 996 to 994. [2024-11-14 02:42:58,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 994 states, 661 states have (on average 1.3721633888048412) internal successors, (907), 683 states have internal predecessors, (907), 235 states have call successors, (235), 100 states have call predecessors, (235), 97 states have return successors, (240), 227 states have call predecessors, (240), 232 states have call successors, (240) [2024-11-14 02:42:58,061 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 994 states to 994 states and 1382 transitions. [2024-11-14 02:42:58,063 INFO L78 Accepts]: Start accepts. Automaton has 994 states and 1382 transitions. Word has length 65 [2024-11-14 02:42:58,063 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 02:42:58,063 INFO L471 AbstractCegarLoop]: Abstraction has 994 states and 1382 transitions. [2024-11-14 02:42:58,063 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 7.6) internal successors, (38), 5 states have internal predecessors, (38), 3 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 1 states have call successors, (10) [2024-11-14 02:42:58,063 INFO L276 IsEmpty]: Start isEmpty. Operand 994 states and 1382 transitions. [2024-11-14 02:42:58,068 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-14 02:42:58,068 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 02:42:58,069 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 02:42:58,069 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2024-11-14 02:42:58,069 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION === [ldv_errorErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 02:42:58,069 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 02:42:58,070 INFO L85 PathProgramCache]: Analyzing trace with hash -2111824302, now seen corresponding path program 1 times [2024-11-14 02:42:58,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 02:42:58,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [792779413] [2024-11-14 02:42:58,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:58,070 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 02:42:58,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:58,445 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-14 02:42:58,446 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 02:42:58,446 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [792779413] [2024-11-14 02:42:58,446 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [792779413] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 02:42:58,446 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1535346498] [2024-11-14 02:42:58,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 02:42:58,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 02:42:58,446 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 02:42:58,449 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 02:42:58,452 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_4f504924-9c3f-4cf6-b9fa-f3e537d7b536/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 02:42:59,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 02:42:59,309 INFO L255 TraceCheckSpWp]: Trace formula consists of 786 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-14 02:42:59,317 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 02:42:59,547 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 4 proven. 3 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 02:42:59,553 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 02:42:59,934 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-14 02:42:59,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1535346498] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-14 02:42:59,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1776545656] [2024-11-14 02:43:00,000 INFO L159 IcfgInterpreter]: Started Sifa with 59 locations of interest [2024-11-14 02:43:00,001 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 02:43:00,007 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 02:43:00,015 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 02:43:00,015 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 02:43:32,198 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_check_return_value with input of size 114 for LOIs [2024-11-14 02:43:32,215 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_handler_precall with input of size 23 for LOIs [2024-11-14 02:43:32,219 INFO L197 IcfgInterpreter]: Interpreting procedure kzalloc with input of size 75 for LOIs [2024-11-14 02:43:32,669 INFO L197 IcfgInterpreter]: Interpreting procedure __init_waitqueue_head with input of size 101 for LOIs [2024-11-14 02:43:32,773 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_malloc with input of size 81 for LOIs [2024-11-14 02:43:32,838 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 02:50:47,018 WARN L286 SmtUtils]: Spent 7.21m on a formula simplification that was a NOOP. DAG size: 508 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)