/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 'cvc4 --incremental --print-success --lang smt' -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf -i ../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_back_harness_negated.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 20:46:11,666 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 20:46:11,728 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 20:46:11,733 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 20:46:11,733 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 20:46:11,765 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 20:46:11,766 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 20:46:11,766 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 20:46:11,767 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 20:46:11,767 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 20:46:11,768 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 20:46:11,769 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 20:46:11,770 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 20:46:11,774 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 20:46:11,774 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 20:46:11,774 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 20:46:11,775 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 20:46:11,775 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 20:46:11,775 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 20:46:11,775 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 20:46:11,776 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 20:46:11,776 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 20:46:11,776 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 20:46:11,777 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 20:46:11,777 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 20:46:11,777 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 20:46:11,777 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 20:46:11,778 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 20:46:11,778 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 20:46:11,778 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 20:46:11,779 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 20:46:11,779 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:46:11,781 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 20:46:11,782 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 20:46:11,782 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 20:46:11,782 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 20:46:11,782 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:11,782 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 20:46:11,783 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 20:46:11,783 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 20:46:11,783 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 20:46:11,783 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 -> cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:12,046 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 20:46:12,074 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 20:46:12,078 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 20:46:12,079 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 20:46:12,080 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 20:46:12,081 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_back_harness_negated.i [2024-11-04 20:46:13,576 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 20:46:14,040 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 20:46:14,041 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_back_harness_negated.i [2024-11-04 20:46:14,085 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5e8dc4c7d/3ad8718e134d4beabfefc944c783a7fd/FLAGd02a89dd2 [2024-11-04 20:46:14,110 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5e8dc4c7d/3ad8718e134d4beabfefc944c783a7fd [2024-11-04 20:46:14,113 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 20:46:14,114 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 20:46:14,118 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 20:46:14,119 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 20:46:14,124 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 20:46:14,125 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:46:14" (1/1) ... [2024-11-04 20:46:14,126 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@126ba38d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:14, skipping insertion in model container [2024-11-04 20:46:14,126 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:46:14" (1/1) ... [2024-11-04 20:46:14,224 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:46:14,622 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_back_harness_negated.i[4494,4507] [2024-11-04 20:46:14,634 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_back_harness_negated.i[4554,4567] [2024-11-04 20:46:15,758 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 20:46:15,956 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 20:46:15,957 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 20:46:15,958 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 20:46:15,969 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 20:46:15,972 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:15,973 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:15,973 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:15,974 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 20:46:15,974 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:15,975 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:15,979 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 20:46:15,979 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 20:46:15,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 20:46:15,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 20:46:15,996 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:15,996 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 20:46:15,997 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:15,997 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 20:46:16,000 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:16,000 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 20:46:16,001 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:16,001 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 20:46:16,003 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:16,005 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 20:46:16,005 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:16,005 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 20:46:16,006 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:16,006 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:16,744 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 20:46:16,745 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 20:46:16,746 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 20:46:16,746 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 20:46:17,131 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 20:46:17,152 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:46:17,189 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 20:46:17,253 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:46:17,259 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_back_harness_negated.i[4494,4507] [2024-11-04 20:46:17,260 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_back_harness_negated.i[4554,4567] [2024-11-04 20:46:17,293 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 20:46:17,318 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 20:46:17,321 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 20:46:17,322 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 20:46:17,330 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 20:46:17,336 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,336 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,337 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,337 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 20:46:17,337 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,338 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,343 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 20:46:17,344 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 20:46:17,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 20:46:17,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 20:46:17,358 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,359 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 20:46:17,359 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,359 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 20:46:17,362 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,363 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 20:46:17,363 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,363 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 20:46:17,365 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,368 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 20:46:17,368 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,369 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 20:46:17,369 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,369 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,447 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 20:46:17,448 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 20:46:17,448 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 20:46:17,449 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 20:46:17,493 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 20:46:17,505 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:46:17,515 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 20:46:17,534 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_back_harness_negated.i[4494,4507] [2024-11-04 20:46:17,535 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_back_harness_negated.i[4554,4567] [2024-11-04 20:46:17,598 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,599 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,599 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,600 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,600 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,606 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,607 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,608 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,608 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,609 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,609 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,610 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,610 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:46:17,708 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:46:17,928 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 20:46:17,940 INFO L204 MainTranslator]: Completed translation [2024-11-04 20:46:17,940 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17 WrapperNode [2024-11-04 20:46:17,941 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 20:46:17,942 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 20:46:17,942 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 20:46:17,942 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 20:46:17,949 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,027 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,074 INFO L138 Inliner]: procedures = 687, calls = 1043, calls flagged for inlining = 50, calls inlined = 5, statements flattened = 136 [2024-11-04 20:46:18,074 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 20:46:18,075 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 20:46:18,075 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 20:46:18,075 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 20:46:18,088 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,088 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,097 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,135 INFO L175 MemorySlicer]: Split 27 memory accesses to 3 slices as follows [2, 5, 20]. 74 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0]. The 6 writes are split as follows [0, 0, 6]. [2024-11-04 20:46:18,136 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,136 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,149 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,157 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,170 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,177 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,192 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 20:46:18,194 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 20:46:18,194 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 20:46:18,195 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 20:46:18,196 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (1/1) ... [2024-11-04 20:46:18,203 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:46:18,215 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 20:46:18,234 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 20:46:18,238 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 20:46:18,268 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_back [2024-11-04 20:46:18,269 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_back [2024-11-04 20:46:18,269 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 20:46:18,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 20:46:18,269 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 20:46:18,270 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 20:46:18,270 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 20:46:18,270 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 20:46:18,270 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:46:18,271 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:46:18,271 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-04 20:46:18,271 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-04 20:46:18,271 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-04 20:46:18,272 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 20:46:18,272 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 20:46:18,272 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 20:46:18,272 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 20:46:18,272 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 20:46:18,272 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 20:46:18,272 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2024-11-04 20:46:18,272 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2024-11-04 20:46:18,272 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 20:46:18,273 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 20:46:18,273 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 20:46:18,273 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 20:46:18,273 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 20:46:18,274 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 20:46:18,274 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 20:46:18,274 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 20:46:18,274 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 20:46:18,274 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-04 20:46:18,275 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-04 20:46:18,275 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2024-11-04 20:46:18,275 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2024-11-04 20:46:18,572 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 20:46:18,575 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 20:46:19,136 INFO L? ?]: Removed 61 outVars from TransFormulas that were not future-live. [2024-11-04 20:46:19,136 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 20:46:19,155 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 20:46:19,156 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-04 20:46:19,156 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:46:19 BoogieIcfgContainer [2024-11-04 20:46:19,156 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 20:46:19,159 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 20:46:19,159 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 20:46:19,162 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 20:46:19,163 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 08:46:14" (1/3) ... [2024-11-04 20:46:19,164 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@16bb353c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:46:19, skipping insertion in model container [2024-11-04 20:46:19,164 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:46:17" (2/3) ... [2024-11-04 20:46:19,164 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@16bb353c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:46:19, skipping insertion in model container [2024-11-04 20:46:19,164 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:46:19" (3/3) ... [2024-11-04 20:46:19,166 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_back_harness_negated.i [2024-11-04 20:46:19,185 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 20:46:19,185 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 20:46:19,273 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 20:46:19,281 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;@2c3cbe4e, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 20:46:19,281 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 20:46:19,287 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 20:46:19,299 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-04 20:46:19,300 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:19,301 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 20:46:19,302 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:19,311 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:19,312 INFO L85 PathProgramCache]: Analyzing trace with hash -722894815, now seen corresponding path program 1 times [2024-11-04 20:46:19,322 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:19,325 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1684641825] [2024-11-04 20:46:19,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:19,329 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:19,330 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:19,334 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:19,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (2)] Waiting until timeout for monitored process [2024-11-04 20:46:19,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:19,674 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 20:46:19,682 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:19,718 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 21 proven. 0 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2024-11-04 20:46:19,718 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:19,837 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 20:46:19,838 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:19,838 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1684641825] [2024-11-04 20:46:19,839 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1684641825] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:46:19,839 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:46:19,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 2 [2024-11-04 20:46:19,842 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1731179917] [2024-11-04 20:46:19,843 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:19,848 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 20:46:19,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:19,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 20:46:19,873 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 20:46:19,875 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 22.0) internal successors, (44), 2 states have internal predecessors, (44), 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 20:46:19,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:19,908 INFO L93 Difference]: Finished difference Result 188 states and 271 transitions. [2024-11-04 20:46:19,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 20:46:19,910 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 22.0) internal successors, (44), 2 states have internal predecessors, (44), 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 84 [2024-11-04 20:46:19,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:19,919 INFO L225 Difference]: With dead ends: 188 [2024-11-04 20:46:19,919 INFO L226 Difference]: Without dead ends: 93 [2024-11-04 20:46:19,923 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 20:46:19,931 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 20:46:19,933 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 20:46:19,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-11-04 20:46:19,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-11-04 20:46:19,985 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 20:46:19,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 122 transitions. [2024-11-04 20:46:19,991 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 122 transitions. Word has length 84 [2024-11-04 20:46:19,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:19,991 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 122 transitions. [2024-11-04 20:46:19,992 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 22.0) internal successors, (44), 2 states have internal predecessors, (44), 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 20:46:19,992 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 122 transitions. [2024-11-04 20:46:19,995 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-04 20:46:19,995 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:19,996 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 20:46:20,001 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (2)] Ended with exit code 0 [2024-11-04 20:46:20,196 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:20,197 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:20,198 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:20,198 INFO L85 PathProgramCache]: Analyzing trace with hash -723996839, now seen corresponding path program 1 times [2024-11-04 20:46:20,198 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:20,198 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [94230745] [2024-11-04 20:46:20,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:20,199 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:20,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:20,202 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:20,203 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (3)] Waiting until timeout for monitored process [2024-11-04 20:46:20,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:20,715 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 20:46:20,721 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:20,802 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 20:46:20,802 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:20,930 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 20:46:20,930 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:20,931 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [94230745] [2024-11-04 20:46:20,931 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [94230745] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:46:20,931 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:46:20,931 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 20:46:20,931 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1112762475] [2024-11-04 20:46:20,931 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:20,932 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:46:20,933 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:20,936 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:46:20,937 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:46:20,937 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 20:46:21,021 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:21,021 INFO L93 Difference]: Finished difference Result 169 states and 224 transitions. [2024-11-04 20:46:21,023 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:46:21,024 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 20:46:21,024 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:21,027 INFO L225 Difference]: With dead ends: 169 [2024-11-04 20:46:21,027 INFO L226 Difference]: Without dead ends: 95 [2024-11-04 20:46:21,028 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 20:46:21,029 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 20:46:21,029 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 20:46:21,030 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-04 20:46:21,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2024-11-04 20:46:21,049 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 20:46:21,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 125 transitions. [2024-11-04 20:46:21,052 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 125 transitions. Word has length 84 [2024-11-04 20:46:21,052 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:21,053 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 125 transitions. [2024-11-04 20:46:21,053 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 20:46:21,053 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 125 transitions. [2024-11-04 20:46:21,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-11-04 20:46:21,059 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:21,060 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 20:46:21,071 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (3)] Forceful destruction successful, exit code 0 [2024-11-04 20:46:21,260 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:21,261 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:21,261 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:21,262 INFO L85 PathProgramCache]: Analyzing trace with hash 2086865941, now seen corresponding path program 1 times [2024-11-04 20:46:21,262 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:21,262 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1999982760] [2024-11-04 20:46:21,262 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:21,262 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:21,262 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:21,265 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:21,267 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (4)] Waiting until timeout for monitored process [2024-11-04 20:46:21,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:21,512 INFO L255 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 20:46:21,518 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:21,629 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 20:46:21,629 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:21,809 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 20:46:21,809 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:21,809 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1999982760] [2024-11-04 20:46:21,809 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1999982760] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:46:21,810 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:46:21,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 10 [2024-11-04 20:46:21,810 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [43801742] [2024-11-04 20:46:21,810 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:21,810 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:46:21,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:21,811 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:46:21,811 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-04 20:46:21,812 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 20:46:22,008 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:22,009 INFO L93 Difference]: Finished difference Result 176 states and 233 transitions. [2024-11-04 20:46:22,009 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 20:46:22,010 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 20:46:22,010 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:22,011 INFO L225 Difference]: With dead ends: 176 [2024-11-04 20:46:22,011 INFO L226 Difference]: Without dead ends: 97 [2024-11-04 20:46:22,012 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 20:46:22,013 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 20:46:22,013 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 20:46:22,014 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2024-11-04 20:46:22,024 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 95. [2024-11-04 20:46:22,024 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 20:46:22,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 124 transitions. [2024-11-04 20:46:22,026 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 124 transitions. Word has length 86 [2024-11-04 20:46:22,026 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:22,026 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 124 transitions. [2024-11-04 20:46:22,027 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 20:46:22,027 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 124 transitions. [2024-11-04 20:46:22,028 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2024-11-04 20:46:22,028 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:22,028 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 20:46:22,033 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (4)] Forceful destruction successful, exit code 0 [2024-11-04 20:46:22,229 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:22,230 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:22,230 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:22,230 INFO L85 PathProgramCache]: Analyzing trace with hash 1429995906, now seen corresponding path program 1 times [2024-11-04 20:46:22,230 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:22,230 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1988519211] [2024-11-04 20:46:22,231 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:22,231 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:22,231 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:22,232 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:22,233 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (5)] Waiting until timeout for monitored process [2024-11-04 20:46:22,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:22,456 INFO L255 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 20:46:22,460 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:22,591 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 20:46:22,591 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:22,812 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 20:46:22,812 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:22,812 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1988519211] [2024-11-04 20:46:22,812 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1988519211] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:46:22,812 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:46:22,812 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 12 [2024-11-04 20:46:22,813 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [690548834] [2024-11-04 20:46:22,813 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:22,813 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-04 20:46:22,813 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:22,814 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-04 20:46:22,814 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-04 20:46:22,814 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 20:46:23,068 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:23,068 INFO L93 Difference]: Finished difference Result 182 states and 241 transitions. [2024-11-04 20:46:23,071 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-04 20:46:23,071 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 20:46:23,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:23,073 INFO L225 Difference]: With dead ends: 182 [2024-11-04 20:46:23,073 INFO L226 Difference]: Without dead ends: 102 [2024-11-04 20:46:23,074 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 20:46:23,080 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 20:46:23,080 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 20:46:23,081 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-11-04 20:46:23,096 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 96. [2024-11-04 20:46:23,097 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 20:46:23,099 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 125 transitions. [2024-11-04 20:46:23,099 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 125 transitions. Word has length 88 [2024-11-04 20:46:23,103 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:23,103 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 125 transitions. [2024-11-04 20:46:23,103 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 20:46:23,104 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 125 transitions. [2024-11-04 20:46:23,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-04 20:46:23,105 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:23,105 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 20:46:23,111 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (5)] Forceful destruction successful, exit code 0 [2024-11-04 20:46:23,305 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:23,306 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:23,306 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:23,306 INFO L85 PathProgramCache]: Analyzing trace with hash -1848432154, now seen corresponding path program 1 times [2024-11-04 20:46:23,306 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:23,306 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1668980982] [2024-11-04 20:46:23,307 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:23,307 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:23,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:23,308 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:23,309 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (6)] Waiting until timeout for monitored process [2024-11-04 20:46:23,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:23,528 INFO L255 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-04 20:46:23,533 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:23,653 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 20:46:23,653 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:23,730 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 20:46:23,730 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:23,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1668980982] [2024-11-04 20:46:23,731 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1668980982] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:46:23,731 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:46:23,731 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [3] total 9 [2024-11-04 20:46:23,731 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1772274064] [2024-11-04 20:46:23,731 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:23,732 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:46:23,732 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:23,733 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:46:23,733 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-04 20:46:23,733 INFO L87 Difference]: Start difference. First operand 96 states and 125 transitions. Second operand has 8 states, 7 states have (on average 7.428571428571429) internal successors, (52), 7 states have internal predecessors, (52), 4 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:46:23,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:23,934 INFO L93 Difference]: Finished difference Result 179 states and 238 transitions. [2024-11-04 20:46:23,934 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 20:46:23,935 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 7.428571428571429) internal successors, (52), 7 states have internal predecessors, (52), 4 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 89 [2024-11-04 20:46:23,935 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:23,937 INFO L225 Difference]: With dead ends: 179 [2024-11-04 20:46:23,937 INFO L226 Difference]: Without dead ends: 102 [2024-11-04 20:46:23,937 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 177 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-04 20:46:23,942 INFO L432 NwaCegarLoop]: 105 mSDtfsCounter, 34 mSDsluCounter, 552 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 657 SdHoareTripleChecker+Invalid, 131 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:46:23,942 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 657 Invalid, 131 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:46:23,943 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-11-04 20:46:23,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 97. [2024-11-04 20:46:23,959 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 20:46:23,961 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 126 transitions. [2024-11-04 20:46:23,961 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 126 transitions. Word has length 89 [2024-11-04 20:46:23,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:23,962 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 126 transitions. [2024-11-04 20:46:23,962 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 7.428571428571429) internal successors, (52), 7 states have internal predecessors, (52), 4 states have call successors, (13), 3 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:46:23,962 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 126 transitions. [2024-11-04 20:46:23,964 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-11-04 20:46:23,965 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:23,965 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 20:46:23,970 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (6)] Forceful destruction successful, exit code 0 [2024-11-04 20:46:24,165 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:24,166 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:24,166 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:24,166 INFO L85 PathProgramCache]: Analyzing trace with hash -2017477272, now seen corresponding path program 1 times [2024-11-04 20:46:24,166 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:24,167 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1064744263] [2024-11-04 20:46:24,167 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:24,167 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:24,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:24,170 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:24,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Waiting until timeout for monitored process [2024-11-04 20:46:24,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:24,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 20:46:24,528 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:24,575 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 20:46:24,575 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:24,670 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 20:46:24,670 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:24,670 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1064744263] [2024-11-04 20:46:24,670 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1064744263] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:46:24,670 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:46:24,671 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 20:46:24,671 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [262127368] [2024-11-04 20:46:24,671 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:24,671 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:46:24,671 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:24,672 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:46:24,672 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:46:24,672 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 20:46:24,740 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:24,740 INFO L93 Difference]: Finished difference Result 178 states and 233 transitions. [2024-11-04 20:46:24,740 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:46:24,741 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 20:46:24,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:24,742 INFO L225 Difference]: With dead ends: 178 [2024-11-04 20:46:24,742 INFO L226 Difference]: Without dead ends: 100 [2024-11-04 20:46:24,743 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 20:46:24,744 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 20:46:24,744 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 20:46:24,745 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-04 20:46:24,760 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 98. [2024-11-04 20:46:24,760 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 20:46:24,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 127 transitions. [2024-11-04 20:46:24,762 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 127 transitions. Word has length 97 [2024-11-04 20:46:24,762 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:24,762 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 127 transitions. [2024-11-04 20:46:24,762 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 20:46:24,762 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 127 transitions. [2024-11-04 20:46:24,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-04 20:46:24,763 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:24,764 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 20:46:24,773 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Forceful destruction successful, exit code 0 [2024-11-04 20:46:24,969 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:24,970 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:24,970 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:24,970 INFO L85 PathProgramCache]: Analyzing trace with hash -63854059, now seen corresponding path program 1 times [2024-11-04 20:46:24,970 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:24,970 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1301840035] [2024-11-04 20:46:24,970 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:24,971 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:24,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:24,972 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:24,973 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (8)] Waiting until timeout for monitored process [2024-11-04 20:46:25,469 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:25,474 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-04 20:46:25,478 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:25,775 INFO L349 Elim1Store]: treesize reduction 42, result has 31.1 percent of original size [2024-11-04 20:46:25,775 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 52 treesize of output 80 [2024-11-04 20:46:25,947 INFO L349 Elim1Store]: treesize reduction 42, result has 31.1 percent of original size [2024-11-04 20:46:25,947 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 52 treesize of output 80 [2024-11-04 20:46:25,992 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 16 treesize of output 15 [2024-11-04 20:46:26,022 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 16 treesize of output 15 [2024-11-04 20:46:26,058 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-04 20:46:26,059 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 16 treesize of output 1 [2024-11-04 20:46:26,122 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-04 20:46:26,123 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 16 treesize of output 1 [2024-11-04 20:46:26,336 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-04 20:46:26,346 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2024-11-04 20:46:26,379 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-04 20:46:26,383 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 39 treesize of output 22 [2024-11-04 20:46:30,976 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 (= (select (select |c_#memory_$Pointer$#2.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|) (_ bv0 64)))) (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$#2.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|))))) is different from true [2024-11-04 20:46:31,291 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 20:46:31,291 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:31,786 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 20:46:31,786 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:31,786 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1301840035] [2024-11-04 20:46:31,786 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1301840035] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:46:31,787 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:46:31,787 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 8] total 20 [2024-11-04 20:46:31,787 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [823116111] [2024-11-04 20:46:31,787 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:46:31,787 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2024-11-04 20:46:31,788 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:31,788 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2024-11-04 20:46:31,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=294, Unknown=1, NotChecked=34, Total=380 [2024-11-04 20:46:31,789 INFO L87 Difference]: Start difference. First operand 98 states and 127 transitions. Second operand has 20 states, 19 states have (on average 5.105263157894737) internal successors, (97), 19 states have internal predecessors, (97), 7 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-04 20:46:33,184 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:33,185 INFO L93 Difference]: Finished difference Result 221 states and 300 transitions. [2024-11-04 20:46:33,185 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-04 20:46:33,186 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 19 states have (on average 5.105263157894737) internal successors, (97), 19 states have internal predecessors, (97), 7 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) Word has length 99 [2024-11-04 20:46:33,186 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:33,189 INFO L225 Difference]: With dead ends: 221 [2024-11-04 20:46:33,189 INFO L226 Difference]: Without dead ends: 142 [2024-11-04 20:46:33,191 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 204 GetRequests, 179 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=87, Invalid=516, Unknown=1, NotChecked=46, Total=650 [2024-11-04 20:46:33,192 INFO L432 NwaCegarLoop]: 110 mSDtfsCounter, 80 mSDsluCounter, 1149 mSDsCounter, 0 mSdLazyCounter, 458 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 91 SdHoareTripleChecker+Valid, 1259 SdHoareTripleChecker+Invalid, 831 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 458 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 335 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:46:33,193 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [91 Valid, 1259 Invalid, 831 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 458 Invalid, 0 Unknown, 335 Unchecked, 1.1s Time] [2024-11-04 20:46:33,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-04 20:46:33,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 116. [2024-11-04 20:46:33,208 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 20:46:33,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 152 transitions. [2024-11-04 20:46:33,210 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 152 transitions. Word has length 99 [2024-11-04 20:46:33,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:33,210 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 152 transitions. [2024-11-04 20:46:33,211 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 19 states have (on average 5.105263157894737) internal successors, (97), 19 states have internal predecessors, (97), 7 states have call successors, (25), 4 states have call predecessors, (25), 3 states have return successors, (22), 6 states have call predecessors, (22), 7 states have call successors, (22) [2024-11-04 20:46:33,211 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 152 transitions. [2024-11-04 20:46:33,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-04 20:46:33,212 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:33,212 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 20:46:33,222 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (8)] Forceful destruction successful, exit code 0 [2024-11-04 20:46:33,413 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:33,413 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:33,414 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:33,414 INFO L85 PathProgramCache]: Analyzing trace with hash 1897720599, now seen corresponding path program 1 times [2024-11-04 20:46:33,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:33,414 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [112543526] [2024-11-04 20:46:33,414 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:33,414 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:33,414 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:33,416 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:33,417 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Waiting until timeout for monitored process [2024-11-04 20:46:33,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:33,636 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 20:46:33,639 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:33,654 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 20:46:33,654 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:33,718 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 20:46:33,718 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:33,718 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [112543526] [2024-11-04 20:46:33,718 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [112543526] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:46:33,718 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:46:33,718 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 20:46:33,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [607355421] [2024-11-04 20:46:33,719 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:33,719 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 20:46:33,719 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:33,720 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 20:46:33,720 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 20:46:33,720 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 20:46:33,751 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:33,751 INFO L93 Difference]: Finished difference Result 214 states and 286 transitions. [2024-11-04 20:46:33,752 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 20:46:33,752 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 20:46:33,753 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:33,754 INFO L225 Difference]: With dead ends: 214 [2024-11-04 20:46:33,754 INFO L226 Difference]: Without dead ends: 117 [2024-11-04 20:46:33,755 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 20:46:33,755 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 20:46:33,756 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 20:46:33,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-11-04 20:46:33,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 116. [2024-11-04 20:46:33,767 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 20:46:33,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 151 transitions. [2024-11-04 20:46:33,769 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 151 transitions. Word has length 99 [2024-11-04 20:46:33,769 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:33,769 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 151 transitions. [2024-11-04 20:46:33,769 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 20:46:33,769 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 151 transitions. [2024-11-04 20:46:33,770 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-04 20:46:33,770 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:33,771 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 20:46:33,777 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Ended with exit code 0 [2024-11-04 20:46:33,971 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:33,971 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:33,972 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:33,972 INFO L85 PathProgramCache]: Analyzing trace with hash -1836546919, now seen corresponding path program 1 times [2024-11-04 20:46:33,972 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:33,972 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1786287422] [2024-11-04 20:46:33,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:33,972 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:33,973 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:33,974 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:33,975 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (10)] Waiting until timeout for monitored process [2024-11-04 20:46:34,198 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:34,203 INFO L255 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-04 20:46:34,206 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:34,225 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 20:46:34,226 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:34,290 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 20:46:34,290 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:34,290 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1786287422] [2024-11-04 20:46:34,290 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1786287422] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:46:34,290 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:46:34,290 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 5 [2024-11-04 20:46:34,291 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [271962392] [2024-11-04 20:46:34,291 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:46:34,291 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 20:46:34,291 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:34,292 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 20:46:34,292 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:46:34,292 INFO L87 Difference]: Start difference. First operand 116 states and 151 transitions. Second operand has 5 states, 5 states have (on average 12.0) internal successors, (60), 5 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 20:46:34,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:46:34,337 INFO L93 Difference]: Finished difference Result 213 states and 285 transitions. [2024-11-04 20:46:34,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 20:46:34,338 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 12.0) internal successors, (60), 5 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 20:46:34,338 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:46:34,340 INFO L225 Difference]: With dead ends: 213 [2024-11-04 20:46:34,340 INFO L226 Difference]: Without dead ends: 116 [2024-11-04 20:46:34,340 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 193 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 20:46:34,341 INFO L432 NwaCegarLoop]: 121 mSDtfsCounter, 0 mSDsluCounter, 346 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 467 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:46:34,341 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 467 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:46:34,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-11-04 20:46:34,356 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2024-11-04 20:46:34,356 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 20:46:34,357 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 146 transitions. [2024-11-04 20:46:34,358 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 146 transitions. Word has length 99 [2024-11-04 20:46:34,358 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:46:34,358 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 146 transitions. [2024-11-04 20:46:34,358 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 12.0) internal successors, (60), 5 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 20:46:34,358 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 146 transitions. [2024-11-04 20:46:34,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-04 20:46:34,359 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:46:34,359 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 20:46:34,365 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (10)] Ended with exit code 0 [2024-11-04 20:46:34,560 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:34,560 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:46:34,561 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:46:34,561 INFO L85 PathProgramCache]: Analyzing trace with hash -913140813, now seen corresponding path program 1 times [2024-11-04 20:46:34,561 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:46:34,561 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [7707755] [2024-11-04 20:46:34,561 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:46:34,561 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:46:34,562 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:46:34,567 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:46:34,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Waiting until timeout for monitored process [2024-11-04 20:46:35,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:46:35,027 INFO L255 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-04 20:46:35,031 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:46:35,219 INFO L349 Elim1Store]: treesize reduction 34, result has 35.8 percent of original size [2024-11-04 20:46:35,219 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 44 treesize of output 72 [2024-11-04 20:46:35,238 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 12 treesize of output 11 [2024-11-04 20:46:35,255 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-04 20:46:35,256 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 12 treesize of output 1 [2024-11-04 20:46:35,304 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 9 [2024-11-04 20:46:35,307 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2024-11-04 20:46:37,065 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 50 proven. 2 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-04 20:46:37,066 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:46:38,783 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-04 20:46:38,784 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 20:46:38,918 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2024-11-04 20:46:38,918 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:46:38,918 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [7707755] [2024-11-04 20:46:38,919 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [7707755] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:46:38,919 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:46:38,919 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 9] total 21 [2024-11-04 20:46:38,919 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1075920397] [2024-11-04 20:46:38,919 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:46:38,919 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-04 20:46:38,920 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:46:38,920 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-04 20:46:38,921 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=351, Unknown=0, NotChecked=0, Total=420 [2024-11-04 20:46:38,921 INFO L87 Difference]: Start difference. First operand 113 states and 146 transitions. Second operand has 21 states, 20 states have (on average 4.8) internal successors, (96), 20 states have internal predecessors, (96), 9 states have call successors, (25), 5 states have call predecessors, (25), 6 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-04 20:46:43,076 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 20:46:47,212 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 20:46:51,423 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 20:46:55,444 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:47:00,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:47:00,790 INFO L93 Difference]: Finished difference Result 272 states and 345 transitions. [2024-11-04 20:47:00,790 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-04 20:47:00,791 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 4.8) internal successors, (96), 20 states have internal predecessors, (96), 9 states have call successors, (25), 5 states have call predecessors, (25), 6 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 100 [2024-11-04 20:47:00,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:47:00,793 INFO L225 Difference]: With dead ends: 272 [2024-11-04 20:47:00,793 INFO L226 Difference]: Without dead ends: 181 [2024-11-04 20:47:00,794 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 212 GetRequests, 173 SyntacticMatches, 7 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 226 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=191, Invalid=931, Unknown=0, NotChecked=0, Total=1122 [2024-11-04 20:47:00,795 INFO L432 NwaCegarLoop]: 119 mSDtfsCounter, 179 mSDsluCounter, 792 mSDsCounter, 0 mSdLazyCounter, 508 mSolverCounterSat, 91 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 19.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 180 SdHoareTripleChecker+Valid, 911 SdHoareTripleChecker+Invalid, 603 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 91 IncrementalHoareTripleChecker+Valid, 508 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 20.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:47:00,796 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [180 Valid, 911 Invalid, 603 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [91 Valid, 508 Invalid, 4 Unknown, 0 Unchecked, 20.2s Time] [2024-11-04 20:47:00,797 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2024-11-04 20:47:00,814 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 174. [2024-11-04 20:47:00,815 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 129 states have (on average 1.2170542635658914) internal successors, (157), 131 states have internal predecessors, (157), 28 states have call successors, (28), 15 states have call predecessors, (28), 16 states have return successors, (31), 27 states have call predecessors, (31), 27 states have call successors, (31) [2024-11-04 20:47:00,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 216 transitions. [2024-11-04 20:47:00,816 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 216 transitions. Word has length 100 [2024-11-04 20:47:00,817 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:47:00,817 INFO L471 AbstractCegarLoop]: Abstraction has 174 states and 216 transitions. [2024-11-04 20:47:00,817 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 4.8) internal successors, (96), 20 states have internal predecessors, (96), 9 states have call successors, (25), 5 states have call predecessors, (25), 6 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-04 20:47:00,817 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 216 transitions. [2024-11-04 20:47:00,818 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-04 20:47:00,818 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:47:00,818 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, 1] [2024-11-04 20:47:00,828 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Forceful destruction successful, exit code 0 [2024-11-04 20:47:01,019 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:47:01,019 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:47:01,020 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:47:01,020 INFO L85 PathProgramCache]: Analyzing trace with hash -1722487439, now seen corresponding path program 1 times [2024-11-04 20:47:01,020 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:47:01,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [28214179] [2024-11-04 20:47:01,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:47:01,020 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:47:01,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:47:01,021 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:47:01,022 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Waiting until timeout for monitored process [2024-11-04 20:47:01,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:47:01,398 INFO L255 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-04 20:47:01,402 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:47:01,640 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 12 [2024-11-04 20:47:01,653 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 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 20:47:04,221 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 25 proven. 0 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2024-11-04 20:47:04,221 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:47:05,355 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 20:47:05,356 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 250 treesize of output 245 [2024-11-04 20:47:05,373 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 172 treesize of output 156 [2024-11-04 20:47:05,584 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 18 [2024-11-04 20:47:05,656 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-04 20:47:05,721 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-04 20:47:06,201 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2024-11-04 20:47:06,201 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:47:06,201 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [28214179] [2024-11-04 20:47:06,201 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [28214179] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:47:06,202 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:47:06,202 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12, 11] imperfect sequences [] total 21 [2024-11-04 20:47:06,202 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [95846963] [2024-11-04 20:47:06,202 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:47:06,202 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-04 20:47:06,203 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:47:06,203 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-04 20:47:06,203 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=355, Unknown=0, NotChecked=0, Total=420 [2024-11-04 20:47:06,204 INFO L87 Difference]: Start difference. First operand 174 states and 216 transitions. Second operand has 21 states, 21 states have (on average 4.714285714285714) internal successors, (99), 19 states have internal predecessors, (99), 9 states have call successors, (25), 5 states have call predecessors, (25), 4 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-04 20:47:10,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:47:10,823 INFO L93 Difference]: Finished difference Result 428 states and 536 transitions. [2024-11-04 20:47:10,824 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-04 20:47:10,824 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 4.714285714285714) internal successors, (99), 19 states have internal predecessors, (99), 9 states have call successors, (25), 5 states have call predecessors, (25), 4 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) Word has length 100 [2024-11-04 20:47:10,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:47:10,826 INFO L225 Difference]: With dead ends: 428 [2024-11-04 20:47:10,826 INFO L226 Difference]: Without dead ends: 338 [2024-11-04 20:47:10,827 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 207 GetRequests, 168 SyntacticMatches, 12 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 210 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=126, Invalid=686, Unknown=0, NotChecked=0, Total=812 [2024-11-04 20:47:10,828 INFO L432 NwaCegarLoop]: 87 mSDtfsCounter, 125 mSDsluCounter, 620 mSDsCounter, 0 mSdLazyCounter, 558 mSolverCounterSat, 80 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 141 SdHoareTripleChecker+Valid, 707 SdHoareTripleChecker+Invalid, 638 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Valid, 558 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.7s IncrementalHoareTripleChecker+Time [2024-11-04 20:47:10,828 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [141 Valid, 707 Invalid, 638 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 558 Invalid, 0 Unknown, 0 Unchecked, 3.7s Time] [2024-11-04 20:47:10,829 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 338 states. [2024-11-04 20:47:10,853 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 338 to 188. [2024-11-04 20:47:10,853 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 138 states have (on average 1.1956521739130435) internal successors, (165), 141 states have internal predecessors, (165), 31 states have call successors, (31), 17 states have call predecessors, (31), 18 states have return successors, (34), 29 states have call predecessors, (34), 30 states have call successors, (34) [2024-11-04 20:47:10,854 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 230 transitions. [2024-11-04 20:47:10,855 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 230 transitions. Word has length 100 [2024-11-04 20:47:10,855 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:47:10,855 INFO L471 AbstractCegarLoop]: Abstraction has 188 states and 230 transitions. [2024-11-04 20:47:10,856 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 4.714285714285714) internal successors, (99), 19 states have internal predecessors, (99), 9 states have call successors, (25), 5 states have call predecessors, (25), 4 states have return successors, (22), 9 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-04 20:47:10,856 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 230 transitions. [2024-11-04 20:47:10,857 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-04 20:47:10,857 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:47:10,857 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, 1] [2024-11-04 20:47:10,864 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Forceful destruction successful, exit code 0 [2024-11-04 20:47:11,057 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:47:11,058 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:47:11,058 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:47:11,058 INFO L85 PathProgramCache]: Analyzing trace with hash -2115514449, now seen corresponding path program 1 times [2024-11-04 20:47:11,058 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:47:11,058 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [332901324] [2024-11-04 20:47:11,058 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:47:11,058 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:47:11,059 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:47:11,060 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:47:11,060 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (13)] Waiting until timeout for monitored process [2024-11-04 20:47:11,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:47:11,468 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 29 conjuncts are in the unsatisfiable core [2024-11-04 20:47:11,472 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:47:11,805 INFO L349 Elim1Store]: treesize reduction 34, result has 35.8 percent of original size [2024-11-04 20:47:11,805 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 44 treesize of output 72 [2024-11-04 20:47:11,831 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 12 treesize of output 11 [2024-11-04 20:47:11,844 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-04 20:47:11,844 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 12 treesize of output 1 [2024-11-04 20:47:11,891 WARN L214 Elim1Store]: Array PQE input equivalent to false [2024-11-04 20:47:11,904 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2024-11-04 20:47:16,091 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 47 proven. 5 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-04 20:47:16,092 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:47:18,736 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-04 20:47:18,737 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 20:47:19,035 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2024-11-04 20:47:19,035 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:47:19,035 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [332901324] [2024-11-04 20:47:19,035 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [332901324] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:47:19,035 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:47:19,035 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 11] total 25 [2024-11-04 20:47:19,035 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1037490248] [2024-11-04 20:47:19,036 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:47:19,036 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-04 20:47:19,036 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:47:19,037 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-04 20:47:19,037 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=513, Unknown=0, NotChecked=0, Total=600 [2024-11-04 20:47:19,037 INFO L87 Difference]: Start difference. First operand 188 states and 230 transitions. Second operand has 25 states, 24 states have (on average 3.875) internal successors, (93), 24 states have internal predecessors, (93), 9 states have call successors, (25), 5 states have call predecessors, (25), 6 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-04 20:47:23,351 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 20:47:27,593 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 20:47:31,886 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 20:47:35,905 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:47:43,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:47:43,061 INFO L93 Difference]: Finished difference Result 278 states and 343 transitions. [2024-11-04 20:47:43,062 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-04 20:47:43,062 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 3.875) internal successors, (93), 24 states have internal predecessors, (93), 9 states have call successors, (25), 5 states have call predecessors, (25), 6 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) Word has length 100 [2024-11-04 20:47:43,063 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:47:43,064 INFO L225 Difference]: With dead ends: 278 [2024-11-04 20:47:43,064 INFO L226 Difference]: Without dead ends: 195 [2024-11-04 20:47:43,065 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 216 GetRequests, 169 SyntacticMatches, 7 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 348 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=278, Invalid=1444, Unknown=0, NotChecked=0, Total=1722 [2024-11-04 20:47:43,065 INFO L432 NwaCegarLoop]: 114 mSDtfsCounter, 181 mSDsluCounter, 1387 mSDsCounter, 0 mSdLazyCounter, 992 mSolverCounterSat, 88 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 21.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 182 SdHoareTripleChecker+Valid, 1501 SdHoareTripleChecker+Invalid, 1084 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 992 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 22.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:47:43,065 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [182 Valid, 1501 Invalid, 1084 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 992 Invalid, 4 Unknown, 0 Unchecked, 22.0s Time] [2024-11-04 20:47:43,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 195 states. [2024-11-04 20:47:43,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 195 to 188. [2024-11-04 20:47:43,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 188 states, 138 states have (on average 1.1884057971014492) internal successors, (164), 141 states have internal predecessors, (164), 31 states have call successors, (31), 17 states have call predecessors, (31), 18 states have return successors, (34), 29 states have call predecessors, (34), 30 states have call successors, (34) [2024-11-04 20:47:43,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 188 states to 188 states and 229 transitions. [2024-11-04 20:47:43,091 INFO L78 Accepts]: Start accepts. Automaton has 188 states and 229 transitions. Word has length 100 [2024-11-04 20:47:43,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:47:43,091 INFO L471 AbstractCegarLoop]: Abstraction has 188 states and 229 transitions. [2024-11-04 20:47:43,091 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 3.875) internal successors, (93), 24 states have internal predecessors, (93), 9 states have call successors, (25), 5 states have call predecessors, (25), 6 states have return successors, (22), 8 states have call predecessors, (22), 8 states have call successors, (22) [2024-11-04 20:47:43,091 INFO L276 IsEmpty]: Start isEmpty. Operand 188 states and 229 transitions. [2024-11-04 20:47:43,092 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-04 20:47:43,092 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:47:43,092 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, 1] [2024-11-04 20:47:43,101 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (13)] Ended with exit code 0 [2024-11-04 20:47:43,293 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:47:43,293 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:47:43,293 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:47:43,294 INFO L85 PathProgramCache]: Analyzing trace with hash -1857349011, now seen corresponding path program 1 times [2024-11-04 20:47:43,294 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:47:43,294 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1964050905] [2024-11-04 20:47:43,294 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:47:43,294 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:47:43,294 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:47:43,297 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:47:43,297 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (14)] Waiting until timeout for monitored process [2024-11-04 20:47:43,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:47:43,643 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-04 20:47:43,646 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:47:43,847 INFO L349 Elim1Store]: treesize reduction 42, result has 31.1 percent of original size [2024-11-04 20:47:43,848 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 52 treesize of output 80 [2024-11-04 20:47:43,871 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 16 treesize of output 15 [2024-11-04 20:47:43,900 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-04 20:47:43,901 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 16 treesize of output 1 [2024-11-04 20:47:43,962 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 13 [2024-11-04 20:47:43,968 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9