/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml --traceabstraction.trace.refinement.strategy FIXED_PREFERENCES --cacsl2boogietranslator.allow.undefined.functions true --traceabstraction.smt.solver External_ModelsAndUnsatCoreMode --traceabstraction.command.for.external.solver 'z3 -smt2 -in SMTLIB2_COMPLIANT=true' -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf -i ../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_swap_contents_harness.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 15:09:56,563 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 15:09:56,623 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf [2024-11-04 15:09:56,627 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 15:09:56,627 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 15:09:56,649 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 15:09:56,650 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 15:09:56,650 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 15:09:56,651 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 15:09:56,651 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 15:09:56,651 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 15:09:56,652 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 15:09:56,652 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 15:09:56,653 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 15:09:56,653 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 15:09:56,653 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 15:09:56,654 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 15:09:56,654 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 15:09:56,654 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 15:09:56,655 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 15:09:56,655 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 15:09:56,656 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 15:09:56,656 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 15:09:56,656 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 15:09:56,656 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 15:09:56,657 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 15:09:56,657 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 15:09:56,657 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 15:09:56,658 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 15:09:56,658 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 15:09:56,658 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 15:09:56,659 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:09:56,659 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 15:09:56,659 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 15:09:56,660 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 15:09:56,660 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 15:09:56,660 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 15:09:56,661 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 15:09:56,661 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 15:09:56,661 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 15:09:56,661 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 15:09:56,662 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Trace refinement strategy -> FIXED_PREFERENCES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Allow undefined functions -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMT solver -> External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Command for external solver -> z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:56,879 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 15:09:56,900 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 15:09:56,905 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 15:09:56,906 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 15:09:56,906 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 15:09:56,907 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_swap_contents_harness.i [2024-11-04 15:09:58,381 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 15:09:58,801 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 15:09:58,802 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_swap_contents_harness.i [2024-11-04 15:09:58,836 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1b3f1d76/dd38b1fa2fce49b497d55066b4a0afc0/FLAG0d624c825 [2024-11-04 15:09:58,855 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1b3f1d76/dd38b1fa2fce49b497d55066b4a0afc0 [2024-11-04 15:09:58,859 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 15:09:58,861 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 15:09:58,862 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 15:09:58,862 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 15:09:58,868 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 15:09:58,868 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:09:58" (1/1) ... [2024-11-04 15:09:58,869 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6fadfc6b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:58, skipping insertion in model container [2024-11-04 15:09:58,870 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:09:58" (1/1) ... [2024-11-04 15:09:58,962 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:09:59,280 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_swap_contents_harness.i[4503,4516] [2024-11-04 15:09:59,287 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_swap_contents_harness.i[4563,4576] [2024-11-04 15:09:59,884 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:59,972 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:59,973 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:59,973 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:59,991 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:59,993 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:59,994 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:59,994 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:59,995 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:59,995 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:59,996 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:59,999 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,000 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,002 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,002 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,011 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,012 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,012 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,013 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,014 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,014 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,015 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,015 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,017 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,017 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,018 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,018 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,019 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,019 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,421 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,422 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,423 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,423 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,556 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,572 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:10:00,594 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 15:10:00,628 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:10:00,633 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_swap_contents_harness.i[4503,4516] [2024-11-04 15:10:00,634 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_swap_contents_harness.i[4563,4576] [2024-11-04 15:10:00,655 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,669 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,670 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,670 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,675 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,676 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,676 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,677 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,677 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,677 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,678 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,680 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,680 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,681 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,682 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,686 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,686 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,687 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,687 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,688 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,688 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,688 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,689 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,690 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,690 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,690 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,691 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,691 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,691 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,773 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,774 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,774 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,775 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,825 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:10:00,835 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:10:00,844 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 15:10:00,860 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_swap_contents_harness.i[4503,4516] [2024-11-04 15:10:00,860 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_swap_contents_harness.i[4563,4576] [2024-11-04 15:10:00,905 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,905 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,905 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,906 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,906 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,912 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,912 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,913 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,914 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,914 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,915 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,915 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,915 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:10:00,993 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:10:01,154 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 15:10:01,166 INFO L204 MainTranslator]: Completed translation [2024-11-04 15:10:01,168 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01 WrapperNode [2024-11-04 15:10:01,168 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 15:10:01,169 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 15:10:01,170 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 15:10:01,170 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 15:10:01,177 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,261 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,317 INFO L138 Inliner]: procedures = 687, calls = 1078, calls flagged for inlining = 51, calls inlined = 5, statements flattened = 214 [2024-11-04 15:10:01,318 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 15:10:01,318 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 15:10:01,318 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 15:10:01,319 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 15:10:01,331 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,332 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,340 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,376 INFO L175 MemorySlicer]: Split 68 memory accesses to 5 slices as follows [2, 47, 5, 7, 7]. 69 percent of accesses are in the largest equivalence class. The 15 initializations are split as follows [2, 0, 5, 4, 4]. The 18 writes are split as follows [0, 18, 0, 0, 0]. [2024-11-04 15:10:01,377 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,377 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,399 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,408 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,413 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,417 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,424 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 15:10:01,425 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 15:10:01,425 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 15:10:01,425 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 15:10:01,426 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (1/1) ... [2024-11-04 15:10:01,439 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:10:01,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:01,476 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-04 15:10:01,482 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-04 15:10:01,506 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_init [2024-11-04 15:10:01,506 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_init [2024-11-04 15:10:01,506 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 15:10:01,506 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 15:10:01,506 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 15:10:01,507 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 15:10:01,507 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#3 [2024-11-04 15:10:01,507 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#4 [2024-11-04 15:10:01,507 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 15:10:01,507 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 15:10:01,507 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:10:01,507 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:10:01,507 INFO L130 BoogieDeclarations]: Found specification of procedure ensure_linked_list_is_allocated [2024-11-04 15:10:01,507 INFO L138 BoogieDeclarations]: Found implementation of procedure ensure_linked_list_is_allocated [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-04 15:10:01,508 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#3 [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#4 [2024-11-04 15:10:01,508 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 15:10:01,508 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2024-11-04 15:10:01,509 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 15:10:01,509 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#3 [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#4 [2024-11-04 15:10:01,509 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 15:10:01,510 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 15:10:01,510 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 15:10:01,510 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#3 [2024-11-04 15:10:01,510 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#4 [2024-11-04 15:10:01,510 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-04 15:10:01,510 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-04 15:10:01,847 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 15:10:01,849 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 15:10:02,999 INFO L? ?]: Removed 63 outVars from TransFormulas that were not future-live. [2024-11-04 15:10:03,000 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 15:10:03,019 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 15:10:03,019 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-04 15:10:03,020 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:10:03 BoogieIcfgContainer [2024-11-04 15:10:03,020 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 15:10:03,045 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 15:10:03,045 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 15:10:03,048 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 15:10:03,048 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 03:09:58" (1/3) ... [2024-11-04 15:10:03,050 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@506afe10 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:10:03, skipping insertion in model container [2024-11-04 15:10:03,050 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:10:01" (2/3) ... [2024-11-04 15:10:03,050 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@506afe10 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:10:03, skipping insertion in model container [2024-11-04 15:10:03,050 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:10:03" (3/3) ... [2024-11-04 15:10:03,052 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_swap_contents_harness.i [2024-11-04 15:10:03,065 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 15:10:03,065 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 15:10:03,119 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 15:10:03,125 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;@3764c8b6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 15:10:03,125 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 15:10:03,129 INFO L276 IsEmpty]: Start isEmpty. Operand has 114 states, 70 states have (on average 1.3) internal successors, (91), 73 states have internal predecessors, (91), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-04 15:10:03,139 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 15:10:03,139 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:03,140 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:03,140 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:03,145 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:03,145 INFO L85 PathProgramCache]: Analyzing trace with hash 408503669, now seen corresponding path program 1 times [2024-11-04 15:10:03,153 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:03,153 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [254110097] [2024-11-04 15:10:03,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:03,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:03,156 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:03,158 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:03,161 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-04 15:10:03,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:03,506 INFO L255 TraceCheckSpWp]: Trace formula consists of 404 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 15:10:03,516 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:03,550 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2024-11-04 15:10:03,551 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:03,726 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-04 15:10:03,727 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:03,727 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [254110097] [2024-11-04 15:10:03,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [254110097] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:03,728 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:03,729 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-04 15:10:03,731 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [429629241] [2024-11-04 15:10:03,732 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:03,735 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 15:10:03,735 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:03,760 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 15:10:03,761 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 15:10:03,762 INFO L87 Difference]: Start difference. First operand has 114 states, 70 states have (on average 1.3) internal successors, (91), 73 states have internal predecessors, (91), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) Second operand has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2024-11-04 15:10:03,795 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:03,796 INFO L93 Difference]: Finished difference Result 225 states and 346 transitions. [2024-11-04 15:10:03,797 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 15:10:03,798 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) Word has length 101 [2024-11-04 15:10:03,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:03,806 INFO L225 Difference]: With dead ends: 225 [2024-11-04 15:10:03,806 INFO L226 Difference]: Without dead ends: 107 [2024-11-04 15:10:03,814 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 200 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 15:10:03,819 INFO L432 NwaCegarLoop]: 155 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, 155 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:03,820 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:10:03,840 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2024-11-04 15:10:03,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 107. [2024-11-04 15:10:03,876 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 64 states have (on average 1.265625) internal successors, (81), 68 states have internal predecessors, (81), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 15:10:03,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 147 transitions. [2024-11-04 15:10:03,888 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 147 transitions. Word has length 101 [2024-11-04 15:10:03,888 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:03,888 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 147 transitions. [2024-11-04 15:10:03,889 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 20.0) internal successors, (40), 2 states have internal predecessors, (40), 2 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (13), 2 states have call predecessors, (13), 2 states have call successors, (13) [2024-11-04 15:10:03,889 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 147 transitions. [2024-11-04 15:10:03,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 15:10:03,896 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:03,896 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:03,919 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-04 15:10:04,097 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:04,097 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:04,098 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:04,098 INFO L85 PathProgramCache]: Analyzing trace with hash 34190191, now seen corresponding path program 1 times [2024-11-04 15:10:04,098 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:04,098 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1580218459] [2024-11-04 15:10:04,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:04,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:04,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:04,101 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:04,102 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-04 15:10:04,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:04,392 INFO L255 TraceCheckSpWp]: Trace formula consists of 404 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:10:04,398 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:04,452 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 32 proven. 0 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2024-11-04 15:10:04,452 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:04,580 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-04 15:10:04,581 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:04,581 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1580218459] [2024-11-04 15:10:04,581 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1580218459] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:04,581 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:04,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:10:04,581 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [890049357] [2024-11-04 15:10:04,581 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:04,583 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:10:04,583 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:04,585 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:10:04,586 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:04,586 INFO L87 Difference]: Start difference. First operand 107 states and 147 transitions. Second operand has 4 states, 4 states have (on average 10.25) internal successors, (41), 4 states have internal predecessors, (41), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:04,652 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:04,652 INFO L93 Difference]: Finished difference Result 198 states and 284 transitions. [2024-11-04 15:10:04,653 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:10:04,654 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 10.25) internal successors, (41), 4 states have internal predecessors, (41), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 101 [2024-11-04 15:10:04,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:04,656 INFO L225 Difference]: With dead ends: 198 [2024-11-04 15:10:04,656 INFO L226 Difference]: Without dead ends: 110 [2024-11-04 15:10:04,658 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 198 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:04,661 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 1 mSDsluCounter, 280 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 424 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:04,661 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 424 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:10:04,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-11-04 15:10:04,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 109. [2024-11-04 15:10:04,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 66 states have (on average 1.2575757575757576) internal successors, (83), 70 states have internal predecessors, (83), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 15:10:04,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 149 transitions. [2024-11-04 15:10:04,679 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 149 transitions. Word has length 101 [2024-11-04 15:10:04,682 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:04,682 INFO L471 AbstractCegarLoop]: Abstraction has 109 states and 149 transitions. [2024-11-04 15:10:04,682 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 10.25) internal successors, (41), 4 states have internal predecessors, (41), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:04,682 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 149 transitions. [2024-11-04 15:10:04,684 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 15:10:04,684 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:04,685 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:04,703 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-04 15:10:04,888 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:04,889 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:04,889 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:04,889 INFO L85 PathProgramCache]: Analyzing trace with hash 742326057, now seen corresponding path program 1 times [2024-11-04 15:10:04,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:04,890 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [987696184] [2024-11-04 15:10:04,890 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:04,890 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:04,890 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:04,892 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:04,894 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-04 15:10:05,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:05,168 INFO L255 TraceCheckSpWp]: Trace formula consists of 395 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:10:05,175 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:05,198 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 36 proven. 0 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2024-11-04 15:10:05,199 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:05,295 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 71 trivial. 0 not checked. [2024-11-04 15:10:05,296 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:05,296 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [987696184] [2024-11-04 15:10:05,296 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [987696184] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:05,296 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:05,296 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:10:05,297 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [21877637] [2024-11-04 15:10:05,297 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:05,297 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:10:05,297 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:05,298 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:10:05,298 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:05,301 INFO L87 Difference]: Start difference. First operand 109 states and 149 transitions. Second operand has 4 states, 4 states have (on average 10.75) internal successors, (43), 4 states have internal predecessors, (43), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:05,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:05,361 INFO L93 Difference]: Finished difference Result 202 states and 288 transitions. [2024-11-04 15:10:05,363 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:10:05,363 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 10.75) internal successors, (43), 4 states have internal predecessors, (43), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 101 [2024-11-04 15:10:05,363 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:05,365 INFO L225 Difference]: With dead ends: 202 [2024-11-04 15:10:05,365 INFO L226 Difference]: Without dead ends: 112 [2024-11-04 15:10:05,366 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 198 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:05,367 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 1 mSDsluCounter, 280 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 424 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:05,368 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 424 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:10:05,372 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2024-11-04 15:10:05,429 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 111. [2024-11-04 15:10:05,430 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 68 states have (on average 1.25) internal successors, (85), 72 states have internal predecessors, (85), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 15:10:05,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 151 transitions. [2024-11-04 15:10:05,434 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 151 transitions. Word has length 101 [2024-11-04 15:10:05,434 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:05,434 INFO L471 AbstractCegarLoop]: Abstraction has 111 states and 151 transitions. [2024-11-04 15:10:05,435 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 10.75) internal successors, (43), 4 states have internal predecessors, (43), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:05,435 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 151 transitions. [2024-11-04 15:10:05,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 15:10:05,440 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:05,440 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:05,463 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-04 15:10:05,644 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:05,645 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:05,645 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:05,646 INFO L85 PathProgramCache]: Analyzing trace with hash -588779165, now seen corresponding path program 1 times [2024-11-04 15:10:05,646 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:05,646 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1313551917] [2024-11-04 15:10:05,646 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:05,646 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:05,646 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:05,648 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:05,650 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-04 15:10:05,900 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:05,909 INFO L255 TraceCheckSpWp]: Trace formula consists of 386 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:10:05,912 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:05,935 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 40 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-04 15:10:05,936 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:06,025 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-11-04 15:10:06,025 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:06,025 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1313551917] [2024-11-04 15:10:06,025 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1313551917] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:06,025 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:06,026 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:10:06,026 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1569694331] [2024-11-04 15:10:06,026 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:06,026 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:10:06,026 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:06,027 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:10:06,027 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:06,027 INFO L87 Difference]: Start difference. First operand 111 states and 151 transitions. Second operand has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:06,066 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:06,066 INFO L93 Difference]: Finished difference Result 206 states and 293 transitions. [2024-11-04 15:10:06,067 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:10:06,067 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 101 [2024-11-04 15:10:06,067 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:06,071 INFO L225 Difference]: With dead ends: 206 [2024-11-04 15:10:06,071 INFO L226 Difference]: Without dead ends: 114 [2024-11-04 15:10:06,072 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 198 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:06,073 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 1 mSDsluCounter, 282 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 426 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:06,073 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 426 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:10:06,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2024-11-04 15:10:06,092 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 114. [2024-11-04 15:10:06,093 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 71 states have (on average 1.2394366197183098) internal successors, (88), 75 states have internal predecessors, (88), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 15:10:06,095 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 154 transitions. [2024-11-04 15:10:06,095 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 154 transitions. Word has length 101 [2024-11-04 15:10:06,095 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:06,096 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 154 transitions. [2024-11-04 15:10:06,096 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:06,097 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 154 transitions. [2024-11-04 15:10:06,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 15:10:06,099 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:06,099 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:06,121 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-04 15:10:06,299 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:06,300 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:06,300 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:06,300 INFO L85 PathProgramCache]: Analyzing trace with hash 1908156957, now seen corresponding path program 1 times [2024-11-04 15:10:06,300 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:06,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1705627101] [2024-11-04 15:10:06,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:06,301 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:06,301 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:06,302 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:06,303 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-04 15:10:06,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:06,552 INFO L255 TraceCheckSpWp]: Trace formula consists of 377 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 15:10:06,555 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:06,656 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 15:10:06,657 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:06,839 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:10:06,839 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:06,839 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1705627101] [2024-11-04 15:10:06,839 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1705627101] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:06,839 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:06,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-04 15:10:06,840 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [813943389] [2024-11-04 15:10:06,840 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:06,841 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:10:06,841 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:06,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:10:06,842 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-04 15:10:06,842 INFO L87 Difference]: Start difference. First operand 114 states and 154 transitions. Second operand has 6 states, 5 states have (on average 9.4) internal successors, (47), 6 states have internal predecessors, (47), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:08,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:08,850 INFO L93 Difference]: Finished difference Result 216 states and 298 transitions. [2024-11-04 15:10:08,851 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:10:08,851 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 9.4) internal successors, (47), 6 states have internal predecessors, (47), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 101 [2024-11-04 15:10:08,851 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:08,854 INFO L225 Difference]: With dead ends: 216 [2024-11-04 15:10:08,854 INFO L226 Difference]: Without dead ends: 121 [2024-11-04 15:10:08,855 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 196 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:10:08,856 INFO L432 NwaCegarLoop]: 134 mSDtfsCounter, 28 mSDsluCounter, 469 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 603 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:08,856 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 603 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-04 15:10:08,857 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-11-04 15:10:08,866 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 121. [2024-11-04 15:10:08,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 77 states have (on average 1.2207792207792207) internal successors, (94), 82 states have internal predecessors, (94), 34 states have call successors, (34), 8 states have call predecessors, (34), 9 states have return successors, (36), 32 states have call predecessors, (36), 32 states have call successors, (36) [2024-11-04 15:10:08,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 164 transitions. [2024-11-04 15:10:08,868 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 164 transitions. Word has length 101 [2024-11-04 15:10:08,869 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:08,869 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 164 transitions. [2024-11-04 15:10:08,869 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 9.4) internal successors, (47), 6 states have internal predecessors, (47), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:08,869 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 164 transitions. [2024-11-04 15:10:08,870 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 15:10:08,871 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:08,871 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:10:08,893 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:09,071 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:09,072 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:09,072 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:09,072 INFO L85 PathProgramCache]: Analyzing trace with hash -1786984915, now seen corresponding path program 1 times [2024-11-04 15:10:09,072 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:09,072 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2067046142] [2024-11-04 15:10:09,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:09,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:09,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:09,074 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:09,075 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-04 15:10:09,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:09,334 INFO L255 TraceCheckSpWp]: Trace formula consists of 401 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 15:10:09,337 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:09,492 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 56 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-04 15:10:09,493 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:09,728 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:10:09,728 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:09,728 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2067046142] [2024-11-04 15:10:09,728 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2067046142] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:09,728 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:09,729 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-04 15:10:09,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1077307873] [2024-11-04 15:10:09,730 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:09,731 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:10:09,731 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:09,731 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:10:09,731 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-04 15:10:09,732 INFO L87 Difference]: Start difference. First operand 121 states and 164 transitions. Second operand has 6 states, 6 states have (on average 9.5) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:11,978 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:11,979 INFO L93 Difference]: Finished difference Result 220 states and 299 transitions. [2024-11-04 15:10:11,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:10:11,980 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 9.5) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 101 [2024-11-04 15:10:11,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:11,982 INFO L225 Difference]: With dead ends: 220 [2024-11-04 15:10:11,982 INFO L226 Difference]: Without dead ends: 121 [2024-11-04 15:10:11,983 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 196 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:10:11,984 INFO L432 NwaCegarLoop]: 139 mSDtfsCounter, 27 mSDsluCounter, 349 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 488 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:11,984 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 488 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2024-11-04 15:10:11,985 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-11-04 15:10:11,998 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 121. [2024-11-04 15:10:11,998 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 77 states have (on average 1.2207792207792207) internal successors, (94), 82 states have internal predecessors, (94), 34 states have call successors, (34), 8 states have call predecessors, (34), 9 states have return successors, (33), 32 states have call predecessors, (33), 32 states have call successors, (33) [2024-11-04 15:10:12,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 161 transitions. [2024-11-04 15:10:12,001 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 161 transitions. Word has length 101 [2024-11-04 15:10:12,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:12,001 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 161 transitions. [2024-11-04 15:10:12,001 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 9.5) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:12,001 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 161 transitions. [2024-11-04 15:10:12,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 15:10:12,003 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:12,003 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:12,025 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:12,203 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:12,204 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:12,205 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:12,205 INFO L85 PathProgramCache]: Analyzing trace with hash -1879544267, now seen corresponding path program 1 times [2024-11-04 15:10:12,205 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:12,205 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1730325646] [2024-11-04 15:10:12,205 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:12,205 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:12,205 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:12,207 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:12,209 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-04 15:10:12,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:12,512 INFO L255 TraceCheckSpWp]: Trace formula consists of 413 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:10:12,519 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:12,580 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-04 15:10:12,581 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:12,774 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-04 15:10:12,775 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:12,775 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1730325646] [2024-11-04 15:10:12,775 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1730325646] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:12,775 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:12,775 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 15:10:12,776 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [737392266] [2024-11-04 15:10:12,776 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:12,776 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:10:12,776 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:12,777 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:10:12,777 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:10:12,777 INFO L87 Difference]: Start difference. First operand 121 states and 161 transitions. Second operand has 6 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 15:10:12,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:12,906 INFO L93 Difference]: Finished difference Result 225 states and 307 transitions. [2024-11-04 15:10:12,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:10:12,910 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 101 [2024-11-04 15:10:12,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:12,912 INFO L225 Difference]: With dead ends: 225 [2024-11-04 15:10:12,912 INFO L226 Difference]: Without dead ends: 123 [2024-11-04 15:10:12,914 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 195 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:10:12,915 INFO L432 NwaCegarLoop]: 141 mSDtfsCounter, 0 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 687 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:12,915 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 687 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:10:12,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-11-04 15:10:12,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 123. [2024-11-04 15:10:12,935 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 78 states have (on average 1.2179487179487178) internal successors, (95), 84 states have internal predecessors, (95), 34 states have call successors, (34), 8 states have call predecessors, (34), 10 states have return successors, (39), 32 states have call predecessors, (39), 32 states have call successors, (39) [2024-11-04 15:10:12,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 168 transitions. [2024-11-04 15:10:12,938 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 168 transitions. Word has length 101 [2024-11-04 15:10:12,938 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:12,939 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 168 transitions. [2024-11-04 15:10:12,939 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 15:10:12,939 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 168 transitions. [2024-11-04 15:10:12,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-04 15:10:12,940 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:12,940 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:12,964 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-04 15:10:13,141 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:13,141 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:13,142 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:13,142 INFO L85 PathProgramCache]: Analyzing trace with hash 574804529, now seen corresponding path program 1 times [2024-11-04 15:10:13,142 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:13,142 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2106602442] [2024-11-04 15:10:13,142 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:13,142 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:13,143 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:13,144 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:13,146 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-04 15:10:13,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:13,425 INFO L255 TraceCheckSpWp]: Trace formula consists of 420 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 15:10:13,428 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:13,547 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 15:10:13,547 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:13,807 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:10:13,808 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:13,808 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2106602442] [2024-11-04 15:10:13,808 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2106602442] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:13,808 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:13,809 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2024-11-04 15:10:13,809 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [791026188] [2024-11-04 15:10:13,809 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:13,809 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:10:13,809 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:13,810 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:10:13,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:10:13,810 INFO L87 Difference]: Start difference. First operand 123 states and 168 transitions. Second operand has 7 states, 6 states have (on average 8.166666666666666) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:17,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:17,782 INFO L93 Difference]: Finished difference Result 232 states and 324 transitions. [2024-11-04 15:10:17,783 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:10:17,784 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 8.166666666666666) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 103 [2024-11-04 15:10:17,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:17,785 INFO L225 Difference]: With dead ends: 232 [2024-11-04 15:10:17,785 INFO L226 Difference]: Without dead ends: 128 [2024-11-04 15:10:17,786 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 197 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 15:10:17,787 INFO L432 NwaCegarLoop]: 127 mSDtfsCounter, 41 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 151 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 673 SdHoareTripleChecker+Invalid, 185 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 151 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.9s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:17,787 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 673 Invalid, 185 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 151 Invalid, 0 Unknown, 0 Unchecked, 3.9s Time] [2024-11-04 15:10:17,788 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-11-04 15:10:17,799 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 126. [2024-11-04 15:10:17,800 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 80 states have (on average 1.2125) internal successors, (97), 87 states have internal predecessors, (97), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 15:10:17,801 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 174 transitions. [2024-11-04 15:10:17,802 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 174 transitions. Word has length 103 [2024-11-04 15:10:17,803 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:17,803 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 174 transitions. [2024-11-04 15:10:17,803 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 8.166666666666666) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:17,803 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 174 transitions. [2024-11-04 15:10:17,804 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2024-11-04 15:10:17,804 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:17,804 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:17,828 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:18,008 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:18,009 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:18,009 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:18,009 INFO L85 PathProgramCache]: Analyzing trace with hash 1835480350, now seen corresponding path program 1 times [2024-11-04 15:10:18,009 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:18,010 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [620191928] [2024-11-04 15:10:18,010 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:18,010 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:18,010 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:18,012 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:18,015 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-04 15:10:18,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:18,323 INFO L255 TraceCheckSpWp]: Trace formula consists of 424 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 15:10:18,326 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:18,470 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 15:10:18,471 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:18,782 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:10:18,783 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:18,783 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [620191928] [2024-11-04 15:10:18,783 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [620191928] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:18,783 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:18,783 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 15:10:18,783 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2016615992] [2024-11-04 15:10:18,783 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:18,784 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:10:18,784 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:18,784 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:10:18,784 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 15:10:18,785 INFO L87 Difference]: Start difference. First operand 126 states and 174 transitions. Second operand has 8 states, 7 states have (on average 7.285714285714286) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:23,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:23,432 INFO L93 Difference]: Finished difference Result 244 states and 346 transitions. [2024-11-04 15:10:23,434 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 15:10:23,434 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 7.285714285714286) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 105 [2024-11-04 15:10:23,435 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:23,436 INFO L225 Difference]: With dead ends: 244 [2024-11-04 15:10:23,436 INFO L226 Difference]: Without dead ends: 137 [2024-11-04 15:10:23,439 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 199 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2024-11-04 15:10:23,441 INFO L432 NwaCegarLoop]: 125 mSDtfsCounter, 50 mSDsluCounter, 653 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 778 SdHoareTripleChecker+Invalid, 243 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:23,441 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 778 Invalid, 243 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 206 Invalid, 0 Unknown, 0 Unchecked, 4.6s Time] [2024-11-04 15:10:23,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2024-11-04 15:10:23,455 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 128. [2024-11-04 15:10:23,455 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 82 states have (on average 1.2195121951219512) internal successors, (100), 89 states have internal predecessors, (100), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 15:10:23,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 177 transitions. [2024-11-04 15:10:23,458 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 177 transitions. Word has length 105 [2024-11-04 15:10:23,458 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:23,458 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 177 transitions. [2024-11-04 15:10:23,459 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 7.285714285714286) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 15:10:23,459 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 177 transitions. [2024-11-04 15:10:23,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:10:23,461 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:23,461 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:23,482 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:23,661 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:23,661 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:23,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:23,662 INFO L85 PathProgramCache]: Analyzing trace with hash 2014676356, now seen corresponding path program 1 times [2024-11-04 15:10:23,662 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:23,662 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [208566219] [2024-11-04 15:10:23,662 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:23,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:23,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:23,664 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:23,665 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-04 15:10:23,943 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:23,953 INFO L255 TraceCheckSpWp]: Trace formula consists of 426 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-04 15:10:23,955 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:23,974 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-04 15:10:23,974 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:24,108 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-04 15:10:24,109 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:24,109 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [208566219] [2024-11-04 15:10:24,109 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [208566219] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:24,109 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:24,109 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 4 [2024-11-04 15:10:24,109 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1221102123] [2024-11-04 15:10:24,109 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:24,109 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-04 15:10:24,110 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:24,110 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-04 15:10:24,110 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:24,110 INFO L87 Difference]: Start difference. First operand 128 states and 177 transitions. Second operand has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:24,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:24,161 INFO L93 Difference]: Finished difference Result 241 states and 347 transitions. [2024-11-04 15:10:24,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-04 15:10:24,162 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 106 [2024-11-04 15:10:24,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:24,164 INFO L225 Difference]: With dead ends: 241 [2024-11-04 15:10:24,164 INFO L226 Difference]: Without dead ends: 132 [2024-11-04 15:10:24,165 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 210 GetRequests, 208 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:24,165 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 2 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 282 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:24,167 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 282 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:10:24,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-04 15:10:24,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 129. [2024-11-04 15:10:24,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 83 states have (on average 1.216867469879518) internal successors, (101), 90 states have internal predecessors, (101), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 15:10:24,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 178 transitions. [2024-11-04 15:10:24,179 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 178 transitions. Word has length 106 [2024-11-04 15:10:24,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:24,179 INFO L471 AbstractCegarLoop]: Abstraction has 129 states and 178 transitions. [2024-11-04 15:10:24,180 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 17.0) internal successors, (51), 3 states have internal predecessors, (51), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 15:10:24,182 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 178 transitions. [2024-11-04 15:10:24,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-04 15:10:24,183 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:24,184 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:24,207 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:24,387 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:24,387 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:24,388 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:24,388 INFO L85 PathProgramCache]: Analyzing trace with hash -1966687324, now seen corresponding path program 1 times [2024-11-04 15:10:24,388 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:24,388 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1689179042] [2024-11-04 15:10:24,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:24,389 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:24,389 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:24,392 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:24,395 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-04 15:10:24,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:24,780 INFO L255 TraceCheckSpWp]: Trace formula consists of 443 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:10:24,782 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:24,807 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-04 15:10:24,808 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:24,936 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-04 15:10:24,937 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:24,937 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1689179042] [2024-11-04 15:10:24,937 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1689179042] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:24,937 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:24,937 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:10:24,937 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [868396290] [2024-11-04 15:10:24,938 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:24,938 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:10:24,938 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:24,938 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:10:24,939 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:24,939 INFO L87 Difference]: Start difference. First operand 129 states and 178 transitions. Second operand has 4 states, 4 states have (on average 14.25) internal successors, (57), 4 states have internal predecessors, (57), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 15:10:24,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:24,967 INFO L93 Difference]: Finished difference Result 242 states and 347 transitions. [2024-11-04 15:10:24,968 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:10:24,968 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 14.25) internal successors, (57), 4 states have internal predecessors, (57), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 114 [2024-11-04 15:10:24,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:24,971 INFO L225 Difference]: With dead ends: 242 [2024-11-04 15:10:24,972 INFO L226 Difference]: Without dead ends: 132 [2024-11-04 15:10:24,973 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 224 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:24,973 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 1 mSDsluCounter, 284 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 428 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:24,974 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 428 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:10:24,974 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-04 15:10:24,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 131. [2024-11-04 15:10:24,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 85 states have (on average 1.2117647058823529) internal successors, (103), 92 states have internal predecessors, (103), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 15:10:24,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 180 transitions. [2024-11-04 15:10:24,984 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 180 transitions. Word has length 114 [2024-11-04 15:10:24,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:24,985 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 180 transitions. [2024-11-04 15:10:24,985 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 14.25) internal successors, (57), 4 states have internal predecessors, (57), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 15:10:24,985 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 180 transitions. [2024-11-04 15:10:24,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-04 15:10:24,986 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:24,986 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:25,009 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-04 15:10:25,186 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:25,187 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:25,187 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:25,187 INFO L85 PathProgramCache]: Analyzing trace with hash -1764863390, now seen corresponding path program 1 times [2024-11-04 15:10:25,187 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:25,187 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [509703594] [2024-11-04 15:10:25,188 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:25,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:25,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:25,189 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:25,190 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-04 15:10:25,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:25,481 INFO L255 TraceCheckSpWp]: Trace formula consists of 438 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-04 15:10:25,484 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:25,664 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 15:10:25,665 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:26,076 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:10:26,076 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:26,076 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [509703594] [2024-11-04 15:10:26,076 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [509703594] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:26,077 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:26,077 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [10] total 13 [2024-11-04 15:10:26,077 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1226595429] [2024-11-04 15:10:26,077 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:26,077 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-04 15:10:26,077 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:26,078 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-04 15:10:26,078 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-11-04 15:10:26,078 INFO L87 Difference]: Start difference. First operand 131 states and 180 transitions. Second operand has 10 states, 9 states have (on average 6.444444444444445) internal successors, (58), 10 states have internal predecessors, (58), 5 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-04 15:10:31,929 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.10s for a HTC check with result INVALID. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-04 15:10:32,081 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:32,082 INFO L93 Difference]: Finished difference Result 264 states and 373 transitions. [2024-11-04 15:10:32,083 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-04 15:10:32,083 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 6.444444444444445) internal successors, (58), 10 states have internal predecessors, (58), 5 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 114 [2024-11-04 15:10:32,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:32,085 INFO L225 Difference]: With dead ends: 264 [2024-11-04 15:10:32,085 INFO L226 Difference]: Without dead ends: 152 [2024-11-04 15:10:32,086 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 215 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-04 15:10:32,086 INFO L432 NwaCegarLoop]: 125 mSDtfsCounter, 62 mSDsluCounter, 892 mSDsCounter, 0 mSdLazyCounter, 307 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 1017 SdHoareTripleChecker+Invalid, 352 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 307 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.9s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:32,087 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 1017 Invalid, 352 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 307 Invalid, 0 Unknown, 0 Unchecked, 5.9s Time] [2024-11-04 15:10:32,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2024-11-04 15:10:32,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 139. [2024-11-04 15:10:32,096 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 90 states have (on average 1.2333333333333334) internal successors, (111), 99 states have internal predecessors, (111), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (48), 33 states have call predecessors, (48), 34 states have call successors, (48) [2024-11-04 15:10:32,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 195 transitions. [2024-11-04 15:10:32,097 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 195 transitions. Word has length 114 [2024-11-04 15:10:32,097 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:32,097 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 195 transitions. [2024-11-04 15:10:32,098 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 6.444444444444445) internal successors, (58), 10 states have internal predecessors, (58), 5 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-04 15:10:32,098 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 195 transitions. [2024-11-04 15:10:32,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-04 15:10:32,099 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:32,099 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:32,120 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2024-11-04 15:10:32,299 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:32,300 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:32,300 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:32,300 INFO L85 PathProgramCache]: Analyzing trace with hash 1649007718, now seen corresponding path program 1 times [2024-11-04 15:10:32,300 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:32,300 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [5148871] [2024-11-04 15:10:32,300 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:32,300 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:32,300 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:32,301 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:32,302 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-04 15:10:32,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:32,586 INFO L255 TraceCheckSpWp]: Trace formula consists of 446 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:10:32,589 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:32,632 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-04 15:10:32,632 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:32,767 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 11 proven. 5 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-04 15:10:32,768 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:32,768 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [5148871] [2024-11-04 15:10:32,768 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [5148871] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:32,768 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:32,768 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 15:10:32,768 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1359945922] [2024-11-04 15:10:32,768 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:32,768 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:10:32,769 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:32,769 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:10:32,769 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:10:32,769 INFO L87 Difference]: Start difference. First operand 139 states and 195 transitions. Second operand has 6 states, 5 states have (on average 12.6) internal successors, (63), 5 states have internal predecessors, (63), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 15:10:32,862 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:32,862 INFO L93 Difference]: Finished difference Result 256 states and 360 transitions. [2024-11-04 15:10:32,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:10:32,863 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 12.6) internal successors, (63), 5 states have internal predecessors, (63), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 114 [2024-11-04 15:10:32,863 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:32,864 INFO L225 Difference]: With dead ends: 256 [2024-11-04 15:10:32,864 INFO L226 Difference]: Without dead ends: 139 [2024-11-04 15:10:32,865 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 221 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:10:32,866 INFO L432 NwaCegarLoop]: 141 mSDtfsCounter, 0 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 687 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:32,866 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 687 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:10:32,866 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2024-11-04 15:10:32,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 139. [2024-11-04 15:10:32,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 90 states have (on average 1.2333333333333334) internal successors, (111), 99 states have internal predecessors, (111), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (47), 33 states have call predecessors, (47), 34 states have call successors, (47) [2024-11-04 15:10:32,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 194 transitions. [2024-11-04 15:10:32,875 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 194 transitions. Word has length 114 [2024-11-04 15:10:32,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:32,875 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 194 transitions. [2024-11-04 15:10:32,876 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 12.6) internal successors, (63), 5 states have internal predecessors, (63), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 15:10:32,876 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 194 transitions. [2024-11-04 15:10:32,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 15:10:32,877 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:32,877 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:32,900 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:33,081 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:33,082 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:33,082 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:33,082 INFO L85 PathProgramCache]: Analyzing trace with hash 796740706, now seen corresponding path program 1 times [2024-11-04 15:10:33,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:33,082 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1836409777] [2024-11-04 15:10:33,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:33,083 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:33,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:33,084 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:33,086 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-04 15:10:33,379 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:33,386 INFO L255 TraceCheckSpWp]: Trace formula consists of 453 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 15:10:33,389 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:33,454 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 58 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-04 15:10:33,455 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:33,654 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:10:33,654 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:33,654 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1836409777] [2024-11-04 15:10:33,654 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1836409777] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:33,654 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:33,654 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2024-11-04 15:10:33,654 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [663313612] [2024-11-04 15:10:33,655 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:33,655 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:10:33,655 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:33,655 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:10:33,656 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:10:33,656 INFO L87 Difference]: Start difference. First operand 139 states and 194 transitions. Second operand has 7 states, 7 states have (on average 10.0) internal successors, (70), 7 states have internal predecessors, (70), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 15:10:37,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:37,572 INFO L93 Difference]: Finished difference Result 263 states and 369 transitions. [2024-11-04 15:10:37,573 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:10:37,573 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 10.0) internal successors, (70), 7 states have internal predecessors, (70), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 116 [2024-11-04 15:10:37,574 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:37,575 INFO L225 Difference]: With dead ends: 263 [2024-11-04 15:10:37,575 INFO L226 Difference]: Without dead ends: 146 [2024-11-04 15:10:37,576 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 231 GetRequests, 223 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 15:10:37,577 INFO L432 NwaCegarLoop]: 130 mSDtfsCounter, 40 mSDsluCounter, 555 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 685 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.9s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:37,577 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 685 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 3.9s Time] [2024-11-04 15:10:37,579 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-04 15:10:37,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 140. [2024-11-04 15:10:37,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 91 states have (on average 1.2307692307692308) internal successors, (112), 100 states have internal predecessors, (112), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (47), 33 states have call predecessors, (47), 34 states have call successors, (47) [2024-11-04 15:10:37,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 195 transitions. [2024-11-04 15:10:37,590 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 195 transitions. Word has length 116 [2024-11-04 15:10:37,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:37,590 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 195 transitions. [2024-11-04 15:10:37,590 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 10.0) internal successors, (70), 7 states have internal predecessors, (70), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 15:10:37,590 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 195 transitions. [2024-11-04 15:10:37,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2024-11-04 15:10:37,591 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:37,592 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2024-11-04 15:10:37,613 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:37,792 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:37,792 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:37,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:37,793 INFO L85 PathProgramCache]: Analyzing trace with hash 1128334735, now seen corresponding path program 1 times [2024-11-04 15:10:37,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:37,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [415045250] [2024-11-04 15:10:37,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:37,793 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:37,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:37,794 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:37,795 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-04 15:10:38,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:38,067 INFO L255 TraceCheckSpWp]: Trace formula consists of 457 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 15:10:38,071 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:38,209 INFO L134 CoverageAnalysis]: Checked inductivity of 88 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-04 15:10:38,209 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:38,448 INFO L134 CoverageAnalysis]: Checked inductivity of 88 backedges. 13 proven. 10 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:10:38,449 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:38,449 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [415045250] [2024-11-04 15:10:38,449 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [415045250] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:38,449 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:38,449 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 15:10:38,449 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [443890955] [2024-11-04 15:10:38,449 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:38,450 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:10:38,450 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:38,450 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:10:38,450 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 15:10:38,451 INFO L87 Difference]: Start difference. First operand 140 states and 195 transitions. Second operand has 8 states, 8 states have (on average 9.0) internal successors, (72), 8 states have internal predecessors, (72), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 15:10:43,344 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:43,344 INFO L93 Difference]: Finished difference Result 272 states and 380 transitions. [2024-11-04 15:10:43,345 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 15:10:43,345 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 9.0) internal successors, (72), 8 states have internal predecessors, (72), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 118 [2024-11-04 15:10:43,345 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:43,347 INFO L225 Difference]: With dead ends: 272 [2024-11-04 15:10:43,347 INFO L226 Difference]: Without dead ends: 154 [2024-11-04 15:10:43,348 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 225 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2024-11-04 15:10:43,351 INFO L432 NwaCegarLoop]: 128 mSDtfsCounter, 49 mSDsluCounter, 663 mSDsCounter, 0 mSdLazyCounter, 175 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 791 SdHoareTripleChecker+Invalid, 204 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 175 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.8s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:43,351 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 791 Invalid, 204 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 175 Invalid, 0 Unknown, 0 Unchecked, 4.8s Time] [2024-11-04 15:10:43,351 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 154 states. [2024-11-04 15:10:43,364 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 154 to 141. [2024-11-04 15:10:43,365 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 92 states have (on average 1.2282608695652173) internal successors, (113), 101 states have internal predecessors, (113), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (47), 33 states have call predecessors, (47), 34 states have call successors, (47) [2024-11-04 15:10:43,366 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 196 transitions. [2024-11-04 15:10:43,366 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 196 transitions. Word has length 118 [2024-11-04 15:10:43,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:43,367 INFO L471 AbstractCegarLoop]: Abstraction has 141 states and 196 transitions. [2024-11-04 15:10:43,367 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 9.0) internal successors, (72), 8 states have internal predecessors, (72), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 15:10:43,368 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 196 transitions. [2024-11-04 15:10:43,369 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2024-11-04 15:10:43,369 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:43,369 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:10:43,392 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:43,569 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:43,570 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:43,570 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:43,570 INFO L85 PathProgramCache]: Analyzing trace with hash 1120508411, now seen corresponding path program 1 times [2024-11-04 15:10:43,570 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:43,570 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2071142357] [2024-11-04 15:10:43,570 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:43,571 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:43,571 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:43,572 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:43,573 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-04 15:10:43,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:43,894 INFO L255 TraceCheckSpWp]: Trace formula consists of 471 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-04 15:10:43,897 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:44,074 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 68 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-04 15:10:44,074 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:44,483 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 22 proven. 10 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-04 15:10:44,483 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:44,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2071142357] [2024-11-04 15:10:44,483 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2071142357] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:44,483 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:44,483 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [10] total 13 [2024-11-04 15:10:44,484 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1338155767] [2024-11-04 15:10:44,484 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:44,484 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-04 15:10:44,484 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:44,485 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-04 15:10:44,485 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-11-04 15:10:44,485 INFO L87 Difference]: Start difference. First operand 141 states and 196 transitions. Second operand has 10 states, 10 states have (on average 7.9) internal successors, (79), 10 states have internal predecessors, (79), 5 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-04 15:10:50,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:50,032 INFO L93 Difference]: Finished difference Result 271 states and 376 transitions. [2024-11-04 15:10:50,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-04 15:10:50,033 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 7.9) internal successors, (79), 10 states have internal predecessors, (79), 5 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 127 [2024-11-04 15:10:50,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:50,035 INFO L225 Difference]: With dead ends: 271 [2024-11-04 15:10:50,035 INFO L226 Difference]: Without dead ends: 152 [2024-11-04 15:10:50,036 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 257 GetRequests, 242 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-04 15:10:50,037 INFO L432 NwaCegarLoop]: 128 mSDtfsCounter, 61 mSDsluCounter, 785 mSDsCounter, 0 mSdLazyCounter, 235 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 913 SdHoareTripleChecker+Invalid, 272 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 235 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.5s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:50,037 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 913 Invalid, 272 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 235 Invalid, 0 Unknown, 0 Unchecked, 5.5s Time] [2024-11-04 15:10:50,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2024-11-04 15:10:50,044 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 137. [2024-11-04 15:10:50,044 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 89 states have (on average 1.2359550561797752) internal successors, (110), 97 states have internal predecessors, (110), 36 states have call successors, (36), 8 states have call predecessors, (36), 11 states have return successors, (43), 33 states have call predecessors, (43), 34 states have call successors, (43) [2024-11-04 15:10:50,045 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 189 transitions. [2024-11-04 15:10:50,046 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 189 transitions. Word has length 127 [2024-11-04 15:10:50,046 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:50,046 INFO L471 AbstractCegarLoop]: Abstraction has 137 states and 189 transitions. [2024-11-04 15:10:50,046 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 7.9) internal successors, (79), 10 states have internal predecessors, (79), 5 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2024-11-04 15:10:50,046 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 189 transitions. [2024-11-04 15:10:50,047 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2024-11-04 15:10:50,048 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:50,048 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:10:50,069 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2024-11-04 15:10:50,248 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:50,248 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:50,249 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:50,249 INFO L85 PathProgramCache]: Analyzing trace with hash -1373217537, now seen corresponding path program 2 times [2024-11-04 15:10:50,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:50,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1977741304] [2024-11-04 15:10:50,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:50,249 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:50,249 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:50,250 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:50,251 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-04 15:10:50,544 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:50,551 INFO L255 TraceCheckSpWp]: Trace formula consists of 479 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:10:50,555 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:50,612 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 65 proven. 0 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-04 15:10:50,613 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:50,746 INFO L134 CoverageAnalysis]: Checked inductivity of 98 backedges. 6 proven. 11 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-04 15:10:50,746 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:50,746 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1977741304] [2024-11-04 15:10:50,746 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1977741304] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:50,746 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:50,747 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 15:10:50,747 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1538024730] [2024-11-04 15:10:50,747 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:50,747 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:10:50,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:50,748 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:10:50,748 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:10:50,748 INFO L87 Difference]: Start difference. First operand 137 states and 189 transitions. Second operand has 7 states, 6 states have (on average 12.166666666666666) internal successors, (73), 6 states have internal predecessors, (73), 3 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2024-11-04 15:10:50,836 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:50,837 INFO L93 Difference]: Finished difference Result 261 states and 367 transitions. [2024-11-04 15:10:50,837 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:10:50,837 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 12.166666666666666) internal successors, (73), 6 states have internal predecessors, (73), 3 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 127 [2024-11-04 15:10:50,837 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:50,839 INFO L225 Difference]: With dead ends: 261 [2024-11-04 15:10:50,839 INFO L226 Difference]: Without dead ends: 143 [2024-11-04 15:10:50,840 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 252 GetRequests, 246 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:10:50,840 INFO L432 NwaCegarLoop]: 140 mSDtfsCounter, 0 mSDsluCounter, 679 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 819 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:50,840 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 819 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:10:50,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-04 15:10:50,848 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 140. [2024-11-04 15:10:50,849 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 91 states have (on average 1.2307692307692308) internal successors, (112), 100 states have internal predecessors, (112), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (49), 33 states have call predecessors, (49), 34 states have call successors, (49) [2024-11-04 15:10:50,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 197 transitions. [2024-11-04 15:10:50,850 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 197 transitions. Word has length 127 [2024-11-04 15:10:50,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:50,851 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 197 transitions. [2024-11-04 15:10:50,851 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 12.166666666666666) internal successors, (73), 6 states have internal predecessors, (73), 3 states have call successors, (14), 2 states have call predecessors, (14), 4 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2024-11-04 15:10:50,851 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 197 transitions. [2024-11-04 15:10:50,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2024-11-04 15:10:50,852 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:50,852 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:10:50,874 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:51,052 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:51,053 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:51,053 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:51,053 INFO L85 PathProgramCache]: Analyzing trace with hash 634885234, now seen corresponding path program 1 times [2024-11-04 15:10:51,053 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:51,054 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [976791979] [2024-11-04 15:10:51,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:51,054 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:51,054 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:51,055 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:51,056 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-04 15:10:51,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:51,417 INFO L255 TraceCheckSpWp]: Trace formula consists of 483 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:10:51,420 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:51,458 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 50 proven. 0 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-04 15:10:51,459 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:51,580 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2024-11-04 15:10:51,580 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:51,581 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [976791979] [2024-11-04 15:10:51,581 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [976791979] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:51,581 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:51,581 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 15:10:51,583 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [886858625] [2024-11-04 15:10:51,583 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:51,584 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:10:51,584 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:51,584 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:10:51,584 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:10:51,585 INFO L87 Difference]: Start difference. First operand 140 states and 197 transitions. Second operand has 7 states, 6 states have (on average 11.0) internal successors, (66), 6 states have internal predecessors, (66), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 15:10:51,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:51,678 INFO L93 Difference]: Finished difference Result 261 states and 368 transitions. [2024-11-04 15:10:51,679 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:10:51,679 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 11.0) internal successors, (66), 6 states have internal predecessors, (66), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 129 [2024-11-04 15:10:51,679 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:51,681 INFO L225 Difference]: With dead ends: 261 [2024-11-04 15:10:51,681 INFO L226 Difference]: Without dead ends: 143 [2024-11-04 15:10:51,682 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 256 GetRequests, 250 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:10:51,682 INFO L432 NwaCegarLoop]: 140 mSDtfsCounter, 0 mSDsluCounter, 679 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 819 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:51,682 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 819 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:10:51,683 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-04 15:10:51,689 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 138. [2024-11-04 15:10:51,689 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 90 states have (on average 1.2333333333333334) internal successors, (111), 98 states have internal predecessors, (111), 36 states have call successors, (36), 8 states have call predecessors, (36), 11 states have return successors, (43), 33 states have call predecessors, (43), 34 states have call successors, (43) [2024-11-04 15:10:51,690 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 190 transitions. [2024-11-04 15:10:51,691 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 190 transitions. Word has length 129 [2024-11-04 15:10:51,691 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:51,691 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 190 transitions. [2024-11-04 15:10:51,692 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 11.0) internal successors, (66), 6 states have internal predecessors, (66), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 15:10:51,692 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 190 transitions. [2024-11-04 15:10:51,692 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-04 15:10:51,693 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:51,693 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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] [2024-11-04 15:10:51,715 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:51,893 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:51,893 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:51,894 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:51,894 INFO L85 PathProgramCache]: Analyzing trace with hash 204048799, now seen corresponding path program 1 times [2024-11-04 15:10:51,894 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:51,894 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [715072720] [2024-11-04 15:10:51,894 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:51,894 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:51,894 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:51,895 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:51,896 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-04 15:10:52,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:52,250 INFO L255 TraceCheckSpWp]: Trace formula consists of 487 conjuncts, 23 conjuncts are in the unsatisfiable core [2024-11-04 15:10:52,254 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:56,678 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_5| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (_ bv0 64) (select (select |c_#memory_$Pointer$#1.base| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_5|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|)))) (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_5| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (_ bv0 64) (select (select |c_#memory_$Pointer$#1.offset| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_5|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|))))) is different from true [2024-11-04 15:10:56,891 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 57 proven. 1 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2024-11-04 15:10:56,891 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:57,405 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 0 proven. 29 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2024-11-04 15:10:57,405 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:57,405 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [715072720] [2024-11-04 15:10:57,405 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [715072720] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:10:57,405 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:10:57,405 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 16 [2024-11-04 15:10:57,405 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1272729984] [2024-11-04 15:10:57,406 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:10:57,406 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-04 15:10:57,406 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:57,407 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-04 15:10:57,407 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=171, Unknown=1, NotChecked=26, Total=240 [2024-11-04 15:10:57,407 INFO L87 Difference]: Start difference. First operand 138 states and 190 transitions. Second operand has 16 states, 16 states have (on average 6.9375) internal successors, (111), 16 states have internal predecessors, (111), 4 states have call successors, (22), 3 states have call predecessors, (22), 3 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) [2024-11-04 15:10:59,442 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result INVALID. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-04 15:11:04,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:11:04,117 INFO L93 Difference]: Finished difference Result 292 states and 424 transitions. [2024-11-04 15:11:04,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-04 15:11:04,119 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 6.9375) internal successors, (111), 16 states have internal predecessors, (111), 4 states have call successors, (22), 3 states have call predecessors, (22), 3 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) Word has length 131 [2024-11-04 15:11:04,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:11:04,122 INFO L225 Difference]: With dead ends: 292 [2024-11-04 15:11:04,122 INFO L226 Difference]: Without dead ends: 173 [2024-11-04 15:11:04,125 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 249 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=74, Invalid=309, Unknown=1, NotChecked=36, Total=420 [2024-11-04 15:11:04,125 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 47 mSDsluCounter, 1144 mSDsCounter, 0 mSdLazyCounter, 453 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 1288 SdHoareTripleChecker+Invalid, 765 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 453 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 302 IncrementalHoareTripleChecker+Unchecked, 6.5s IncrementalHoareTripleChecker+Time [2024-11-04 15:11:04,125 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 1288 Invalid, 765 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 453 Invalid, 0 Unknown, 302 Unchecked, 6.5s Time] [2024-11-04 15:11:04,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2024-11-04 15:11:04,138 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 149. [2024-11-04 15:11:04,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 149 states, 100 states have (on average 1.24) internal successors, (124), 106 states have internal predecessors, (124), 36 states have call successors, (36), 9 states have call predecessors, (36), 12 states have return successors, (44), 35 states have call predecessors, (44), 34 states have call successors, (44) [2024-11-04 15:11:04,140 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 204 transitions. [2024-11-04 15:11:04,142 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 204 transitions. Word has length 131 [2024-11-04 15:11:04,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:11:04,142 INFO L471 AbstractCegarLoop]: Abstraction has 149 states and 204 transitions. [2024-11-04 15:11:04,142 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 6.9375) internal successors, (111), 16 states have internal predecessors, (111), 4 states have call successors, (22), 3 states have call predecessors, (22), 3 states have return successors, (21), 4 states have call predecessors, (21), 4 states have call successors, (21) [2024-11-04 15:11:04,142 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 204 transitions. [2024-11-04 15:11:04,144 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 134 [2024-11-04 15:11:04,144 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:11:04,144 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:11:04,168 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2024-11-04 15:11:04,345 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:04,345 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:11:04,346 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:11:04,346 INFO L85 PathProgramCache]: Analyzing trace with hash -883566423, now seen corresponding path program 1 times [2024-11-04 15:11:04,346 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:11:04,346 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [721428957] [2024-11-04 15:11:04,346 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:11:04,346 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:04,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:11:04,347 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:11:04,348 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-04 15:11:04,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:11:04,703 INFO L255 TraceCheckSpWp]: Trace formula consists of 491 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-04 15:11:04,707 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:11:06,018 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-04 15:11:06,023 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-04 15:11:06,076 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 46 proven. 33 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-04 15:11:06,076 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:11:06,599 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 15:11:06,599 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 28 treesize of output 31 [2024-11-04 15:11:06,652 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 15:11:06,653 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 22 treesize of output 25 [2024-11-04 15:11:06,872 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-11-04 15:11:06,873 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:11:06,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [721428957] [2024-11-04 15:11:06,873 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [721428957] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:11:06,873 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:11:06,873 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 15 [2024-11-04 15:11:06,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1976639339] [2024-11-04 15:11:06,873 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:11:06,874 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-04 15:11:06,874 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:11:06,874 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-04 15:11:06,875 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2024-11-04 15:11:06,875 INFO L87 Difference]: Start difference. First operand 149 states and 204 transitions. Second operand has 15 states, 14 states have (on average 7.928571428571429) internal successors, (111), 15 states have internal predecessors, (111), 10 states have call successors, (23), 3 states have call predecessors, (23), 4 states have return successors, (22), 9 states have call predecessors, (22), 10 states have call successors, (22) [2024-11-04 15:11:17,298 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:11:17,298 INFO L93 Difference]: Finished difference Result 444 states and 614 transitions. [2024-11-04 15:11:17,299 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-04 15:11:17,299 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 14 states have (on average 7.928571428571429) internal successors, (111), 15 states have internal predecessors, (111), 10 states have call successors, (23), 3 states have call predecessors, (23), 4 states have return successors, (22), 9 states have call predecessors, (22), 10 states have call successors, (22) Word has length 133 [2024-11-04 15:11:17,300 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:11:17,303 INFO L225 Difference]: With dead ends: 444 [2024-11-04 15:11:17,303 INFO L226 Difference]: Without dead ends: 304 [2024-11-04 15:11:17,304 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 283 GetRequests, 252 SyntacticMatches, 6 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 136 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=118, Invalid=584, Unknown=0, NotChecked=0, Total=702 [2024-11-04 15:11:17,305 INFO L432 NwaCegarLoop]: 186 mSDtfsCounter, 119 mSDsluCounter, 1514 mSDsCounter, 0 mSdLazyCounter, 919 mSolverCounterSat, 73 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 131 SdHoareTripleChecker+Valid, 1700 SdHoareTripleChecker+Invalid, 992 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 73 IncrementalHoareTripleChecker+Valid, 919 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.7s IncrementalHoareTripleChecker+Time [2024-11-04 15:11:17,305 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [131 Valid, 1700 Invalid, 992 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [73 Valid, 919 Invalid, 0 Unknown, 0 Unchecked, 9.7s Time] [2024-11-04 15:11:17,306 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 304 states. [2024-11-04 15:11:17,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 304 to 254. [2024-11-04 15:11:17,329 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 254 states, 172 states have (on average 1.2383720930232558) internal successors, (213), 182 states have internal predecessors, (213), 60 states have call successors, (60), 16 states have call predecessors, (60), 21 states have return successors, (78), 58 states have call predecessors, (78), 56 states have call successors, (78) [2024-11-04 15:11:17,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 254 states to 254 states and 351 transitions. [2024-11-04 15:11:17,331 INFO L78 Accepts]: Start accepts. Automaton has 254 states and 351 transitions. Word has length 133 [2024-11-04 15:11:17,332 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:11:17,332 INFO L471 AbstractCegarLoop]: Abstraction has 254 states and 351 transitions. [2024-11-04 15:11:17,332 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 14 states have (on average 7.928571428571429) internal successors, (111), 15 states have internal predecessors, (111), 10 states have call successors, (23), 3 states have call predecessors, (23), 4 states have return successors, (22), 9 states have call predecessors, (22), 10 states have call successors, (22) [2024-11-04 15:11:17,332 INFO L276 IsEmpty]: Start isEmpty. Operand 254 states and 351 transitions. [2024-11-04 15:11:17,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 144 [2024-11-04 15:11:17,333 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:11:17,334 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:11:17,359 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-11-04 15:11:17,537 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:17,538 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:11:17,538 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:11:17,538 INFO L85 PathProgramCache]: Analyzing trace with hash 708046964, now seen corresponding path program 1 times [2024-11-04 15:11:17,538 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:11:17,538 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1840818267] [2024-11-04 15:11:17,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:11:17,539 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:17,539 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:11:17,540 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:11:17,541 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-11-04 15:11:17,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:11:17,875 INFO L255 TraceCheckSpWp]: Trace formula consists of 507 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-04 15:11:17,878 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:11:17,909 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 75 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2024-11-04 15:11:17,910 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:11:18,074 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 6 proven. 12 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2024-11-04 15:11:18,074 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:11:18,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1840818267] [2024-11-04 15:11:18,074 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1840818267] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:11:18,074 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:11:18,074 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 5 [2024-11-04 15:11:18,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1472753154] [2024-11-04 15:11:18,075 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:11:18,075 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 15:11:18,075 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:11:18,075 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 15:11:18,076 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 15:11:18,076 INFO L87 Difference]: Start difference. First operand 254 states and 351 transitions. Second operand has 5 states, 5 states have (on average 15.2) internal successors, (76), 4 states have internal predecessors, (76), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (14), 3 states have call predecessors, (14), 2 states have call successors, (14) [2024-11-04 15:11:18,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:11:18,117 INFO L93 Difference]: Finished difference Result 493 states and 711 transitions. [2024-11-04 15:11:18,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 15:11:18,118 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 15.2) internal successors, (76), 4 states have internal predecessors, (76), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (14), 3 states have call predecessors, (14), 2 states have call successors, (14) Word has length 143 [2024-11-04 15:11:18,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:11:18,121 INFO L225 Difference]: With dead ends: 493 [2024-11-04 15:11:18,121 INFO L226 Difference]: Without dead ends: 258 [2024-11-04 15:11:18,123 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 284 GetRequests, 281 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 15:11:18,124 INFO L432 NwaCegarLoop]: 145 mSDtfsCounter, 0 mSDsluCounter, 429 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 574 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:11:18,124 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 574 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:11:18,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 258 states. [2024-11-04 15:11:18,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 258 to 256. [2024-11-04 15:11:18,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 256 states, 173 states have (on average 1.2138728323699421) internal successors, (210), 183 states have internal predecessors, (210), 59 states have call successors, (59), 16 states have call predecessors, (59), 23 states have return successors, (78), 59 states have call predecessors, (78), 55 states have call successors, (78) [2024-11-04 15:11:18,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 256 states to 256 states and 347 transitions. [2024-11-04 15:11:18,152 INFO L78 Accepts]: Start accepts. Automaton has 256 states and 347 transitions. Word has length 143 [2024-11-04 15:11:18,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:11:18,152 INFO L471 AbstractCegarLoop]: Abstraction has 256 states and 347 transitions. [2024-11-04 15:11:18,152 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 15.2) internal successors, (76), 4 states have internal predecessors, (76), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (14), 3 states have call predecessors, (14), 2 states have call successors, (14) [2024-11-04 15:11:18,152 INFO L276 IsEmpty]: Start isEmpty. Operand 256 states and 347 transitions. [2024-11-04 15:11:18,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 144 [2024-11-04 15:11:18,153 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:11:18,153 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:11:18,178 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2024-11-04 15:11:18,354 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:18,354 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:11:18,354 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:11:18,355 INFO L85 PathProgramCache]: Analyzing trace with hash 1011515768, now seen corresponding path program 1 times [2024-11-04 15:11:18,355 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:11:18,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1094268567] [2024-11-04 15:11:18,355 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:11:18,355 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:18,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:11:18,356 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:11:18,357 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2024-11-04 15:11:18,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:11:18,700 INFO L255 TraceCheckSpWp]: Trace formula consists of 515 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-04 15:11:18,703 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:11:19,006 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 80 proven. 0 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2024-11-04 15:11:19,006 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:11:19,412 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-04 15:11:19,412 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 23 [2024-11-04 15:11:19,444 INFO L349 Elim1Store]: treesize reduction 10, result has 9.1 percent of original size [2024-11-04 15:11:19,445 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 20 treesize of output 12 [2024-11-04 15:11:19,518 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 9 proven. 15 refuted. 0 times theorem prover too weak. 107 trivial. 0 not checked. [2024-11-04 15:11:19,518 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:11:19,518 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1094268567] [2024-11-04 15:11:19,518 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1094268567] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:11:19,519 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:11:19,519 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 15:11:19,519 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1731911026] [2024-11-04 15:11:19,519 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:11:19,519 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:11:19,519 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:11:19,520 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:11:19,520 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2024-11-04 15:11:19,520 INFO L87 Difference]: Start difference. First operand 256 states and 347 transitions. Second operand has 8 states, 8 states have (on average 9.75) internal successors, (78), 7 states have internal predecessors, (78), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (14), 3 states have call predecessors, (14), 2 states have call successors, (14) [2024-11-04 15:11:24,598 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.07s for a HTC check with result INVALID. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-04 15:11:27,405 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.50s for a HTC check with result INVALID. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:11:27,498 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:11:27,498 INFO L93 Difference]: Finished difference Result 498 states and 687 transitions. [2024-11-04 15:11:27,499 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 15:11:27,499 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 9.75) internal successors, (78), 7 states have internal predecessors, (78), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (14), 3 states have call predecessors, (14), 2 states have call successors, (14) Word has length 143 [2024-11-04 15:11:27,499 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:11:27,502 INFO L225 Difference]: With dead ends: 498 [2024-11-04 15:11:27,502 INFO L226 Difference]: Without dead ends: 264 [2024-11-04 15:11:27,503 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 289 GetRequests, 277 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=39, Invalid=143, Unknown=0, NotChecked=0, Total=182 [2024-11-04 15:11:27,503 INFO L432 NwaCegarLoop]: 148 mSDtfsCounter, 12 mSDsluCounter, 758 mSDsCounter, 0 mSdLazyCounter, 202 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 906 SdHoareTripleChecker+Invalid, 202 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 202 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.8s IncrementalHoareTripleChecker+Time [2024-11-04 15:11:27,504 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [14 Valid, 906 Invalid, 202 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 202 Invalid, 0 Unknown, 0 Unchecked, 7.8s Time] [2024-11-04 15:11:27,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2024-11-04 15:11:27,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 254. [2024-11-04 15:11:27,525 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 254 states, 171 states have (on average 1.1988304093567252) internal successors, (205), 182 states have internal predecessors, (205), 59 states have call successors, (59), 16 states have call predecessors, (59), 23 states have return successors, (78), 58 states have call predecessors, (78), 55 states have call successors, (78) [2024-11-04 15:11:27,526 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 254 states to 254 states and 342 transitions. [2024-11-04 15:11:27,527 INFO L78 Accepts]: Start accepts. Automaton has 254 states and 342 transitions. Word has length 143 [2024-11-04 15:11:27,527 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:11:27,527 INFO L471 AbstractCegarLoop]: Abstraction has 254 states and 342 transitions. [2024-11-04 15:11:27,528 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 9.75) internal successors, (78), 7 states have internal predecessors, (78), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (14), 3 states have call predecessors, (14), 2 states have call successors, (14) [2024-11-04 15:11:27,528 INFO L276 IsEmpty]: Start isEmpty. Operand 254 states and 342 transitions. [2024-11-04 15:11:27,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2024-11-04 15:11:27,529 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:11:27,529 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:11:27,550 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2024-11-04 15:11:27,729 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:27,730 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:11:27,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:11:27,730 INFO L85 PathProgramCache]: Analyzing trace with hash -249505762, now seen corresponding path program 2 times [2024-11-04 15:11:27,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:11:27,730 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1453377458] [2024-11-04 15:11:27,730 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:11:27,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:11:27,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:11:27,732 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:11:27,733 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2024-11-04 15:11:28,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:11:28,120 INFO L255 TraceCheckSpWp]: Trace formula consists of 517 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-04 15:11:28,124 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:11:28,222 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-04 15:11:29,696 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 75 proven. 14 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2024-11-04 15:11:29,696 INFO L311 TraceCheckSpWp]: Computing backward predicates...