/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml --traceabstraction.trace.refinement.strategy FIXED_PREFERENCES --cacsl2boogietranslator.allow.undefined.functions true --traceabstraction.smt.solver External_ModelsAndUnsatCoreMode --traceabstraction.command.for.external.solver 'z3 -smt2 -in SMTLIB2_COMPLIANT=true' -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf -i ../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 15:07:14,953 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 15:07:15,037 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf [2024-11-04 15:07:15,041 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 15:07:15,041 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 15:07:15,067 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 15:07:15,068 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 15:07:15,068 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 15:07:15,069 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 15:07:15,069 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 15:07:15,069 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 15:07:15,070 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 15:07:15,070 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 15:07:15,071 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 15:07:15,071 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 15:07:15,071 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 15:07:15,072 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 15:07:15,072 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 15:07:15,075 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 15:07:15,075 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 15:07:15,075 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 15:07:15,079 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 15:07:15,079 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 15:07:15,080 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 15:07:15,080 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 15:07:15,080 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 15:07:15,081 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 15:07:15,081 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 15:07:15,081 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 15:07:15,081 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 15:07:15,081 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 15:07:15,082 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:07:15,082 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 15:07:15,082 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 15:07:15,082 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 15:07:15,083 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 15:07:15,083 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 15:07:15,083 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 15:07:15,083 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 15:07:15,084 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 15:07:15,084 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 15:07:15,085 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Trace refinement strategy -> FIXED_PREFERENCES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Allow undefined functions -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMT solver -> External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Command for external solver -> z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:15,306 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 15:07:15,332 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 15:07:15,335 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 15:07:15,336 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 15:07:15,337 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 15:07:15,338 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i [2024-11-04 15:07:16,782 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 15:07:17,163 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 15:07:17,164 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i [2024-11-04 15:07:17,205 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5d33c98a0/7b29764bd45b4abea605e0fca8b34249/FLAG9ee5a088a [2024-11-04 15:07:17,223 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5d33c98a0/7b29764bd45b4abea605e0fca8b34249 [2024-11-04 15:07:17,227 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 15:07:17,228 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 15:07:17,230 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 15:07:17,230 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 15:07:17,235 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 15:07:17,236 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:07:17" (1/1) ... [2024-11-04 15:07:17,237 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7b30f73c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:17, skipping insertion in model container [2024-11-04 15:07:17,237 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:07:17" (1/1) ... [2024-11-04 15:07:17,323 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:07:17,630 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i[4495,4508] [2024-11-04 15:07:17,641 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i[4555,4568] [2024-11-04 15:07:18,200 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,295 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,296 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,297 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,311 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,313 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,314 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,344 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,345 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,345 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,346 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,350 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,350 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,355 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,355 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,369 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,370 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,373 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,374 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,376 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,376 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,376 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,377 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,378 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,379 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,379 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,380 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,380 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,380 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,613 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,613 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,618 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,619 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,720 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,743 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:07:18,767 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 15:07:18,821 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:07:18,826 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i[4495,4508] [2024-11-04 15:07:18,827 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i[4555,4568] [2024-11-04 15:07:18,863 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,886 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,886 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,887 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,894 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,900 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,900 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,901 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,901 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,901 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,902 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,906 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,906 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,907 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,912 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,917 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,917 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,918 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,918 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,920 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,920 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,921 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,921 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,922 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,922 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,922 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,923 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,923 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,923 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:18,981 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,982 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,982 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:18,983 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:19,018 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:19,026 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:07:19,033 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 15:07:19,048 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i[4495,4508] [2024-11-04 15:07:19,050 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_front_harness_negated.i[4555,4568] [2024-11-04 15:07:19,100 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,101 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,101 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,102 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,102 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,108 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,108 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,109 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,110 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,110 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,111 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,111 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,111 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:19,188 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:07:19,363 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 15:07:19,373 INFO L204 MainTranslator]: Completed translation [2024-11-04 15:07:19,373 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19 WrapperNode [2024-11-04 15:07:19,373 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 15:07:19,374 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 15:07:19,374 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 15:07:19,374 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 15:07:19,381 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,460 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,501 INFO L138 Inliner]: procedures = 687, calls = 1043, calls flagged for inlining = 50, calls inlined = 5, statements flattened = 136 [2024-11-04 15:07:19,502 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 15:07:19,503 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 15:07:19,503 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 15:07:19,503 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 15:07:19,515 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,516 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,520 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,547 INFO L175 MemorySlicer]: Split 27 memory accesses to 3 slices as follows [2, 20, 5]. 74 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 0, 5]. The 6 writes are split as follows [0, 6, 0]. [2024-11-04 15:07:19,548 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,548 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,567 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,571 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,576 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,578 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,584 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 15:07:19,585 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 15:07:19,585 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 15:07:19,585 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 15:07:19,590 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (1/1) ... [2024-11-04 15:07:19,595 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:07:19,604 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:19,619 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-04 15:07:19,622 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-04 15:07:19,647 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 15:07:19,648 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 15:07:19,648 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 15:07:19,648 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 15:07:19,648 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 15:07:19,648 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 15:07:19,648 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:07:19,648 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:07:19,648 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-04 15:07:19,648 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-04 15:07:19,649 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_front [2024-11-04 15:07:19,649 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_front [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 15:07:19,649 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2024-11-04 15:07:19,649 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2024-11-04 15:07:19,649 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 15:07:19,649 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-04 15:07:19,650 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-04 15:07:19,650 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2024-11-04 15:07:19,650 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2024-11-04 15:07:19,941 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 15:07:19,944 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 15:07:20,369 INFO L? ?]: Removed 61 outVars from TransFormulas that were not future-live. [2024-11-04 15:07:20,369 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 15:07:20,385 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 15:07:20,385 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-04 15:07:20,385 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:07:20 BoogieIcfgContainer [2024-11-04 15:07:20,385 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 15:07:20,389 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 15:07:20,389 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 15:07:20,392 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 15:07:20,392 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 03:07:17" (1/3) ... [2024-11-04 15:07:20,393 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2583a228 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:07:20, skipping insertion in model container [2024-11-04 15:07:20,393 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:19" (2/3) ... [2024-11-04 15:07:20,393 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2583a228 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:07:20, skipping insertion in model container [2024-11-04 15:07:20,393 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:07:20" (3/3) ... [2024-11-04 15:07:20,394 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_front_harness_negated.i [2024-11-04 15:07:20,427 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 15:07:20,428 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 15:07:20,494 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 15:07:20,502 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=PETRI_NET, 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;@2f956c7d, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 15:07:20,502 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 15:07:20,507 INFO L276 IsEmpty]: Start isEmpty. Operand has 98 states, 64 states have (on average 1.296875) internal successors, (83), 65 states have internal predecessors, (83), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2024-11-04 15:07:20,518 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-04 15:07:20,519 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:20,519 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:20,520 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:20,525 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:20,525 INFO L85 PathProgramCache]: Analyzing trace with hash -1606468667, now seen corresponding path program 1 times [2024-11-04 15:07:20,533 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:20,534 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [119306429] [2024-11-04 15:07:20,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:20,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:20,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:20,540 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:20,542 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-04 15:07:20,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:20,784 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 15:07:20,792 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:20,830 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-04 15:07:20,830 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:20,930 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-04 15:07:20,932 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:20,932 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [119306429] [2024-11-04 15:07:20,932 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [119306429] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:20,932 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:20,932 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-04 15:07:20,934 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1580766824] [2024-11-04 15:07:20,934 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:20,938 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 15:07:20,938 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:20,956 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 15:07:20,956 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 15:07:20,958 INFO L87 Difference]: Start difference. First operand has 98 states, 64 states have (on average 1.296875) internal successors, (83), 65 states have internal predecessors, (83), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand has 2 states, 2 states have (on average 17.0) internal successors, (34), 2 states have internal predecessors, (34), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-04 15:07:20,989 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:20,990 INFO L93 Difference]: Finished difference Result 188 states and 271 transitions. [2024-11-04 15:07:20,991 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 15:07:20,992 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 17.0) internal successors, (34), 2 states have internal predecessors, (34), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 84 [2024-11-04 15:07:20,993 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:20,999 INFO L225 Difference]: With dead ends: 188 [2024-11-04 15:07:21,000 INFO L226 Difference]: Without dead ends: 93 [2024-11-04 15:07:21,007 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 166 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 15:07:21,011 INFO L432 NwaCegarLoop]: 127 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 127 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:21,012 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 127 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:21,029 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-11-04 15:07:21,056 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-11-04 15:07:21,059 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 60 states have (on average 1.25) internal successors, (75), 61 states have internal predecessors, (75), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2024-11-04 15:07:21,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 122 transitions. [2024-11-04 15:07:21,066 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 122 transitions. Word has length 84 [2024-11-04 15:07:21,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:21,067 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 122 transitions. [2024-11-04 15:07:21,067 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 17.0) internal successors, (34), 2 states have internal predecessors, (34), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-04 15:07:21,067 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 122 transitions. [2024-11-04 15:07:21,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-04 15:07:21,072 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:21,072 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:21,097 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-04 15:07:21,276 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:21,277 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:21,278 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:21,278 INFO L85 PathProgramCache]: Analyzing trace with hash -1607570691, now seen corresponding path program 1 times [2024-11-04 15:07:21,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:21,278 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1290859012] [2024-11-04 15:07:21,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:21,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:21,279 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:21,281 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:21,282 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-04 15:07:21,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:21,482 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:07:21,486 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:21,554 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 57 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-04 15:07:21,554 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:21,656 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 9 proven. 8 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2024-11-04 15:07:21,656 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:21,656 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1290859012] [2024-11-04 15:07:21,656 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1290859012] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:21,656 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:21,657 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 15:07:21,658 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [438805678] [2024-11-04 15:07:21,658 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:21,660 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:07:21,661 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:21,662 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:07:21,662 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:07:21,662 INFO L87 Difference]: Start difference. First operand 93 states and 122 transitions. Second operand has 6 states, 5 states have (on average 10.2) internal successors, (51), 5 states have internal predecessors, (51), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 15:07:21,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:21,748 INFO L93 Difference]: Finished difference Result 169 states and 224 transitions. [2024-11-04 15:07:21,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:07:21,752 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 10.2) internal successors, (51), 5 states have internal predecessors, (51), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 84 [2024-11-04 15:07:21,753 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:21,755 INFO L225 Difference]: With dead ends: 169 [2024-11-04 15:07:21,755 INFO L226 Difference]: Without dead ends: 95 [2024-11-04 15:07:21,756 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 161 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:07:21,758 INFO L432 NwaCegarLoop]: 116 mSDtfsCounter, 0 mSDsluCounter, 448 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 564 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:21,759 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 564 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:07:21,760 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-04 15:07:21,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2024-11-04 15:07:21,777 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 61 states have (on average 1.2459016393442623) internal successors, (76), 63 states have internal predecessors, (76), 24 states have call successors, (24), 8 states have call predecessors, (24), 9 states have return successors, (25), 23 states have call predecessors, (25), 23 states have call successors, (25) [2024-11-04 15:07:21,779 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 125 transitions. [2024-11-04 15:07:21,781 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 125 transitions. Word has length 84 [2024-11-04 15:07:21,781 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:21,781 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 125 transitions. [2024-11-04 15:07:21,782 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 10.2) internal successors, (51), 5 states have internal predecessors, (51), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 15:07:21,782 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 125 transitions. [2024-11-04 15:07:21,784 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-11-04 15:07:21,784 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:21,784 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:21,806 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:21,985 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:21,985 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:21,986 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:21,986 INFO L85 PathProgramCache]: Analyzing trace with hash -254868999, now seen corresponding path program 1 times [2024-11-04 15:07:21,986 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:21,986 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1145760330] [2024-11-04 15:07:21,986 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:21,987 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:21,987 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:21,992 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:21,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-04 15:07:22,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:22,166 INFO L255 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 15:07:22,170 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:22,302 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-04 15:07:22,302 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:22,509 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-04 15:07:22,510 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:22,510 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1145760330] [2024-11-04 15:07:22,510 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1145760330] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:22,510 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:22,510 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 10 [2024-11-04 15:07:22,510 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [845237306] [2024-11-04 15:07:22,511 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:22,511 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:07:22,511 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:22,512 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:07:22,512 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-04 15:07:22,512 INFO L87 Difference]: Start difference. First operand 95 states and 125 transitions. Second operand has 8 states, 7 states have (on average 7.142857142857143) internal successors, (50), 7 states have internal predecessors, (50), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:07:22,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:22,724 INFO L93 Difference]: Finished difference Result 176 states and 233 transitions. [2024-11-04 15:07:22,725 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 15:07:22,725 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 7.142857142857143) internal successors, (50), 7 states have internal predecessors, (50), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 86 [2024-11-04 15:07:22,725 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:22,728 INFO L225 Difference]: With dead ends: 176 [2024-11-04 15:07:22,728 INFO L226 Difference]: Without dead ends: 97 [2024-11-04 15:07:22,729 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 162 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 15:07:22,730 INFO L432 NwaCegarLoop]: 109 mSDtfsCounter, 32 mSDsluCounter, 572 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 681 SdHoareTripleChecker+Invalid, 127 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:22,730 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [41 Valid, 681 Invalid, 127 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 15:07:22,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2024-11-04 15:07:22,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 95. [2024-11-04 15:07:22,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 61 states have (on average 1.2295081967213115) internal successors, (75), 63 states have internal predecessors, (75), 24 states have call successors, (24), 8 states have call predecessors, (24), 9 states have return successors, (25), 23 states have call predecessors, (25), 23 states have call successors, (25) [2024-11-04 15:07:22,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 124 transitions. [2024-11-04 15:07:22,754 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 124 transitions. Word has length 86 [2024-11-04 15:07:22,754 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:22,754 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 124 transitions. [2024-11-04 15:07:22,755 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 7.142857142857143) internal successors, (50), 7 states have internal predecessors, (50), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:07:22,755 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 124 transitions. [2024-11-04 15:07:22,756 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2024-11-04 15:07:22,756 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:22,759 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:22,776 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:22,962 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:22,963 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:22,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:22,963 INFO L85 PathProgramCache]: Analyzing trace with hash -2045206106, now seen corresponding path program 1 times [2024-11-04 15:07:22,964 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:22,964 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [66413734] [2024-11-04 15:07:22,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:22,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:22,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:22,968 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:22,969 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-04 15:07:23,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:23,148 INFO L255 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 15:07:23,156 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:23,302 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-04 15:07:23,302 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:23,598 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-04 15:07:23,599 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:23,599 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [66413734] [2024-11-04 15:07:23,599 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [66413734] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:23,599 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:23,599 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 12 [2024-11-04 15:07:23,600 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [533601397] [2024-11-04 15:07:23,600 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:23,600 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-04 15:07:23,600 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:23,601 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-04 15:07:23,601 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-04 15:07:23,601 INFO L87 Difference]: Start difference. First operand 95 states and 124 transitions. Second operand has 9 states, 8 states have (on average 6.5) internal successors, (52), 8 states have internal predecessors, (52), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:07:23,860 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:23,860 INFO L93 Difference]: Finished difference Result 182 states and 241 transitions. [2024-11-04 15:07:23,861 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-04 15:07:23,861 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 6.5) internal successors, (52), 8 states have internal predecessors, (52), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 88 [2024-11-04 15:07:23,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:23,863 INFO L225 Difference]: With dead ends: 182 [2024-11-04 15:07:23,863 INFO L226 Difference]: Without dead ends: 102 [2024-11-04 15:07:23,864 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 164 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2024-11-04 15:07:23,864 INFO L432 NwaCegarLoop]: 106 mSDtfsCounter, 41 mSDsluCounter, 659 mSDsCounter, 0 mSdLazyCounter, 137 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 765 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 137 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:23,865 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 765 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 137 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 15:07:23,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-11-04 15:07:23,876 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 96. [2024-11-04 15:07:23,877 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 62 states have (on average 1.2258064516129032) internal successors, (76), 64 states have internal predecessors, (76), 24 states have call successors, (24), 8 states have call predecessors, (24), 9 states have return successors, (25), 23 states have call predecessors, (25), 23 states have call successors, (25) [2024-11-04 15:07:23,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 125 transitions. [2024-11-04 15:07:23,878 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 125 transitions. Word has length 88 [2024-11-04 15:07:23,878 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:23,878 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 125 transitions. [2024-11-04 15:07:23,879 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 6.5) internal successors, (52), 8 states have internal predecessors, (52), 4 states have call successors, (13), 3 states have call predecessors, (13), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:07:23,879 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 125 transitions. [2024-11-04 15:07:23,881 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-04 15:07:23,881 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:23,881 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:23,902 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-04 15:07:24,081 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:24,082 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:24,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:24,083 INFO L85 PathProgramCache]: Analyzing trace with hash -708361508, now seen corresponding path program 1 times [2024-11-04 15:07:24,083 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:24,083 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [353354381] [2024-11-04 15:07:24,083 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:24,083 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:24,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:24,084 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:24,085 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-04 15:07:24,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:24,251 INFO L255 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-04 15:07:24,254 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:24,268 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 50 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-04 15:07:24,268 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:24,329 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-11-04 15:07:24,329 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:24,329 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [353354381] [2024-11-04 15:07:24,329 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [353354381] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:24,329 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:24,329 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 4 [2024-11-04 15:07:24,330 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1417795898] [2024-11-04 15:07:24,330 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:24,330 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-04 15:07:24,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:24,331 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-04 15:07:24,331 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:24,331 INFO L87 Difference]: Start difference. First operand 96 states and 125 transitions. Second operand has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:07:24,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:24,363 INFO L93 Difference]: Finished difference Result 177 states and 236 transitions. [2024-11-04 15:07:24,364 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-04 15:07:24,364 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 89 [2024-11-04 15:07:24,364 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:24,366 INFO L225 Difference]: With dead ends: 177 [2024-11-04 15:07:24,367 INFO L226 Difference]: Without dead ends: 100 [2024-11-04 15:07:24,367 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 174 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:24,368 INFO L432 NwaCegarLoop]: 118 mSDtfsCounter, 2 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 231 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:24,368 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 231 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:24,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-04 15:07:24,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 97. [2024-11-04 15:07:24,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 63 states have (on average 1.2222222222222223) internal successors, (77), 65 states have internal predecessors, (77), 24 states have call successors, (24), 8 states have call predecessors, (24), 9 states have return successors, (25), 23 states have call predecessors, (25), 23 states have call successors, (25) [2024-11-04 15:07:24,381 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 126 transitions. [2024-11-04 15:07:24,382 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 126 transitions. Word has length 89 [2024-11-04 15:07:24,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:24,382 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 126 transitions. [2024-11-04 15:07:24,382 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:07:24,382 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 126 transitions. [2024-11-04 15:07:24,383 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-11-04 15:07:24,384 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:24,384 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:07:24,399 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:24,584 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:24,585 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:24,585 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:24,585 INFO L85 PathProgramCache]: Analyzing trace with hash -1326114882, now seen corresponding path program 1 times [2024-11-04 15:07:24,585 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:24,586 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1571250511] [2024-11-04 15:07:24,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:24,586 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:24,586 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:24,588 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:24,589 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-04 15:07:24,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:24,760 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:07:24,764 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:24,818 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 57 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-04 15:07:24,818 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:24,925 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 9 proven. 8 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2024-11-04 15:07:24,926 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:24,926 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1571250511] [2024-11-04 15:07:24,926 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1571250511] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:24,926 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:24,926 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 15:07:24,926 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [722648608] [2024-11-04 15:07:24,926 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:24,927 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:07:24,927 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:24,928 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:07:24,928 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:24,928 INFO L87 Difference]: Start difference. First operand 97 states and 126 transitions. Second operand has 7 states, 6 states have (on average 10.333333333333334) internal successors, (62), 6 states have internal predecessors, (62), 3 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 15:07:25,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:25,005 INFO L93 Difference]: Finished difference Result 178 states and 233 transitions. [2024-11-04 15:07:25,007 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:07:25,007 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 10.333333333333334) internal successors, (62), 6 states have internal predecessors, (62), 3 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 97 [2024-11-04 15:07:25,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:25,009 INFO L225 Difference]: With dead ends: 178 [2024-11-04 15:07:25,009 INFO L226 Difference]: Without dead ends: 100 [2024-11-04 15:07:25,010 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 186 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:25,010 INFO L432 NwaCegarLoop]: 114 mSDtfsCounter, 0 mSDsluCounter, 552 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 666 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:25,011 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 666 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:07:25,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-04 15:07:25,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 98. [2024-11-04 15:07:25,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 64 states have (on average 1.21875) internal successors, (78), 66 states have internal predecessors, (78), 24 states have call successors, (24), 8 states have call predecessors, (24), 9 states have return successors, (25), 23 states have call predecessors, (25), 23 states have call successors, (25) [2024-11-04 15:07:25,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 127 transitions. [2024-11-04 15:07:25,032 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 127 transitions. Word has length 97 [2024-11-04 15:07:25,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:25,033 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 127 transitions. [2024-11-04 15:07:25,033 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 10.333333333333334) internal successors, (62), 6 states have internal predecessors, (62), 3 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 15:07:25,033 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 127 transitions. [2024-11-04 15:07:25,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-04 15:07:25,034 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:25,038 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:07:25,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:25,238 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:25,239 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:25,239 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:25,239 INFO L85 PathProgramCache]: Analyzing trace with hash -720348629, now seen corresponding path program 1 times [2024-11-04 15:07:25,239 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:25,240 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2111462907] [2024-11-04 15:07:25,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:25,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:25,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:25,242 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:25,243 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-04 15:07:25,417 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:25,422 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-04 15:07:25,429 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:25,477 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-04 15:07:29,936 WARN L873 $PredicateComparison]: unable to prove that (or (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (_ bv0 64) (select (select |c_#memory_$Pointer$#1.base| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|)))) (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (select (select |c_#memory_$Pointer$#1.offset| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|) (_ bv0 64))))) is different from true [2024-11-04 15:07:30,169 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 50 proven. 1 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-04 15:07:30,170 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:30,526 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-04 15:07:30,527 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:30,527 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2111462907] [2024-11-04 15:07:30,527 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2111462907] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:07:30,527 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:07:30,527 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2024-11-04 15:07:30,527 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2113428323] [2024-11-04 15:07:30,527 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:07:30,528 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-04 15:07:30,528 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:30,529 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-04 15:07:30,529 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=199, Unknown=1, NotChecked=28, Total=272 [2024-11-04 15:07:30,529 INFO L87 Difference]: Start difference. First operand 98 states and 127 transitions. Second operand has 17 states, 17 states have (on average 5.529411764705882) internal successors, (94), 17 states have internal predecessors, (94), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) [2024-11-04 15:07:31,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:31,536 INFO L93 Difference]: Finished difference Result 221 states and 300 transitions. [2024-11-04 15:07:31,537 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 15:07:31,537 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 5.529411764705882) internal successors, (94), 17 states have internal predecessors, (94), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) Word has length 99 [2024-11-04 15:07:31,537 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:31,539 INFO L225 Difference]: With dead ends: 221 [2024-11-04 15:07:31,540 INFO L226 Difference]: Without dead ends: 142 [2024-11-04 15:07:31,541 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 181 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=76, Invalid=347, Unknown=1, NotChecked=38, Total=462 [2024-11-04 15:07:31,542 INFO L432 NwaCegarLoop]: 114 mSDtfsCounter, 67 mSDsluCounter, 990 mSDsCounter, 0 mSdLazyCounter, 382 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 1104 SdHoareTripleChecker+Invalid, 704 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 382 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 308 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:31,542 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [69 Valid, 1104 Invalid, 704 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 382 Invalid, 0 Unknown, 308 Unchecked, 0.8s Time] [2024-11-04 15:07:31,544 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-04 15:07:31,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 116. [2024-11-04 15:07:31,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 80 states have (on average 1.25) internal successors, (100), 82 states have internal predecessors, (100), 25 states have call successors, (25), 9 states have call predecessors, (25), 10 states have return successors, (27), 24 states have call predecessors, (27), 24 states have call successors, (27) [2024-11-04 15:07:31,568 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 152 transitions. [2024-11-04 15:07:31,568 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 152 transitions. Word has length 99 [2024-11-04 15:07:31,568 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:31,569 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 152 transitions. [2024-11-04 15:07:31,569 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 5.529411764705882) internal successors, (94), 17 states have internal predecessors, (94), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) [2024-11-04 15:07:31,569 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 152 transitions. [2024-11-04 15:07:31,570 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-04 15:07:31,571 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:31,571 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:07:31,593 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-04 15:07:31,775 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:31,776 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:31,776 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:31,776 INFO L85 PathProgramCache]: Analyzing trace with hash 1241226029, now seen corresponding path program 1 times [2024-11-04 15:07:31,776 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:31,777 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1140484611] [2024-11-04 15:07:31,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:31,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:31,777 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:31,778 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:31,779 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-04 15:07:31,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:31,941 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:07:31,944 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:31,959 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 47 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-04 15:07:31,959 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:32,015 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2024-11-04 15:07:32,015 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:32,015 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1140484611] [2024-11-04 15:07:32,016 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1140484611] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:32,016 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:32,016 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:07:32,016 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [650498328] [2024-11-04 15:07:32,016 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:32,016 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:07:32,016 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:32,017 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:07:32,017 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:32,017 INFO L87 Difference]: Start difference. First operand 116 states and 152 transitions. Second operand has 4 states, 4 states have (on average 14.5) internal successors, (58), 4 states have internal predecessors, (58), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 15:07:32,047 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:32,048 INFO L93 Difference]: Finished difference Result 214 states and 286 transitions. [2024-11-04 15:07:32,048 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:07:32,048 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 14.5) internal successors, (58), 4 states have internal predecessors, (58), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 99 [2024-11-04 15:07:32,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:32,050 INFO L225 Difference]: With dead ends: 214 [2024-11-04 15:07:32,050 INFO L226 Difference]: Without dead ends: 117 [2024-11-04 15:07:32,050 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 194 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-04 15:07:32,051 INFO L432 NwaCegarLoop]: 121 mSDtfsCounter, 0 mSDsluCounter, 230 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 351 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:32,051 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 351 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:32,052 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-11-04 15:07:32,059 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 116. [2024-11-04 15:07:32,060 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 80 states have (on average 1.2375) internal successors, (99), 82 states have internal predecessors, (99), 25 states have call successors, (25), 9 states have call predecessors, (25), 10 states have return successors, (27), 24 states have call predecessors, (27), 24 states have call successors, (27) [2024-11-04 15:07:32,061 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 151 transitions. [2024-11-04 15:07:32,061 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 151 transitions. Word has length 99 [2024-11-04 15:07:32,061 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:32,061 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 151 transitions. [2024-11-04 15:07:32,062 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 14.5) internal successors, (58), 4 states have internal predecessors, (58), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 15:07:32,062 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 151 transitions. [2024-11-04 15:07:32,063 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-04 15:07:32,063 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:32,063 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:07:32,084 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-04 15:07:32,263 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:32,264 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:32,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:32,264 INFO L85 PathProgramCache]: Analyzing trace with hash 1801925807, now seen corresponding path program 1 times [2024-11-04 15:07:32,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:32,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [954782404] [2024-11-04 15:07:32,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:32,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:32,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:32,266 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:32,267 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-04 15:07:32,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:32,443 INFO L255 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:07:32,445 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:32,459 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-04 15:07:32,460 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:32,539 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 0 proven. 5 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-04 15:07:32,539 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:32,540 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [954782404] [2024-11-04 15:07:32,540 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [954782404] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:32,540 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:32,540 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:07:32,540 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1984891437] [2024-11-04 15:07:32,540 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:32,541 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:07:32,542 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:32,542 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:07:32,542 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:32,543 INFO L87 Difference]: Start difference. First operand 116 states and 151 transitions. Second operand has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 15:07:32,575 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:32,576 INFO L93 Difference]: Finished difference Result 213 states and 285 transitions. [2024-11-04 15:07:32,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:07:32,578 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 99 [2024-11-04 15:07:32,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:32,579 INFO L225 Difference]: With dead ends: 213 [2024-11-04 15:07:32,579 INFO L226 Difference]: Without dead ends: 116 [2024-11-04 15:07:32,580 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 194 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-04 15:07:32,581 INFO L432 NwaCegarLoop]: 121 mSDtfsCounter, 0 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:32,581 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 352 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:32,583 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-11-04 15:07:32,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2024-11-04 15:07:32,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 77 states have (on average 1.2207792207792207) internal successors, (94), 79 states have internal predecessors, (94), 25 states have call successors, (25), 9 states have call predecessors, (25), 10 states have return successors, (27), 24 states have call predecessors, (27), 24 states have call successors, (27) [2024-11-04 15:07:32,599 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 146 transitions. [2024-11-04 15:07:32,599 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 146 transitions. Word has length 99 [2024-11-04 15:07:32,600 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:32,600 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 146 transitions. [2024-11-04 15:07:32,600 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 15:07:32,600 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 146 transitions. [2024-11-04 15:07:32,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-04 15:07:32,601 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:32,602 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:07:32,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:32,805 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:32,806 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:32,806 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:32,806 INFO L85 PathProgramCache]: Analyzing trace with hash 1707514615, now seen corresponding path program 1 times [2024-11-04 15:07:32,806 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:32,807 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1164332552] [2024-11-04 15:07:32,807 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:32,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:32,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:32,809 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:32,810 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-04 15:07:32,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:32,978 INFO L255 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:07:32,981 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:33,016 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2024-11-04 15:07:33,016 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:33,102 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2024-11-04 15:07:33,102 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:33,102 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1164332552] [2024-11-04 15:07:33,102 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1164332552] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:07:33,102 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:07:33,103 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6, 6] imperfect sequences [] total 8 [2024-11-04 15:07:33,103 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [129621123] [2024-11-04 15:07:33,103 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:33,103 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:07:33,103 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:33,104 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:07:33,104 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:33,104 INFO L87 Difference]: Start difference. First operand 113 states and 146 transitions. Second operand has 8 states, 7 states have (on average 7.0) internal successors, (49), 5 states have internal predecessors, (49), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) [2024-11-04 15:07:33,145 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:33,146 INFO L93 Difference]: Finished difference Result 123 states and 157 transitions. [2024-11-04 15:07:33,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:07:33,146 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 7.0) internal successors, (49), 5 states have internal predecessors, (49), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) Word has length 100 [2024-11-04 15:07:33,146 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:33,148 INFO L225 Difference]: With dead ends: 123 [2024-11-04 15:07:33,148 INFO L226 Difference]: Without dead ends: 121 [2024-11-04 15:07:33,148 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 192 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:07:33,149 INFO L432 NwaCegarLoop]: 118 mSDtfsCounter, 3 mSDsluCounter, 575 mSDsCounter, 0 mSdLazyCounter, 32 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 693 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 32 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:33,149 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 693 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 32 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:33,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-11-04 15:07:33,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 120. [2024-11-04 15:07:33,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 81 states have (on average 1.2098765432098766) internal successors, (98), 84 states have internal predecessors, (98), 26 states have call successors, (26), 10 states have call predecessors, (26), 12 states have return successors, (30), 25 states have call predecessors, (30), 25 states have call successors, (30) [2024-11-04 15:07:33,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 154 transitions. [2024-11-04 15:07:33,162 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 154 transitions. Word has length 100 [2024-11-04 15:07:33,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:33,162 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 154 transitions. [2024-11-04 15:07:33,163 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 7.0) internal successors, (49), 5 states have internal predecessors, (49), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) [2024-11-04 15:07:33,163 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 154 transitions. [2024-11-04 15:07:33,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2024-11-04 15:07:33,164 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:33,164 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:33,184 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:33,364 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:33,365 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:33,365 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:33,366 INFO L85 PathProgramCache]: Analyzing trace with hash 2067834226, now seen corresponding path program 1 times [2024-11-04 15:07:33,366 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:33,366 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [128379252] [2024-11-04 15:07:33,366 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:33,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:33,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:33,367 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:33,368 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-04 15:07:33,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:33,539 INFO L255 TraceCheckSpWp]: Trace formula consists of 293 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:07:33,542 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:33,589 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-04 15:07:33,589 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:33,679 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-04 15:07:33,679 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:33,679 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [128379252] [2024-11-04 15:07:33,679 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [128379252] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:07:33,679 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:07:33,680 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7, 7] imperfect sequences [] total 9 [2024-11-04 15:07:33,680 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [641543287] [2024-11-04 15:07:33,680 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:33,680 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-04 15:07:33,680 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:33,681 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-04 15:07:33,681 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:07:33,681 INFO L87 Difference]: Start difference. First operand 120 states and 154 transitions. Second operand has 9 states, 8 states have (on average 6.25) internal successors, (50), 6 states have internal predecessors, (50), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) [2024-11-04 15:07:33,737 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:33,737 INFO L93 Difference]: Finished difference Result 128 states and 162 transitions. [2024-11-04 15:07:33,738 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:07:33,738 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 6.25) internal successors, (50), 6 states have internal predecessors, (50), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) Word has length 113 [2024-11-04 15:07:33,738 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:33,739 INFO L225 Difference]: With dead ends: 128 [2024-11-04 15:07:33,740 INFO L226 Difference]: Without dead ends: 126 [2024-11-04 15:07:33,740 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 217 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 15:07:33,740 INFO L432 NwaCegarLoop]: 117 mSDtfsCounter, 3 mSDsluCounter, 801 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 918 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:33,741 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 918 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 48 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:33,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2024-11-04 15:07:33,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 118. [2024-11-04 15:07:33,749 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 80 states have (on average 1.2125) internal successors, (97), 82 states have internal predecessors, (97), 26 states have call successors, (26), 10 states have call predecessors, (26), 11 states have return successors, (28), 25 states have call predecessors, (28), 25 states have call successors, (28) [2024-11-04 15:07:33,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 151 transitions. [2024-11-04 15:07:33,750 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 151 transitions. Word has length 113 [2024-11-04 15:07:33,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:33,750 INFO L471 AbstractCegarLoop]: Abstraction has 118 states and 151 transitions. [2024-11-04 15:07:33,750 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 6.25) internal successors, (50), 6 states have internal predecessors, (50), 2 states have call successors, (14), 3 states have call predecessors, (14), 2 states have return successors, (11), 2 states have call predecessors, (11), 1 states have call successors, (11) [2024-11-04 15:07:33,750 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 151 transitions. [2024-11-04 15:07:33,751 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 15:07:33,751 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:33,752 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:33,771 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-04 15:07:33,952 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:33,952 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:33,953 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:33,953 INFO L85 PathProgramCache]: Analyzing trace with hash 1691427697, now seen corresponding path program 1 times [2024-11-04 15:07:33,953 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:33,953 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1847551813] [2024-11-04 15:07:33,953 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:33,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:33,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:33,954 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:33,955 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-04 15:07:34,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:34,126 INFO L255 TraceCheckSpWp]: Trace formula consists of 299 conjuncts, 36 conjuncts are in the unsatisfiable core [2024-11-04 15:07:34,130 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:34,204 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-04 15:07:34,206 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-04 15:07:38,582 WARN L873 $PredicateComparison]: unable to prove that (or (exists ((v_aws_linked_list_front_~list.base_BEFORE_CALL_6 (_ BitVec 64))) (not (= (select (select |c_#memory_$Pointer$#1.base| v_aws_linked_list_front_~list.base_BEFORE_CALL_6) (_ bv0 64)) v_aws_linked_list_front_~list.base_BEFORE_CALL_6))) (exists ((v_aws_linked_list_front_~list.base_BEFORE_CALL_6 (_ BitVec 64))) (not (= (_ bv16 64) (select (select |c_#memory_$Pointer$#1.offset| v_aws_linked_list_front_~list.base_BEFORE_CALL_6) (_ bv0 64)))))) is different from true [2024-11-04 15:07:39,705 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 75 proven. 5 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-11-04 15:07:39,705 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:45,882 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 6 proven. 38 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2024-11-04 15:07:45,883 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:45,883 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1847551813] [2024-11-04 15:07:45,883 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1847551813] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:07:45,883 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:07:45,883 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 31 [2024-11-04 15:07:45,883 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [367831849] [2024-11-04 15:07:45,883 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:07:45,884 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-04 15:07:45,884 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:45,884 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-04 15:07:45,885 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=780, Unknown=2, NotChecked=56, Total=930 [2024-11-04 15:07:45,885 INFO L87 Difference]: Start difference. First operand 118 states and 151 transitions. Second operand has 31 states, 27 states have (on average 5.037037037037037) internal successors, (136), 27 states have internal predecessors, (136), 14 states have call successors, (29), 5 states have call predecessors, (29), 9 states have return successors, (26), 11 states have call predecessors, (26), 12 states have call successors, (26) [2024-11-04 15:07:52,600 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:07:58,207 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:02,216 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:06,224 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:10,274 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:11,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:11,038 INFO L93 Difference]: Finished difference Result 275 states and 355 transitions. [2024-11-04 15:08:11,039 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-04 15:08:11,039 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 27 states have (on average 5.037037037037037) internal successors, (136), 27 states have internal predecessors, (136), 14 states have call successors, (29), 5 states have call predecessors, (29), 9 states have return successors, (26), 11 states have call predecessors, (26), 12 states have call successors, (26) Word has length 116 [2024-11-04 15:08:11,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:11,041 INFO L225 Difference]: With dead ends: 275 [2024-11-04 15:08:11,041 INFO L226 Difference]: Without dead ends: 158 [2024-11-04 15:08:11,042 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 240 GetRequests, 203 SyntacticMatches, 1 SemanticMatches, 36 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 208 ImplicationChecksByTransitivity, 11.9s TimeCoverageRelationStatistics Valid=140, Invalid=1194, Unknown=2, NotChecked=70, Total=1406 [2024-11-04 15:08:11,042 INFO L432 NwaCegarLoop]: 102 mSDtfsCounter, 78 mSDsluCounter, 1040 mSDsCounter, 0 mSdLazyCounter, 1161 mSolverCounterSat, 49 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 23.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 89 SdHoareTripleChecker+Valid, 1142 SdHoareTripleChecker+Invalid, 1681 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 1161 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 466 IncrementalHoareTripleChecker+Unchecked, 23.5s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:11,042 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [89 Valid, 1142 Invalid, 1681 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 1161 Invalid, 5 Unknown, 466 Unchecked, 23.5s Time] [2024-11-04 15:08:11,043 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2024-11-04 15:08:11,060 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 146. [2024-11-04 15:08:11,061 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 105 states have (on average 1.2095238095238094) internal successors, (127), 106 states have internal predecessors, (127), 28 states have call successors, (28), 12 states have call predecessors, (28), 12 states have return successors, (31), 27 states have call predecessors, (31), 27 states have call successors, (31) [2024-11-04 15:08:11,062 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 186 transitions. [2024-11-04 15:08:11,063 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 186 transitions. Word has length 116 [2024-11-04 15:08:11,063 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:11,063 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 186 transitions. [2024-11-04 15:08:11,063 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 27 states have (on average 5.037037037037037) internal successors, (136), 27 states have internal predecessors, (136), 14 states have call successors, (29), 5 states have call predecessors, (29), 9 states have return successors, (26), 11 states have call predecessors, (26), 12 states have call successors, (26) [2024-11-04 15:08:11,063 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 186 transitions. [2024-11-04 15:08:11,064 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-11-04 15:08:11,064 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:11,065 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:08:11,081 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-04 15:08:11,266 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:11,266 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:11,266 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:11,266 INFO L85 PathProgramCache]: Analyzing trace with hash -997985191, now seen corresponding path program 1 times [2024-11-04 15:08:11,266 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:11,267 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [785216832] [2024-11-04 15:08:11,267 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:11,267 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:11,267 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:11,268 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:08:11,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-04 15:08:11,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:11,432 INFO L255 TraceCheckSpWp]: Trace formula consists of 313 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-04 15:08:11,435 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:11,691 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-04 15:08:11,691 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:08:12,032 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-04 15:08:12,032 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 23 [2024-11-04 15:08:12,047 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-04 15:08:12,047 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 20 treesize of output 12 [2024-11-04 15:08:12,073 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2024-11-04 15:08:12,073 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:08:12,073 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [785216832] [2024-11-04 15:08:12,073 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [785216832] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:08:12,073 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:08:12,073 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 15:08:12,073 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1272010499] [2024-11-04 15:08:12,073 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:08:12,074 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:08:12,074 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:08:12,074 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:08:12,074 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2024-11-04 15:08:12,074 INFO L87 Difference]: Start difference. First operand 146 states and 186 transitions. Second operand has 8 states, 8 states have (on average 9.5) internal successors, (76), 7 states have internal predecessors, (76), 2 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 3 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 15:08:12,978 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:12,978 INFO L93 Difference]: Finished difference Result 276 states and 370 transitions. [2024-11-04 15:08:12,979 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 15:08:12,979 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 9.5) internal successors, (76), 7 states have internal predecessors, (76), 2 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 3 states have call predecessors, (15), 2 states have call successors, (15) Word has length 124 [2024-11-04 15:08:12,979 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:12,980 INFO L225 Difference]: With dead ends: 276 [2024-11-04 15:08:12,980 INFO L226 Difference]: Without dead ends: 176 [2024-11-04 15:08:12,981 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 251 GetRequests, 239 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-11-04 15:08:12,982 INFO L432 NwaCegarLoop]: 117 mSDtfsCounter, 15 mSDsluCounter, 596 mSDsCounter, 0 mSdLazyCounter, 215 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 713 SdHoareTripleChecker+Invalid, 215 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 215 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:12,982 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 713 Invalid, 215 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 215 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-04 15:08:12,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2024-11-04 15:08:13,004 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 155. [2024-11-04 15:08:13,004 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 113 states have (on average 1.2123893805309736) internal successors, (137), 113 states have internal predecessors, (137), 28 states have call successors, (28), 12 states have call predecessors, (28), 13 states have return successors, (35), 29 states have call predecessors, (35), 27 states have call successors, (35) [2024-11-04 15:08:13,005 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 200 transitions. [2024-11-04 15:08:13,006 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 200 transitions. Word has length 124 [2024-11-04 15:08:13,006 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:13,006 INFO L471 AbstractCegarLoop]: Abstraction has 155 states and 200 transitions. [2024-11-04 15:08:13,006 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 9.5) internal successors, (76), 7 states have internal predecessors, (76), 2 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 3 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 15:08:13,007 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 200 transitions. [2024-11-04 15:08:13,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-11-04 15:08:13,007 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:13,008 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:08:13,028 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-04 15:08:13,208 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:13,208 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:13,209 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:13,209 INFO L85 PathProgramCache]: Analyzing trace with hash -318712937, now seen corresponding path program 1 times [2024-11-04 15:08:13,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:13,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [605349785] [2024-11-04 15:08:13,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:13,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:13,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:13,211 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:08:13,211 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-04 15:08:13,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:13,378 INFO L255 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-04 15:08:13,380 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:13,395 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 56 proven. 0 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-04 15:08:13,396 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:08:13,492 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-04 15:08:13,492 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:08:13,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [605349785] [2024-11-04 15:08:13,492 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [605349785] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:08:13,492 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:08:13,492 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 5 [2024-11-04 15:08:13,493 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [12415520] [2024-11-04 15:08:13,493 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:08:13,493 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 15:08:13,493 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:08:13,494 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 15:08:13,494 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 15:08:13,494 INFO L87 Difference]: Start difference. First operand 155 states and 200 transitions. Second operand has 5 states, 5 states have (on average 14.6) internal successors, (73), 4 states have internal predecessors, (73), 2 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 3 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 15:08:13,529 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:13,529 INFO L93 Difference]: Finished difference Result 277 states and 370 transitions. [2024-11-04 15:08:13,529 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 15:08:13,529 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 14.6) internal successors, (73), 4 states have internal predecessors, (73), 2 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 3 states have call predecessors, (15), 2 states have call successors, (15) Word has length 124 [2024-11-04 15:08:13,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:13,531 INFO L225 Difference]: With dead ends: 277 [2024-11-04 15:08:13,531 INFO L226 Difference]: Without dead ends: 160 [2024-11-04 15:08:13,532 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 243 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 15:08:13,532 INFO L432 NwaCegarLoop]: 125 mSDtfsCounter, 0 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 489 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:13,532 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 489 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:08:13,533 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2024-11-04 15:08:13,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 159. [2024-11-04 15:08:13,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 159 states, 116 states have (on average 1.206896551724138) internal successors, (140), 116 states have internal predecessors, (140), 28 states have call successors, (28), 12 states have call predecessors, (28), 14 states have return successors, (39), 30 states have call predecessors, (39), 27 states have call successors, (39) [2024-11-04 15:08:13,550 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 159 states to 159 states and 207 transitions. [2024-11-04 15:08:13,551 INFO L78 Accepts]: Start accepts. Automaton has 159 states and 207 transitions. Word has length 124 [2024-11-04 15:08:13,551 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:13,551 INFO L471 AbstractCegarLoop]: Abstraction has 159 states and 207 transitions. [2024-11-04 15:08:13,552 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 14.6) internal successors, (73), 4 states have internal predecessors, (73), 2 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 3 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 15:08:13,552 INFO L276 IsEmpty]: Start isEmpty. Operand 159 states and 207 transitions. [2024-11-04 15:08:13,553 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2024-11-04 15:08:13,553 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:13,553 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:08:13,570 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-04 15:08:13,753 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:13,754 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:13,754 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:13,754 INFO L85 PathProgramCache]: Analyzing trace with hash -1052378089, now seen corresponding path program 1 times [2024-11-04 15:08:13,754 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:13,754 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1387280214] [2024-11-04 15:08:13,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:13,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:13,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:13,755 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:08:13,756 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-04 15:08:13,930 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:13,934 INFO L255 TraceCheckSpWp]: Trace formula consists of 310 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:08:13,936 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:13,946 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 58 proven. 0 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-04 15:08:13,946 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:08:14,008 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2024-11-04 15:08:14,008 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:08:14,008 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1387280214] [2024-11-04 15:08:14,008 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1387280214] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:08:14,008 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:08:14,008 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:08:14,009 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [300819467] [2024-11-04 15:08:14,009 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:08:14,009 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:08:14,009 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:08:14,010 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:08:14,010 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:08:14,010 INFO L87 Difference]: Start difference. First operand 159 states and 207 transitions. Second operand has 4 states, 4 states have (on average 18.75) internal successors, (75), 4 states have internal predecessors, (75), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 15:08:14,062 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:14,062 INFO L93 Difference]: Finished difference Result 272 states and 362 transitions. [2024-11-04 15:08:14,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:08:14,063 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 18.75) internal successors, (75), 4 states have internal predecessors, (75), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 124 [2024-11-04 15:08:14,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:14,064 INFO L225 Difference]: With dead ends: 272 [2024-11-04 15:08:14,064 INFO L226 Difference]: Without dead ends: 152 [2024-11-04 15:08:14,065 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 244 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-04 15:08:14,065 INFO L432 NwaCegarLoop]: 120 mSDtfsCounter, 0 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 351 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:14,065 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 351 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:08:14,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2024-11-04 15:08:14,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 152. [2024-11-04 15:08:14,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 152 states, 110 states have (on average 1.1818181818181819) internal successors, (130), 111 states have internal predecessors, (130), 28 states have call successors, (28), 12 states have call predecessors, (28), 13 states have return successors, (33), 28 states have call predecessors, (33), 27 states have call successors, (33) [2024-11-04 15:08:14,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 152 states to 152 states and 191 transitions. [2024-11-04 15:08:14,087 INFO L78 Accepts]: Start accepts. Automaton has 152 states and 191 transitions. Word has length 124 [2024-11-04 15:08:14,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:14,088 INFO L471 AbstractCegarLoop]: Abstraction has 152 states and 191 transitions. [2024-11-04 15:08:14,088 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 18.75) internal successors, (75), 4 states have internal predecessors, (75), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 15:08:14,088 INFO L276 IsEmpty]: Start isEmpty. Operand 152 states and 191 transitions. [2024-11-04 15:08:14,089 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 126 [2024-11-04 15:08:14,089 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:14,089 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:08:14,109 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-11-04 15:08:14,289 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:14,290 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:14,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:14,290 INFO L85 PathProgramCache]: Analyzing trace with hash -1997351601, now seen corresponding path program 1 times [2024-11-04 15:08:14,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:14,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2067115925] [2024-11-04 15:08:14,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:14,290 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:14,290 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:14,291 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:08:14,292 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-04 15:08:14,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:14,470 INFO L255 TraceCheckSpWp]: Trace formula consists of 315 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-04 15:08:14,473 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:15,988 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 50 proven. 2 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-04 15:08:15,989 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:08:18,696 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-04 15:08:18,697 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 25 [2024-11-04 15:08:18,715 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-04 15:08:18,716 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 12 [2024-11-04 15:08:18,759 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-04 15:08:18,760 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:08:18,760 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2067115925] [2024-11-04 15:08:18,760 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2067115925] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:08:18,760 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:08:18,760 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 9] total 19 [2024-11-04 15:08:18,760 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1586881258] [2024-11-04 15:08:18,760 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:08:18,761 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-04 15:08:18,761 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:08:18,762 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-04 15:08:18,762 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2024-11-04 15:08:18,762 INFO L87 Difference]: Start difference. First operand 152 states and 191 transitions. Second operand has 19 states, 18 states have (on average 5.944444444444445) internal successors, (107), 18 states have internal predecessors, (107), 8 states have call successors, (29), 5 states have call predecessors, (29), 7 states have return successors, (26), 7 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-04 15:08:23,121 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:27,380 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:31,599 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:35,608 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:40,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:40,152 INFO L93 Difference]: Finished difference Result 289 states and 357 transitions. [2024-11-04 15:08:40,153 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-04 15:08:40,153 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 18 states have (on average 5.944444444444445) internal successors, (107), 18 states have internal predecessors, (107), 8 states have call successors, (29), 5 states have call predecessors, (29), 7 states have return successors, (26), 7 states have call predecessors, (26), 8 states have call successors, (26) Word has length 125 [2024-11-04 15:08:40,153 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:40,155 INFO L225 Difference]: With dead ends: 289 [2024-11-04 15:08:40,155 INFO L226 Difference]: Without dead ends: 194 [2024-11-04 15:08:40,156 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 223 SyntacticMatches, 9 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 157 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=157, Invalid=713, Unknown=0, NotChecked=0, Total=870 [2024-11-04 15:08:40,158 INFO L432 NwaCegarLoop]: 113 mSDtfsCounter, 153 mSDsluCounter, 703 mSDsCounter, 0 mSdLazyCounter, 462 mSolverCounterSat, 76 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 19.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 154 SdHoareTripleChecker+Valid, 816 SdHoareTripleChecker+Invalid, 542 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 76 IncrementalHoareTripleChecker+Valid, 462 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.2s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:40,158 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [154 Valid, 816 Invalid, 542 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [76 Valid, 462 Invalid, 4 Unknown, 0 Unchecked, 20.2s Time] [2024-11-04 15:08:40,159 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 194 states. [2024-11-04 15:08:40,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 194 to 190. [2024-11-04 15:08:40,180 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 190 states, 141 states have (on average 1.1560283687943262) internal successors, (163), 144 states have internal predecessors, (163), 29 states have call successors, (29), 16 states have call predecessors, (29), 19 states have return successors, (36), 29 states have call predecessors, (36), 28 states have call successors, (36) [2024-11-04 15:08:40,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 228 transitions. [2024-11-04 15:08:40,182 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 228 transitions. Word has length 125 [2024-11-04 15:08:40,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:40,182 INFO L471 AbstractCegarLoop]: Abstraction has 190 states and 228 transitions. [2024-11-04 15:08:40,183 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 18 states have (on average 5.944444444444445) internal successors, (107), 18 states have internal predecessors, (107), 8 states have call successors, (29), 5 states have call predecessors, (29), 7 states have return successors, (26), 7 states have call predecessors, (26), 8 states have call successors, (26) [2024-11-04 15:08:40,183 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 228 transitions. [2024-11-04 15:08:40,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 126 [2024-11-04 15:08:40,184 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:40,184 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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-04 15:08:40,206 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-04 15:08:40,384 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:40,385 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:40,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:40,385 INFO L85 PathProgramCache]: Analyzing trace with hash -1778496883, now seen corresponding path program 1 times [2024-11-04 15:08:40,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:40,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [980918263] [2024-11-04 15:08:40,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:40,386 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:40,386 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:40,387 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:08:40,388 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-04 15:08:40,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:40,615 INFO L255 TraceCheckSpWp]: Trace formula consists of 312 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-04 15:08:40,618 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:40,909 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 7 [2024-11-04 15:08:40,935 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-04 15:08:40,936 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 1 [2024-11-04 15:08:43,893 INFO L134 CoverageAnalysis]: Checked inductivity of 93 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-11-04 15:08:43,893 INFO L311 TraceCheckSpWp]: Computing backward predicates...