/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 --cacsl2boogietranslator.allow.undefined.functions true --traceabstraction.trace.refinement.strategy FOX -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf -i ../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_back_harness.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-17387ad-m [2024-11-06 14:20:25,532 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-06 14:20:25,601 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-06 14:20:25,606 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-06 14:20:25,607 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-06 14:20:25,632 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-06 14:20:25,632 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-06 14:20:25,633 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-06 14:20:25,633 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-06 14:20:25,633 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-06 14:20:25,633 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-06 14:20:25,634 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-06 14:20:25,634 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-06 14:20:25,634 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-06 14:20:25,635 INFO L153 SettingsManager]: * Use SBE=true [2024-11-06 14:20:25,635 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-06 14:20:25,635 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-06 14:20:25,636 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-06 14:20:25,636 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-06 14:20:25,636 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-06 14:20:25,636 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-06 14:20:25,637 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-06 14:20:25,637 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-06 14:20:25,637 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-06 14:20:25,637 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-06 14:20:25,638 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-06 14:20:25,638 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-06 14:20:25,638 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-06 14:20:25,638 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-06 14:20:25,639 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-06 14:20:25,639 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-06 14:20:25,639 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 14:20:25,639 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-06 14:20:25,639 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-06 14:20:25,640 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-06 14:20:25,640 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-06 14:20:25,640 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-06 14:20:25,640 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-06 14:20:25,641 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-06 14:20:25,641 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-06 14:20:25,641 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-06 14:20:25,641 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.cacsl2boogietranslator: Allow undefined functions -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Trace refinement strategy -> FOX [2024-11-06 14:20:25,828 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-06 14:20:25,846 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-06 14:20:25,849 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-06 14:20:25,850 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-06 14:20:25,850 INFO L274 PluginConnector]: CDTParser initialized [2024-11-06 14:20:25,851 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.i [2024-11-06 14:20:27,176 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-06 14:20:27,511 INFO L384 CDTParser]: Found 1 translation units. [2024-11-06 14:20:27,512 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_back_harness.i [2024-11-06 14:20:27,536 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c6ebf34bd/18d4217a88a640d6a4e35932dcc96eac/FLAG8925c1d05 [2024-11-06 14:20:27,554 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c6ebf34bd/18d4217a88a640d6a4e35932dcc96eac [2024-11-06 14:20:27,556 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-06 14:20:27,557 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-06 14:20:27,558 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-06 14:20:27,558 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-06 14:20:27,564 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-06 14:20:27,564 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 02:20:27" (1/1) ... [2024-11-06 14:20:27,565 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2ad2423d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:27, skipping insertion in model container [2024-11-06 14:20:27,565 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.11 02:20:27" (1/1) ... [2024-11-06 14:20:27,638 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 14:20:27,883 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.i[4494,4507] [2024-11-06 14:20:27,891 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.i[4554,4567] [2024-11-06 14:20:28,450 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-06 14:20:28,571 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-06 14:20:28,572 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-06 14:20:28,573 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-06 14:20:28,581 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-06 14:20:28,583 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,584 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,584 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,586 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-06 14:20:28,586 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,586 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,589 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-06 14:20:28,589 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-06 14:20:28,591 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-06 14:20:28,591 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-06 14:20:28,597 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,598 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-06 14:20:28,598 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,598 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-06 14:20:28,600 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,601 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-06 14:20:28,601 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,602 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-06 14:20:28,603 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,604 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-06 14:20:28,604 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,604 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-06 14:20:28,605 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:28,605 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,038 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-06 14:20:29,039 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-06 14:20:29,040 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-06 14:20:29,040 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-06 14:20:29,246 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-06 14:20:29,276 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 14:20:29,307 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-06 14:20:29,335 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-06 14:20:29,340 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.i[4494,4507] [2024-11-06 14:20:29,341 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.i[4554,4567] [2024-11-06 14:20:29,364 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-06 14:20:29,377 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-06 14:20:29,377 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-06 14:20:29,377 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-06 14:20:29,382 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-06 14:20:29,383 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,383 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,383 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,383 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-06 14:20:29,384 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,384 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,385 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-06 14:20:29,385 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-06 14:20:29,386 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-06 14:20:29,386 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-06 14:20:29,389 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,389 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-06 14:20:29,389 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,390 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-06 14:20:29,390 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,390 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-06 14:20:29,391 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,391 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-06 14:20:29,391 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,392 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-06 14:20:29,392 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,392 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-06 14:20:29,392 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,393 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,450 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-06 14:20:29,450 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-06 14:20:29,450 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-06 14:20:29,451 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-06 14:20:29,481 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-06 14:20:29,489 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 14:20:29,497 INFO L200 MainTranslator]: Completed pre-run [2024-11-06 14:20:29,509 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.i[4494,4507] [2024-11-06 14:20:29,510 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.i[4554,4567] [2024-11-06 14:20:29,540 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,541 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,541 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,541 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,541 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,546 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,546 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,546 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,547 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,547 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,547 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,548 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,548 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-06 14:20:29,604 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-06 14:20:29,726 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-06 14:20:29,736 INFO L204 MainTranslator]: Completed translation [2024-11-06 14:20:29,736 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29 WrapperNode [2024-11-06 14:20:29,736 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-06 14:20:29,737 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-06 14:20:29,737 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-06 14:20:29,737 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-06 14:20:29,742 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,813 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,857 INFO L138 Inliner]: procedures = 687, calls = 1043, calls flagged for inlining = 50, calls inlined = 5, statements flattened = 136 [2024-11-06 14:20:29,858 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-06 14:20:29,859 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-06 14:20:29,859 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-06 14:20:29,859 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-06 14:20:29,869 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,869 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,874 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,905 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-06 14:20:29,905 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,905 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,921 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,924 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,932 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,934 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,940 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-06 14:20:29,941 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-06 14:20:29,941 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-06 14:20:29,941 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-06 14:20:29,941 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (1/1) ... [2024-11-06 14:20:29,950 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-06 14:20:29,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:29,983 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-06 14:20:29,991 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-06 14:20:30,017 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_back [2024-11-06 14:20:30,017 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_back [2024-11-06 14:20:30,017 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-06 14:20:30,017 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-06 14:20:30,017 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-06 14:20:30,017 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-06 14:20:30,017 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-06 14:20:30,018 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-06 14:20:30,018 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-06 14:20:30,018 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-06 14:20:30,018 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-06 14:20:30,018 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-06 14:20:30,018 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-06 14:20:30,019 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-06 14:20:30,019 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-06 14:20:30,019 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-06 14:20:30,019 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-06 14:20:30,019 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-06 14:20:30,019 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-06 14:20:30,019 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2024-11-06 14:20:30,020 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-06 14:20:30,020 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-06 14:20:30,020 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-06 14:20:30,020 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-06 14:20:30,021 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2024-11-06 14:20:30,021 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2024-11-06 14:20:30,309 INFO L238 CfgBuilder]: Building ICFG [2024-11-06 14:20:30,312 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-06 14:20:30,551 INFO L? ?]: Removed 61 outVars from TransFormulas that were not future-live. [2024-11-06 14:20:30,551 INFO L287 CfgBuilder]: Performing block encoding [2024-11-06 14:20:30,566 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-06 14:20:30,566 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-06 14:20:30,566 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 02:20:30 BoogieIcfgContainer [2024-11-06 14:20:30,567 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-06 14:20:30,568 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-06 14:20:30,568 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-06 14:20:30,570 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-06 14:20:30,570 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.11 02:20:27" (1/3) ... [2024-11-06 14:20:30,571 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@308edc8b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 02:20:30, skipping insertion in model container [2024-11-06 14:20:30,571 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.11 02:20:29" (2/3) ... [2024-11-06 14:20:30,571 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@308edc8b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.11 02:20:30, skipping insertion in model container [2024-11-06 14:20:30,571 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.11 02:20:30" (3/3) ... [2024-11-06 14:20:30,572 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_back_harness.i [2024-11-06 14:20:30,582 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-06 14:20:30,583 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-06 14:20:30,643 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-06 14:20:30,650 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;@4538da1c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-06 14:20:30,651 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-06 14:20:30,655 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-06 14:20:30,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-06 14:20:30,671 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:30,671 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-06 14:20:30,671 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:30,679 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:30,680 INFO L85 PathProgramCache]: Analyzing trace with hash -722894815, now seen corresponding path program 1 times [2024-11-06 14:20:30,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:30,695 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [405496722] [2024-11-06 14:20:30,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:30,698 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:30,698 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:30,701 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:30,703 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-06 14:20:30,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:30,936 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-06 14:20:30,945 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:30,988 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-06 14:20:30,988 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:30,988 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:30,989 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [405496722] [2024-11-06 14:20:30,989 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [405496722] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:30,989 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:30,989 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-06 14:20:30,994 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2039484905] [2024-11-06 14:20:30,995 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:31,001 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-06 14:20:31,002 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:31,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-06 14:20:31,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-06 14:20:31,033 INFO L87 Difference]: Start difference. First operand has 98 states, 64 states have (on average 1.296875) internal successors, (83), 65 states have internal predecessors, (83), 24 states have call successors, (24), 8 states have call predecessors, (24), 8 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand has 2 states, 2 states have (on average 17.0) internal successors, (34), 2 states have internal predecessors, (34), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-06 14:20:31,059 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:31,059 INFO L93 Difference]: Finished difference Result 188 states and 271 transitions. [2024-11-06 14:20:31,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-06 14:20:31,062 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 17.0) internal successors, (34), 2 states have internal predecessors, (34), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 84 [2024-11-06 14:20:31,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:31,068 INFO L225 Difference]: With dead ends: 188 [2024-11-06 14:20:31,068 INFO L226 Difference]: Without dead ends: 93 [2024-11-06 14:20:31,071 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 83 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-06 14:20:31,076 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-06 14:20:31,078 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-06 14:20:31,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2024-11-06 14:20:31,111 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2024-11-06 14:20:31,113 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-06 14:20:31,120 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 122 transitions. [2024-11-06 14:20:31,121 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 122 transitions. Word has length 84 [2024-11-06 14:20:31,121 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:31,121 INFO L471 AbstractCegarLoop]: Abstraction has 93 states and 122 transitions. [2024-11-06 14:20:31,121 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 17.0) internal successors, (34), 2 states have internal predecessors, (34), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2024-11-06 14:20:31,121 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 122 transitions. [2024-11-06 14:20:31,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2024-11-06 14:20:31,125 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:31,125 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-06 14:20:31,144 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-06 14:20:31,329 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:31,330 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:31,331 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:31,331 INFO L85 PathProgramCache]: Analyzing trace with hash -723996839, now seen corresponding path program 1 times [2024-11-06 14:20:31,333 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:31,333 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1322182961] [2024-11-06 14:20:31,333 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:31,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:31,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:31,339 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:31,340 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-06 14:20:31,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:31,591 INFO L255 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-06 14:20:31,598 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:31,689 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-06 14:20:31,689 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:31,690 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:31,690 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1322182961] [2024-11-06 14:20:31,690 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1322182961] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:31,690 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:31,690 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-06 14:20:31,690 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [984803910] [2024-11-06 14:20:31,690 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:31,695 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-06 14:20:31,695 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:31,695 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-06 14:20:31,695 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-06 14:20:31,696 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-06 14:20:31,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:31,744 INFO L93 Difference]: Finished difference Result 169 states and 224 transitions. [2024-11-06 14:20:31,745 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-06 14:20:31,745 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-06 14:20:31,745 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:31,747 INFO L225 Difference]: With dead ends: 169 [2024-11-06 14:20:31,747 INFO L226 Difference]: Without dead ends: 95 [2024-11-06 14:20:31,748 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-06 14:20:31,749 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.0s IncrementalHoareTripleChecker+Time [2024-11-06 14:20:31,749 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.0s Time] [2024-11-06 14:20:31,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2024-11-06 14:20:31,756 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2024-11-06 14:20:31,756 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-06 14:20:31,758 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 125 transitions. [2024-11-06 14:20:31,758 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 125 transitions. Word has length 84 [2024-11-06 14:20:31,758 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:31,758 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 125 transitions. [2024-11-06 14:20:31,758 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-06 14:20:31,758 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 125 transitions. [2024-11-06 14:20:31,760 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2024-11-06 14:20:31,760 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:31,760 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-06 14:20:31,776 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-06 14:20:31,964 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:31,964 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:31,965 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:31,965 INFO L85 PathProgramCache]: Analyzing trace with hash 2086865941, now seen corresponding path program 1 times [2024-11-06 14:20:31,966 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:31,966 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1312941150] [2024-11-06 14:20:31,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:31,966 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:31,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:31,967 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:31,968 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-06 14:20:32,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:32,118 INFO L255 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-06 14:20:32,123 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:32,232 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-06 14:20:32,232 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:32,232 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:32,232 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1312941150] [2024-11-06 14:20:32,232 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1312941150] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:32,233 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:32,233 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-06 14:20:32,233 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1228242519] [2024-11-06 14:20:32,233 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:32,236 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-06 14:20:32,236 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:32,236 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-06 14:20:32,237 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2024-11-06 14:20:32,237 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-06 14:20:32,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:32,404 INFO L93 Difference]: Finished difference Result 176 states and 233 transitions. [2024-11-06 14:20:32,406 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-06 14:20:32,407 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-06 14:20:32,407 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:32,408 INFO L225 Difference]: With dead ends: 176 [2024-11-06 14:20:32,408 INFO L226 Difference]: Without dead ends: 97 [2024-11-06 14:20:32,409 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-06 14:20:32,409 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.1s IncrementalHoareTripleChecker+Time [2024-11-06 14:20:32,409 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.1s Time] [2024-11-06 14:20:32,410 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2024-11-06 14:20:32,425 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 95. [2024-11-06 14:20:32,426 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-06 14:20:32,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 124 transitions. [2024-11-06 14:20:32,427 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 124 transitions. Word has length 86 [2024-11-06 14:20:32,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:32,428 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 124 transitions. [2024-11-06 14:20:32,428 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-06 14:20:32,428 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 124 transitions. [2024-11-06 14:20:32,429 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2024-11-06 14:20:32,430 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:32,430 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-06 14:20:32,448 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-06 14:20:32,636 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:32,637 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:32,638 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:32,638 INFO L85 PathProgramCache]: Analyzing trace with hash 1429995906, now seen corresponding path program 1 times [2024-11-06 14:20:32,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:32,640 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1135506379] [2024-11-06 14:20:32,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:32,641 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:32,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:32,642 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:32,644 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-06 14:20:32,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:32,790 INFO L255 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-06 14:20:32,793 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:32,882 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-06 14:20:32,882 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:32,882 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:32,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1135506379] [2024-11-06 14:20:32,883 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1135506379] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:32,883 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:32,883 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2024-11-06 14:20:32,883 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [491597574] [2024-11-06 14:20:32,883 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:32,883 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-06 14:20:32,883 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:32,884 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-06 14:20:32,884 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2024-11-06 14:20:32,884 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-06 14:20:33,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:33,157 INFO L93 Difference]: Finished difference Result 182 states and 241 transitions. [2024-11-06 14:20:33,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-06 14:20:33,163 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-06 14:20:33,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:33,164 INFO L225 Difference]: With dead ends: 182 [2024-11-06 14:20:33,164 INFO L226 Difference]: Without dead ends: 102 [2024-11-06 14:20:33,165 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-06 14:20:33,165 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-06 14:20:33,166 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-06 14:20:33,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2024-11-06 14:20:33,187 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 96. [2024-11-06 14:20:33,187 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-06 14:20:33,188 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 125 transitions. [2024-11-06 14:20:33,188 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 125 transitions. Word has length 88 [2024-11-06 14:20:33,188 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:33,188 INFO L471 AbstractCegarLoop]: Abstraction has 96 states and 125 transitions. [2024-11-06 14:20:33,189 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-06 14:20:33,189 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 125 transitions. [2024-11-06 14:20:33,193 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-06 14:20:33,193 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:33,193 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-06 14:20:33,215 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-06 14:20:33,393 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:33,394 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:33,394 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:33,394 INFO L85 PathProgramCache]: Analyzing trace with hash -1848432154, now seen corresponding path program 1 times [2024-11-06 14:20:33,395 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:33,395 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1195851055] [2024-11-06 14:20:33,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:33,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:33,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:33,397 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:33,398 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-06 14:20:33,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:33,572 INFO L255 TraceCheckSpWp]: Trace formula consists of 234 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-06 14:20:33,575 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:33,600 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-06 14:20:33,601 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:33,601 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:33,601 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1195851055] [2024-11-06 14:20:33,601 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1195851055] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:33,601 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:33,601 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-06 14:20:33,601 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [413797673] [2024-11-06 14:20:33,602 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:33,602 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-06 14:20:33,602 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:33,603 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-06 14:20:33,603 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-06 14:20:33,603 INFO L87 Difference]: Start difference. First operand 96 states and 125 transitions. Second operand has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-06 14:20:33,630 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:33,630 INFO L93 Difference]: Finished difference Result 177 states and 236 transitions. [2024-11-06 14:20:33,633 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-06 14:20:33,633 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 89 [2024-11-06 14:20:33,634 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:33,635 INFO L225 Difference]: With dead ends: 177 [2024-11-06 14:20:33,635 INFO L226 Difference]: Without dead ends: 100 [2024-11-06 14:20:33,636 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 87 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-06 14:20:33,636 INFO L432 NwaCegarLoop]: 118 mSDtfsCounter, 2 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 231 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 14:20:33,636 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 231 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 14:20:33,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-06 14:20:33,644 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 97. [2024-11-06 14:20:33,645 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-06 14:20:33,645 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 126 transitions. [2024-11-06 14:20:33,646 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 126 transitions. Word has length 89 [2024-11-06 14:20:33,646 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:33,646 INFO L471 AbstractCegarLoop]: Abstraction has 97 states and 126 transitions. [2024-11-06 14:20:33,646 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.333333333333332) internal successors, (52), 3 states have internal predecessors, (52), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-06 14:20:33,646 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 126 transitions. [2024-11-06 14:20:33,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2024-11-06 14:20:33,648 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:33,648 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-06 14:20:33,668 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-06 14:20:33,848 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:33,849 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:33,849 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:33,849 INFO L85 PathProgramCache]: Analyzing trace with hash -2017477272, now seen corresponding path program 1 times [2024-11-06 14:20:33,850 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:33,850 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1708378706] [2024-11-06 14:20:33,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:33,851 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:33,851 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:33,852 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:33,853 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-06 14:20:34,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:34,015 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-06 14:20:34,018 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:34,054 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-06 14:20:34,054 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:34,054 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:34,054 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1708378706] [2024-11-06 14:20:34,054 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1708378706] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:34,055 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:34,055 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2024-11-06 14:20:34,055 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1137376618] [2024-11-06 14:20:34,055 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:34,055 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-06 14:20:34,055 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:34,056 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-06 14:20:34,056 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-06 14:20:34,056 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-06 14:20:34,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:34,117 INFO L93 Difference]: Finished difference Result 178 states and 233 transitions. [2024-11-06 14:20:34,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-06 14:20:34,118 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-06 14:20:34,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:34,119 INFO L225 Difference]: With dead ends: 178 [2024-11-06 14:20:34,120 INFO L226 Difference]: Without dead ends: 100 [2024-11-06 14:20:34,120 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 91 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-06 14:20:34,121 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.0s IncrementalHoareTripleChecker+Time [2024-11-06 14:20:34,121 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.0s Time] [2024-11-06 14:20:34,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-06 14:20:34,129 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 98. [2024-11-06 14:20:34,129 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-06 14:20:34,130 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 127 transitions. [2024-11-06 14:20:34,130 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 127 transitions. Word has length 97 [2024-11-06 14:20:34,130 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:34,131 INFO L471 AbstractCegarLoop]: Abstraction has 98 states and 127 transitions. [2024-11-06 14:20:34,131 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-06 14:20:34,131 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 127 transitions. [2024-11-06 14:20:34,132 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-06 14:20:34,132 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:34,132 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-06 14:20:34,150 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-06 14:20:34,333 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:34,333 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:34,334 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:34,334 INFO L85 PathProgramCache]: Analyzing trace with hash -63854059, now seen corresponding path program 1 times [2024-11-06 14:20:34,334 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:34,334 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [475146452] [2024-11-06 14:20:34,334 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:34,335 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:34,335 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:34,336 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:34,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-06 14:20:34,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:34,489 INFO L255 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-06 14:20:34,493 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:34,559 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 13 treesize of output 1 [2024-11-06 14:20:34,563 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 13 treesize of output 1 [2024-11-06 14:20:38,906 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-06 14:20:39,119 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-06 14:20:39,119 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 14:20:39,398 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-06 14:20:39,398 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:39,399 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [475146452] [2024-11-06 14:20:39,399 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [475146452] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 14:20:39,399 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 14:20:39,399 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2024-11-06 14:20:39,399 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2095035873] [2024-11-06 14:20:39,399 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 14:20:39,399 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-06 14:20:39,399 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:39,400 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-06 14:20:39,400 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=199, Unknown=1, NotChecked=28, Total=272 [2024-11-06 14:20:39,400 INFO L87 Difference]: Start difference. First operand 98 states and 127 transitions. Second operand has 17 states, 17 states have (on average 5.529411764705882) internal successors, (94), 17 states have internal predecessors, (94), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) [2024-11-06 14:20:40,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:40,075 INFO L93 Difference]: Finished difference Result 221 states and 300 transitions. [2024-11-06 14:20:40,076 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-06 14:20:40,076 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 5.529411764705882) internal successors, (94), 17 states have internal predecessors, (94), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) Word has length 99 [2024-11-06 14:20:40,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:40,078 INFO L225 Difference]: With dead ends: 221 [2024-11-06 14:20:40,078 INFO L226 Difference]: Without dead ends: 142 [2024-11-06 14:20:40,078 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 181 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=76, Invalid=347, Unknown=1, NotChecked=38, Total=462 [2024-11-06 14:20:40,079 INFO L432 NwaCegarLoop]: 117 mSDtfsCounter, 66 mSDsluCounter, 812 mSDsCounter, 0 mSdLazyCounter, 316 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 929 SdHoareTripleChecker+Invalid, 637 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 316 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 308 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-06 14:20:40,079 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 929 Invalid, 637 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 316 Invalid, 0 Unknown, 308 Unchecked, 0.5s Time] [2024-11-06 14:20:40,080 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-06 14:20:40,096 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 116. [2024-11-06 14:20:40,097 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-06 14:20:40,098 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 152 transitions. [2024-11-06 14:20:40,098 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 152 transitions. Word has length 99 [2024-11-06 14:20:40,102 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:40,102 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 152 transitions. [2024-11-06 14:20:40,102 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 5.529411764705882) internal successors, (94), 17 states have internal predecessors, (94), 5 states have call successors, (21), 3 states have call predecessors, (21), 3 states have return successors, (19), 5 states have call predecessors, (19), 5 states have call successors, (19) [2024-11-06 14:20:40,103 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 152 transitions. [2024-11-06 14:20:40,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-06 14:20:40,103 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:40,104 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-06 14:20:40,120 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-06 14:20:40,304 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:40,304 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:40,304 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:40,304 INFO L85 PathProgramCache]: Analyzing trace with hash 1897720599, now seen corresponding path program 1 times [2024-11-06 14:20:40,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:40,305 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1330772451] [2024-11-06 14:20:40,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:40,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:40,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:40,307 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:40,308 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-06 14:20:40,433 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:40,435 INFO L255 TraceCheckSpWp]: Trace formula consists of 255 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-06 14:20:40,437 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:40,449 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-06 14:20:40,449 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:40,449 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:40,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1330772451] [2024-11-06 14:20:40,449 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1330772451] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:40,449 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:40,449 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-06 14:20:40,449 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1862361193] [2024-11-06 14:20:40,450 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:40,450 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-06 14:20:40,450 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:40,450 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-06 14:20:40,450 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-06 14:20:40,451 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-06 14:20:40,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:40,475 INFO L93 Difference]: Finished difference Result 214 states and 286 transitions. [2024-11-06 14:20:40,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-06 14:20:40,476 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-06 14:20:40,476 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:40,477 INFO L225 Difference]: With dead ends: 214 [2024-11-06 14:20:40,477 INFO L226 Difference]: Without dead ends: 117 [2024-11-06 14:20:40,478 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 96 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-06 14:20:40,478 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-06 14:20:40,478 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-06 14:20:40,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 117 states. [2024-11-06 14:20:40,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 117 to 116. [2024-11-06 14:20:40,492 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-06 14:20:40,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 151 transitions. [2024-11-06 14:20:40,493 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 151 transitions. Word has length 99 [2024-11-06 14:20:40,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:40,493 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 151 transitions. [2024-11-06 14:20:40,493 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-06 14:20:40,493 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 151 transitions. [2024-11-06 14:20:40,494 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 100 [2024-11-06 14:20:40,494 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:40,494 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-06 14:20:40,515 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-06 14:20:40,700 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:40,701 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:40,701 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:40,701 INFO L85 PathProgramCache]: Analyzing trace with hash -1836546919, now seen corresponding path program 1 times [2024-11-06 14:20:40,701 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:40,702 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [369735633] [2024-11-06 14:20:40,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:40,702 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:40,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:40,703 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:40,704 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-06 14:20:40,826 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:40,828 INFO L255 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-06 14:20:40,830 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:40,847 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-06 14:20:40,847 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:20:40,847 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:40,847 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [369735633] [2024-11-06 14:20:40,847 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [369735633] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:20:40,847 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:20:40,848 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-06 14:20:40,848 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1683320869] [2024-11-06 14:20:40,848 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:20:40,848 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-06 14:20:40,848 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:40,848 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-06 14:20:40,849 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-06 14:20:40,849 INFO L87 Difference]: Start difference. First operand 116 states and 151 transitions. Second operand has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-06 14:20:40,868 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:20:40,868 INFO L93 Difference]: Finished difference Result 213 states and 285 transitions. [2024-11-06 14:20:40,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-06 14:20:40,868 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 99 [2024-11-06 14:20:40,869 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:20:40,869 INFO L225 Difference]: With dead ends: 213 [2024-11-06 14:20:40,869 INFO L226 Difference]: Without dead ends: 116 [2024-11-06 14:20:40,870 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 96 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-06 14:20:40,870 INFO L432 NwaCegarLoop]: 121 mSDtfsCounter, 0 mSDsluCounter, 231 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 352 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-06 14:20:40,870 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 352 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-06 14:20:40,871 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2024-11-06 14:20:40,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 113. [2024-11-06 14:20:40,883 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-06 14:20:40,884 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 146 transitions. [2024-11-06 14:20:40,884 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 146 transitions. Word has length 99 [2024-11-06 14:20:40,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:20:40,884 INFO L471 AbstractCegarLoop]: Abstraction has 113 states and 146 transitions. [2024-11-06 14:20:40,884 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 15.0) internal successors, (60), 4 states have internal predecessors, (60), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-06 14:20:40,884 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 146 transitions. [2024-11-06 14:20:40,885 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-06 14:20:40,885 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:20:40,885 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-06 14:20:40,919 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-06 14:20:41,089 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:41,090 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:20:41,090 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:20:41,090 INFO L85 PathProgramCache]: Analyzing trace with hash -913140813, now seen corresponding path program 1 times [2024-11-06 14:20:41,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:20:41,091 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [907025502] [2024-11-06 14:20:41,091 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:20:41,091 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:20:41,091 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:20:41,092 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:20:41,093 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-06 14:20:41,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:20:41,241 INFO L255 TraceCheckSpWp]: Trace formula consists of 260 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-06 14:20:41,245 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:20:41,291 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-06 14:20:41,294 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-06 14:20:42,460 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-06 14:20:42,460 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 14:20:43,146 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-06 14:20:43,146 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:20:43,146 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [907025502] [2024-11-06 14:20:43,146 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [907025502] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 14:20:43,146 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 14:20:43,146 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 9] total 21 [2024-11-06 14:20:43,146 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1644302131] [2024-11-06 14:20:43,147 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 14:20:43,147 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-06 14:20:43,147 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:20:43,148 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-06 14:20:43,148 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2024-11-06 14:20:43,148 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-06 14:20:47,548 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-06 14:20:51,768 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-06 14:20:55,896 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-06 14:20:59,923 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.03s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-06 14:21:03,059 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:21:03,059 INFO L93 Difference]: Finished difference Result 272 states and 345 transitions. [2024-11-06 14:21:03,060 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-06 14:21:03,061 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-06 14:21:03,061 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:21:03,062 INFO L225 Difference]: With dead ends: 272 [2024-11-06 14:21:03,062 INFO L226 Difference]: Without dead ends: 181 [2024-11-06 14:21:03,063 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 212 GetRequests, 173 SyntacticMatches, 7 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 226 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=191, Invalid=931, Unknown=0, NotChecked=0, Total=1122 [2024-11-06 14:21:03,063 INFO L432 NwaCegarLoop]: 119 mSDtfsCounter, 125 mSDsluCounter, 1155 mSDsCounter, 0 mSdLazyCounter, 729 mSolverCounterSat, 49 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 19.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 126 SdHoareTripleChecker+Valid, 1274 SdHoareTripleChecker+Invalid, 782 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 729 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.2s IncrementalHoareTripleChecker+Time [2024-11-06 14:21:03,063 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [126 Valid, 1274 Invalid, 782 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 729 Invalid, 4 Unknown, 0 Unchecked, 19.2s Time] [2024-11-06 14:21:03,064 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 181 states. [2024-11-06 14:21:03,077 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 181 to 174. [2024-11-06 14:21:03,078 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-06 14:21:03,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 216 transitions. [2024-11-06 14:21:03,079 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 216 transitions. Word has length 100 [2024-11-06 14:21:03,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:21:03,079 INFO L471 AbstractCegarLoop]: Abstraction has 174 states and 216 transitions. [2024-11-06 14:21:03,079 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-06 14:21:03,079 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 216 transitions. [2024-11-06 14:21:03,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-06 14:21:03,081 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:21:03,081 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-06 14:21:03,097 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-06 14:21:03,284 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:21:03,285 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:21:03,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:21:03,285 INFO L85 PathProgramCache]: Analyzing trace with hash -1722487439, now seen corresponding path program 1 times [2024-11-06 14:21:03,285 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:21:03,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [762249652] [2024-11-06 14:21:03,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:21:03,286 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:21:03,286 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:21:03,287 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:21:03,289 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-06 14:21:03,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:21:03,429 INFO L255 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-06 14:21:03,432 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:21:03,641 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-06 14:21:03,646 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-06 14:21:05,842 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 14:21:05,842 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:21:05,843 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:21:05,843 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [762249652] [2024-11-06 14:21:05,843 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [762249652] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:21:05,843 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:21:05,843 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-06 14:21:05,843 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [793700696] [2024-11-06 14:21:05,843 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:21:05,843 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-06 14:21:05,843 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:21:05,844 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-06 14:21:05,844 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2024-11-06 14:21:05,844 INFO L87 Difference]: Start difference. First operand 174 states and 216 transitions. Second operand has 12 states, 12 states have (on average 4.833333333333333) internal successors, (58), 11 states have internal predecessors, (58), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-06 14:21:08,725 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:21:08,725 INFO L93 Difference]: Finished difference Result 422 states and 529 transitions. [2024-11-06 14:21:08,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-06 14:21:08,726 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 4.833333333333333) internal successors, (58), 11 states have internal predecessors, (58), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) Word has length 100 [2024-11-06 14:21:08,726 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:21:08,728 INFO L225 Difference]: With dead ends: 422 [2024-11-06 14:21:08,728 INFO L226 Difference]: Without dead ends: 338 [2024-11-06 14:21:08,728 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 77 SyntacticMatches, 12 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=55, Invalid=185, Unknown=0, NotChecked=0, Total=240 [2024-11-06 14:21:08,729 INFO L432 NwaCegarLoop]: 87 mSDtfsCounter, 74 mSDsluCounter, 537 mSDsCounter, 0 mSdLazyCounter, 451 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 624 SdHoareTripleChecker+Invalid, 485 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 451 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.6s IncrementalHoareTripleChecker+Time [2024-11-06 14:21:08,729 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 624 Invalid, 485 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 451 Invalid, 0 Unknown, 0 Unchecked, 2.6s Time] [2024-11-06 14:21:08,735 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 338 states. [2024-11-06 14:21:08,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 338 to 336. [2024-11-06 14:21:08,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 336 states, 250 states have (on average 1.216) internal successors, (304), 254 states have internal predecessors, (304), 54 states have call successors, (54), 29 states have call predecessors, (54), 31 states have return successors, (60), 52 states have call predecessors, (60), 52 states have call successors, (60) [2024-11-06 14:21:08,810 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 336 states to 336 states and 418 transitions. [2024-11-06 14:21:08,811 INFO L78 Accepts]: Start accepts. Automaton has 336 states and 418 transitions. Word has length 100 [2024-11-06 14:21:08,811 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:21:08,811 INFO L471 AbstractCegarLoop]: Abstraction has 336 states and 418 transitions. [2024-11-06 14:21:08,812 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 4.833333333333333) internal successors, (58), 11 states have internal predecessors, (58), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-06 14:21:08,812 INFO L276 IsEmpty]: Start isEmpty. Operand 336 states and 418 transitions. [2024-11-06 14:21:08,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-06 14:21:08,813 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:21:08,813 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-06 14:21:08,830 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2024-11-06 14:21:09,013 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:21:09,013 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:21:09,014 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:21:09,014 INFO L85 PathProgramCache]: Analyzing trace with hash -2115514449, now seen corresponding path program 1 times [2024-11-06 14:21:09,014 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:21:09,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [979404490] [2024-11-06 14:21:09,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:21:09,014 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:21:09,015 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:21:09,016 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:21:09,017 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-06 14:21:09,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:21:09,160 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-11-06 14:21:09,163 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:21:09,276 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-06 14:21:11,176 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-06 14:21:11,177 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 14:21:14,713 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-06 14:21:14,714 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-06 14:21:14,866 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-06 14:21:14,866 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:21:14,866 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [979404490] [2024-11-06 14:21:14,866 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [979404490] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 14:21:14,866 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-06 14:21:14,866 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 11] total 25 [2024-11-06 14:21:14,866 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1371940688] [2024-11-06 14:21:14,866 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-06 14:21:14,867 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-06 14:21:14,867 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:21:14,867 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-06 14:21:14,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=513, Unknown=0, NotChecked=0, Total=600 [2024-11-06 14:21:14,868 INFO L87 Difference]: Start difference. First operand 336 states and 418 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-06 14:21:18,885 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-06 14:21:22,985 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-06 14:21:27,188 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-06 14:21:31,547 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-06 14:21:35,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:21:35,111 INFO L93 Difference]: Finished difference Result 515 states and 645 transitions. [2024-11-06 14:21:35,112 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-06 14:21:35,112 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-06 14:21:35,112 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:21:35,118 INFO L225 Difference]: With dead ends: 515 [2024-11-06 14:21:35,118 INFO L226 Difference]: Without dead ends: 351 [2024-11-06 14:21:35,120 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 215 GetRequests, 169 SyntacticMatches, 7 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 328 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=271, Invalid=1369, Unknown=0, NotChecked=0, Total=1640 [2024-11-06 14:21:35,124 INFO L432 NwaCegarLoop]: 115 mSDtfsCounter, 190 mSDsluCounter, 1130 mSDsCounter, 0 mSdLazyCounter, 809 mSolverCounterSat, 80 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 191 SdHoareTripleChecker+Valid, 1245 SdHoareTripleChecker+Invalid, 893 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Valid, 809 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.0s IncrementalHoareTripleChecker+Time [2024-11-06 14:21:35,124 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [191 Valid, 1245 Invalid, 893 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [80 Valid, 809 Invalid, 4 Unknown, 0 Unchecked, 19.0s Time] [2024-11-06 14:21:35,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 351 states. [2024-11-06 14:21:35,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 351 to 336. [2024-11-06 14:21:35,166 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 336 states, 250 states have (on average 1.208) internal successors, (302), 254 states have internal predecessors, (302), 54 states have call successors, (54), 29 states have call predecessors, (54), 31 states have return successors, (60), 52 states have call predecessors, (60), 52 states have call successors, (60) [2024-11-06 14:21:35,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 336 states to 336 states and 416 transitions. [2024-11-06 14:21:35,168 INFO L78 Accepts]: Start accepts. Automaton has 336 states and 416 transitions. Word has length 100 [2024-11-06 14:21:35,168 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:21:35,168 INFO L471 AbstractCegarLoop]: Abstraction has 336 states and 416 transitions. [2024-11-06 14:21:35,168 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-06 14:21:35,169 INFO L276 IsEmpty]: Start isEmpty. Operand 336 states and 416 transitions. [2024-11-06 14:21:35,171 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-06 14:21:35,171 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:21:35,171 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-06 14:21:35,192 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-06 14:21:35,375 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:21:35,375 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:21:35,376 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:21:35,376 INFO L85 PathProgramCache]: Analyzing trace with hash -1857349011, now seen corresponding path program 1 times [2024-11-06 14:21:35,376 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:21:35,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2119288750] [2024-11-06 14:21:35,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:21:35,377 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:21:35,377 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:21:35,381 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:21:35,382 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-06 14:21:35,541 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:21:35,544 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-06 14:21:35,547 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:21:35,641 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-06 14:21:37,459 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 43 proven. 11 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 14:21:37,459 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 14:21:38,900 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:21:38,900 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2119288750] [2024-11-06 14:21:38,900 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2119288750] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-06 14:21:38,901 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [1007376375] [2024-11-06 14:21:38,901 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:21:38,901 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-06 14:21:38,901 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-06 14:21:38,917 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-06 14:21:38,918 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (15)] Waiting until timeout for monitored process [2024-11-06 14:21:39,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:21:39,258 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-06 14:21:39,262 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:21:39,516 INFO L349 Elim1Store]: treesize reduction 34, result has 35.8 percent of original size [2024-11-06 14:21:39,517 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-06 14:21:39,534 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-06 14:21:39,549 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-06 14:21:39,550 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-06 14:21:39,583 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-06 14:21:39,587 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-06 14:21:42,912 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 43 proven. 11 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-06 14:21:42,912 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-06 14:21:45,566 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-06 14:21:45,566 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 226 treesize of output 221 [2024-11-06 14:21:45,577 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 164 treesize of output 156 [2024-11-06 14:21:45,778 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-06 14:21:45,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [1007376375] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-06 14:21:45,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-06 14:21:45,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 16] total 44 [2024-11-06 14:21:45,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [921888683] [2024-11-06 14:21:45,779 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-06 14:21:45,779 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 44 states [2024-11-06 14:21:45,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:21:45,780 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2024-11-06 14:21:45,781 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=208, Invalid=3098, Unknown=0, NotChecked=0, Total=3306 [2024-11-06 14:21:45,781 INFO L87 Difference]: Start difference. First operand 336 states and 416 transitions. Second operand has 44 states, 41 states have (on average 3.292682926829268) internal successors, (135), 41 states have internal predecessors, (135), 19 states have call successors, (37), 7 states have call predecessors, (37), 9 states have return successors, (33), 16 states have call predecessors, (33), 18 states have call successors, (33) [2024-11-06 14:21:49,928 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-06 14:22:04,355 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-06 14:22:04,355 INFO L93 Difference]: Finished difference Result 897 states and 1129 transitions. [2024-11-06 14:22:04,355 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2024-11-06 14:22:04,356 INFO L78 Accepts]: Start accepts. Automaton has has 44 states, 41 states have (on average 3.292682926829268) internal successors, (135), 41 states have internal predecessors, (135), 19 states have call successors, (37), 7 states have call predecessors, (37), 9 states have return successors, (33), 16 states have call predecessors, (33), 18 states have call successors, (33) Word has length 100 [2024-11-06 14:22:04,356 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-06 14:22:04,359 INFO L225 Difference]: With dead ends: 897 [2024-11-06 14:22:04,365 INFO L226 Difference]: Without dead ends: 677 [2024-11-06 14:22:04,368 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 408 GetRequests, 306 SyntacticMatches, 12 SemanticMatches, 90 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1923 ImplicationChecksByTransitivity, 11.7s TimeCoverageRelationStatistics Valid=877, Invalid=7495, Unknown=0, NotChecked=0, Total=8372 [2024-11-06 14:22:04,372 INFO L432 NwaCegarLoop]: 123 mSDtfsCounter, 571 mSDsluCounter, 2452 mSDsCounter, 0 mSdLazyCounter, 2341 mSolverCounterSat, 241 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 572 SdHoareTripleChecker+Valid, 2575 SdHoareTripleChecker+Invalid, 2583 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 241 IncrementalHoareTripleChecker+Valid, 2341 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.7s IncrementalHoareTripleChecker+Time [2024-11-06 14:22:04,373 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [572 Valid, 2575 Invalid, 2583 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [241 Valid, 2341 Invalid, 1 Unknown, 0 Unchecked, 13.7s Time] [2024-11-06 14:22:04,374 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 677 states. [2024-11-06 14:22:04,465 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 677 to 579. [2024-11-06 14:22:04,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 579 states, 430 states have (on average 1.213953488372093) internal successors, (522), 439 states have internal predecessors, (522), 94 states have call successors, (94), 45 states have call predecessors, (94), 54 states have return successors, (113), 94 states have call predecessors, (113), 90 states have call successors, (113) [2024-11-06 14:22:04,472 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 579 states to 579 states and 729 transitions. [2024-11-06 14:22:04,473 INFO L78 Accepts]: Start accepts. Automaton has 579 states and 729 transitions. Word has length 100 [2024-11-06 14:22:04,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-06 14:22:04,473 INFO L471 AbstractCegarLoop]: Abstraction has 579 states and 729 transitions. [2024-11-06 14:22:04,473 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 44 states, 41 states have (on average 3.292682926829268) internal successors, (135), 41 states have internal predecessors, (135), 19 states have call successors, (37), 7 states have call predecessors, (37), 9 states have return successors, (33), 16 states have call predecessors, (33), 18 states have call successors, (33) [2024-11-06 14:22:04,474 INFO L276 IsEmpty]: Start isEmpty. Operand 579 states and 729 transitions. [2024-11-06 14:22:04,474 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 103 [2024-11-06 14:22:04,474 INFO L207 NwaCegarLoop]: Found error trace [2024-11-06 14:22:04,475 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, 1, 1] [2024-11-06 14:22:04,492 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-06 14:22:04,682 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (15)] Forceful destruction successful, exit code 0 [2024-11-06 14:22:04,876 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-06 14:22:04,876 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-06 14:22:04,877 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-06 14:22:04,877 INFO L85 PathProgramCache]: Analyzing trace with hash -309909297, now seen corresponding path program 1 times [2024-11-06 14:22:04,877 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2024-11-06 14:22:04,877 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1246938277] [2024-11-06 14:22:04,877 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-06 14:22:04,877 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-06 14:22:04,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-06 14:22:04,882 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-06 14:22:04,883 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-06 14:22:05,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-06 14:22:05,082 INFO L255 TraceCheckSpWp]: Trace formula consists of 283 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-06 14:22:05,085 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-06 14:22:05,293 INFO L349 Elim1Store]: treesize reduction 50, result has 41.2 percent of original size [2024-11-06 14:22:05,293 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 60 treesize of output 104 [2024-11-06 14:22:05,308 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2024-11-06 14:22:05,316 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-06 14:22:05,316 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 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-06 14:22:05,349 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 20 [2024-11-06 14:22:06,424 INFO L134 CoverageAnalysis]: Checked inductivity of 79 backedges. 31 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-06 14:22:06,424 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-06 14:22:06,424 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2024-11-06 14:22:06,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1246938277] [2024-11-06 14:22:06,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1246938277] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-06 14:22:06,425 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-06 14:22:06,425 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-06 14:22:06,425 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1177465265] [2024-11-06 14:22:06,425 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-06 14:22:06,426 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-06 14:22:06,426 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2024-11-06 14:22:06,426 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-06 14:22:06,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2024-11-06 14:22:06,427 INFO L87 Difference]: Start difference. First operand 579 states and 729 transitions. Second operand has 12 states, 12 states have (on average 5.0) internal successors, (60), 11 states have internal predecessors, (60), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 5 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-06 14:22:10,465 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]