/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_end_harness_negated.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 15:07:08,400 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 15:07:08,479 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf [2024-11-04 15:07:08,485 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 15:07:08,486 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 15:07:08,509 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 15:07:08,510 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 15:07:08,510 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 15:07:08,511 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 15:07:08,511 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 15:07:08,512 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 15:07:08,512 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 15:07:08,513 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 15:07:08,513 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 15:07:08,513 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 15:07:08,514 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 15:07:08,514 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 15:07:08,514 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 15:07:08,515 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 15:07:08,515 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 15:07:08,518 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 15:07:08,518 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 15:07:08,519 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 15:07:08,519 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 15:07:08,519 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 15:07:08,519 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 15:07:08,520 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 15:07:08,520 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 15:07:08,520 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 15:07:08,521 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 15:07:08,521 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 15:07:08,521 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:07:08,521 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 15:07:08,522 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 15:07:08,526 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 15:07:08,526 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 15:07:08,527 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 15:07:08,527 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 15:07:08,527 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 15:07:08,527 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 15:07:08,528 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 15:07:08,528 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Trace refinement strategy -> FIXED_PREFERENCES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Allow undefined functions -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMT solver -> External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Command for external solver -> z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:08,775 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 15:07:08,803 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 15:07:08,805 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 15:07:08,806 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 15:07:08,806 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 15:07:08,807 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_end_harness_negated.i [2024-11-04 15:07:10,273 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 15:07:10,686 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 15:07:10,687 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_end_harness_negated.i [2024-11-04 15:07:10,724 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ac4421413/9a2daddabfb647e4b201f98f3afb1584/FLAG965b04e85 [2024-11-04 15:07:10,740 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ac4421413/9a2daddabfb647e4b201f98f3afb1584 [2024-11-04 15:07:10,742 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 15:07:10,743 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 15:07:10,745 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 15:07:10,745 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 15:07:10,751 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 15:07:10,752 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:07:10" (1/1) ... [2024-11-04 15:07:10,753 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5d5e6f21 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:10, skipping insertion in model container [2024-11-04 15:07:10,754 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:07:10" (1/1) ... [2024-11-04 15:07:10,845 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:07:11,146 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_end_harness_negated.i[4493,4506] [2024-11-04 15:07:11,157 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_end_harness_negated.i[4553,4566] [2024-11-04 15:07:11,711 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,818 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,818 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,819 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,837 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,839 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,840 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,840 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,841 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,841 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,842 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,846 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,847 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,849 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,849 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,862 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,863 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,863 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,865 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,867 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,867 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,867 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,868 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,870 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,872 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,873 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,873 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:11,873 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:11,874 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,201 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,201 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,202 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,202 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,298 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,309 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:07:12,327 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 15:07:12,345 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:07:12,349 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_end_harness_negated.i[4493,4506] [2024-11-04 15:07:12,349 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_end_harness_negated.i[4553,4566] [2024-11-04 15:07:12,374 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,389 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,389 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,390 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,397 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,402 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,402 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,402 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,403 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,403 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,403 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,405 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,405 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,410 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,411 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,419 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,419 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,419 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,419 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,424 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,425 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,425 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,425 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,426 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,427 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,427 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,427 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,427 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,427 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,482 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,482 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,483 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,483 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,526 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:07:12,538 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:07:12,546 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 15:07:12,565 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_end_harness_negated.i[4493,4506] [2024-11-04 15:07:12,565 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_end_harness_negated.i[4553,4566] [2024-11-04 15:07:12,618 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,619 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,619 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,619 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,620 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,627 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,628 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,628 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,629 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,631 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,632 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,632 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,632 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:07:12,722 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:07:12,923 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 15:07:12,931 INFO L204 MainTranslator]: Completed translation [2024-11-04 15:07:12,932 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12 WrapperNode [2024-11-04 15:07:12,932 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 15:07:12,933 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 15:07:12,933 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 15:07:12,933 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 15:07:12,942 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,006 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,047 INFO L138 Inliner]: procedures = 687, calls = 1038, calls flagged for inlining = 52, calls inlined = 6, statements flattened = 138 [2024-11-04 15:07:13,048 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 15:07:13,048 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 15:07:13,049 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 15:07:13,049 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 15:07:13,059 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,059 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,064 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,097 INFO L175 MemorySlicer]: Split 21 memory accesses to 3 slices as follows [2, 5, 14]. 67 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0]. The 6 writes are split as follows [0, 0, 6]. [2024-11-04 15:07:13,098 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,098 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,120 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,130 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,135 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,137 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,147 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 15:07:13,148 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 15:07:13,148 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 15:07:13,148 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 15:07:13,148 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (1/1) ... [2024-11-04 15:07:13,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:07:13,167 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:13,181 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-04 15:07:13,184 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-04 15:07:13,208 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 15:07:13,209 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 15:07:13,209 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 15:07:13,209 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 15:07:13,210 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 15:07:13,210 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 15:07:13,210 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:07:13,210 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:07:13,210 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-04 15:07:13,210 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-04 15:07:13,210 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-04 15:07:13,210 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 15:07:13,210 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 15:07:13,211 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 15:07:13,211 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 15:07:13,211 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 15:07:13,212 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 15:07:13,212 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 15:07:13,212 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 15:07:13,212 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-04 15:07:13,212 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-04 15:07:13,479 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 15:07:13,482 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 15:07:13,805 INFO L? ?]: Removed 54 outVars from TransFormulas that were not future-live. [2024-11-04 15:07:13,805 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 15:07:13,846 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 15:07:13,847 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-04 15:07:13,847 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:07:13 BoogieIcfgContainer [2024-11-04 15:07:13,847 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 15:07:13,850 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 15:07:13,850 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 15:07:13,853 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 15:07:13,853 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 03:07:10" (1/3) ... [2024-11-04 15:07:13,854 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f876f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:07:13, skipping insertion in model container [2024-11-04 15:07:13,854 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:07:12" (2/3) ... [2024-11-04 15:07:13,854 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1f876f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:07:13, skipping insertion in model container [2024-11-04 15:07:13,855 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:07:13" (3/3) ... [2024-11-04 15:07:13,856 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_end_harness_negated.i [2024-11-04 15:07:13,869 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 15:07:13,869 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 15:07:13,934 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 15:07:13,940 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;@3a4787e5, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 15:07:13,940 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 15:07:13,944 INFO L276 IsEmpty]: Start isEmpty. Operand has 68 states, 48 states have (on average 1.3541666666666667) internal successors, (65), 49 states have internal predecessors, (65), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-04 15:07:13,953 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-04 15:07:13,954 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:13,954 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:13,955 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:13,959 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:13,959 INFO L85 PathProgramCache]: Analyzing trace with hash -2107862704, now seen corresponding path program 1 times [2024-11-04 15:07:13,967 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:13,967 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2041009248] [2024-11-04 15:07:13,967 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:13,970 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:13,970 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:13,973 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:13,974 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-04 15:07:14,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:14,217 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 15:07:14,225 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:14,260 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-04 15:07:14,261 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:14,304 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-04 15:07:14,305 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:14,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2041009248] [2024-11-04 15:07:14,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2041009248] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:14,306 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:14,306 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-04 15:07:14,308 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1246090261] [2024-11-04 15:07:14,309 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:14,312 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 15:07:14,314 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:14,335 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 15:07:14,335 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 15:07:14,338 INFO L87 Difference]: Start difference. First operand has 68 states, 48 states have (on average 1.3541666666666667) internal successors, (65), 49 states have internal predecessors, (65), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 14.5) internal successors, (29), 2 states have internal predecessors, (29), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:14,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:14,367 INFO L93 Difference]: Finished difference Result 128 states and 184 transitions. [2024-11-04 15:07:14,368 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 15:07:14,369 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 14.5) internal successors, (29), 2 states have internal predecessors, (29), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 68 [2024-11-04 15:07:14,369 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:14,375 INFO L225 Difference]: With dead ends: 128 [2024-11-04 15:07:14,375 INFO L226 Difference]: Without dead ends: 63 [2024-11-04 15:07:14,378 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 134 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 15:07:14,380 INFO L432 NwaCegarLoop]: 87 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, 87 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:14,381 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:14,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-04 15:07:14,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2024-11-04 15:07:14,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 44 states have (on average 1.2954545454545454) internal successors, (57), 45 states have internal predecessors, (57), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-04 15:07:14,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 82 transitions. [2024-11-04 15:07:14,415 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 82 transitions. Word has length 68 [2024-11-04 15:07:14,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:14,415 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 82 transitions. [2024-11-04 15:07:14,416 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 14.5) internal successors, (29), 2 states have internal predecessors, (29), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:14,416 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 82 transitions. [2024-11-04 15:07:14,418 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-04 15:07:14,418 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:14,418 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:14,438 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-04 15:07:14,622 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:14,623 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:14,624 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:14,624 INFO L85 PathProgramCache]: Analyzing trace with hash 900796622, now seen corresponding path program 1 times [2024-11-04 15:07:14,624 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:14,624 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1730196617] [2024-11-04 15:07:14,624 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:14,624 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:14,625 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:14,626 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:14,627 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-04 15:07:14,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:14,856 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:07:14,861 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:14,938 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 33 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-04 15:07:14,939 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:15,037 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 3 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-04 15:07:15,038 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:15,038 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1730196617] [2024-11-04 15:07:15,038 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1730196617] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:15,038 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:15,038 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 15:07:15,039 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1733666509] [2024-11-04 15:07:15,039 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:15,040 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:07:15,040 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:15,041 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:07:15,041 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:07:15,041 INFO L87 Difference]: Start difference. First operand 63 states and 82 transitions. Second operand has 6 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 3 states have call successors, (8), 2 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-04 15:07:15,120 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:15,120 INFO L93 Difference]: Finished difference Result 114 states and 152 transitions. [2024-11-04 15:07:15,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:07:15,121 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 3 states have call successors, (8), 2 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) Word has length 68 [2024-11-04 15:07:15,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:15,128 INFO L225 Difference]: With dead ends: 114 [2024-11-04 15:07:15,128 INFO L226 Difference]: Without dead ends: 65 [2024-11-04 15:07:15,129 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 129 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:07:15,130 INFO L432 NwaCegarLoop]: 78 mSDtfsCounter, 0 mSDsluCounter, 299 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 377 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:15,130 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 377 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:07:15,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-11-04 15:07:15,144 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2024-11-04 15:07:15,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 45 states have (on average 1.288888888888889) internal successors, (58), 47 states have internal predecessors, (58), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (15), 12 states have call predecessors, (15), 12 states have call successors, (15) [2024-11-04 15:07:15,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 86 transitions. [2024-11-04 15:07:15,147 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 86 transitions. Word has length 68 [2024-11-04 15:07:15,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:15,147 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 86 transitions. [2024-11-04 15:07:15,148 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 3 states have call successors, (8), 2 states have call predecessors, (8), 4 states have return successors, (7), 3 states have call predecessors, (7), 3 states have call successors, (7) [2024-11-04 15:07:15,148 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 86 transitions. [2024-11-04 15:07:15,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-04 15:07:15,150 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:15,152 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:15,173 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:15,352 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:15,353 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:15,354 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:15,354 INFO L85 PathProgramCache]: Analyzing trace with hash 577933322, now seen corresponding path program 1 times [2024-11-04 15:07:15,354 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:15,354 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [546369029] [2024-11-04 15:07:15,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:15,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:15,354 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:15,356 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:15,358 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-04 15:07:15,530 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:15,535 INFO L255 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:07:15,538 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:15,620 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-04 15:07:15,620 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:15,794 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-04 15:07:15,795 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:15,795 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [546369029] [2024-11-04 15:07:15,795 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [546369029] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:15,795 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:15,795 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2024-11-04 15:07:15,795 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [747949431] [2024-11-04 15:07:15,796 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:15,796 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:07:15,796 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:15,797 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:07:15,797 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:15,797 INFO L87 Difference]: Start difference. First operand 65 states and 86 transitions. Second operand has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:15,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:15,931 INFO L93 Difference]: Finished difference Result 121 states and 163 transitions. [2024-11-04 15:07:15,932 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:07:15,932 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 70 [2024-11-04 15:07:15,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:15,934 INFO L225 Difference]: With dead ends: 121 [2024-11-04 15:07:15,934 INFO L226 Difference]: Without dead ends: 70 [2024-11-04 15:07:15,935 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 132 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:15,935 INFO L432 NwaCegarLoop]: 71 mSDtfsCounter, 20 mSDsluCounter, 229 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 300 SdHoareTripleChecker+Invalid, 80 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:15,936 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [35 Valid, 300 Invalid, 80 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:07:15,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-04 15:07:15,950 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2024-11-04 15:07:15,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 47 states have (on average 1.2765957446808511) internal successors, (60), 50 states have internal predecessors, (60), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (17), 12 states have call predecessors, (17), 12 states have call successors, (17) [2024-11-04 15:07:15,953 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 90 transitions. [2024-11-04 15:07:15,954 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 90 transitions. Word has length 70 [2024-11-04 15:07:15,954 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:15,954 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 90 transitions. [2024-11-04 15:07:15,957 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 7.0) internal successors, (42), 6 states have internal predecessors, (42), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:15,957 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 90 transitions. [2024-11-04 15:07:15,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-04 15:07:15,959 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:15,959 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:15,982 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:07:16,159 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:16,160 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:16,161 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:16,161 INFO L85 PathProgramCache]: Analyzing trace with hash -34807881, now seen corresponding path program 1 times [2024-11-04 15:07:16,161 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:16,161 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1461318557] [2024-11-04 15:07:16,161 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:16,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:16,161 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:16,163 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:16,164 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-04 15:07:16,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:16,330 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 15:07:16,334 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:16,427 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-04 15:07:16,427 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:16,604 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-04 15:07:16,605 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:16,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1461318557] [2024-11-04 15:07:16,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1461318557] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:16,605 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:16,605 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 10 [2024-11-04 15:07:16,605 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [230822595] [2024-11-04 15:07:16,605 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:16,606 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:07:16,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:16,607 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:07:16,607 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 15:07:16,607 INFO L87 Difference]: Start difference. First operand 68 states and 90 transitions. Second operand has 7 states, 7 states have (on average 6.285714285714286) internal successors, (44), 7 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:16,800 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:16,800 INFO L93 Difference]: Finished difference Result 133 states and 181 transitions. [2024-11-04 15:07:16,801 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 15:07:16,801 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 6.285714285714286) internal successors, (44), 7 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 72 [2024-11-04 15:07:16,801 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:16,803 INFO L225 Difference]: With dead ends: 133 [2024-11-04 15:07:16,803 INFO L226 Difference]: Without dead ends: 79 [2024-11-04 15:07:16,804 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 134 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2024-11-04 15:07:16,804 INFO L432 NwaCegarLoop]: 69 mSDtfsCounter, 29 mSDsluCounter, 285 mSDsCounter, 0 mSdLazyCounter, 117 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 354 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 117 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:16,805 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 354 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 117 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 15:07:16,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2024-11-04 15:07:16,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 70. [2024-11-04 15:07:16,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 49 states have (on average 1.2857142857142858) internal successors, (63), 52 states have internal predecessors, (63), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (17), 12 states have call predecessors, (17), 12 states have call successors, (17) [2024-11-04 15:07:16,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 93 transitions. [2024-11-04 15:07:16,818 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 93 transitions. Word has length 72 [2024-11-04 15:07:16,821 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:16,821 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 93 transitions. [2024-11-04 15:07:16,821 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 6.285714285714286) internal successors, (44), 7 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:16,821 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 93 transitions. [2024-11-04 15:07:16,822 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-04 15:07:16,822 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:16,823 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:16,841 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:17,023 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:17,023 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:17,024 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:17,024 INFO L85 PathProgramCache]: Analyzing trace with hash 387052583, now seen corresponding path program 1 times [2024-11-04 15:07:17,024 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:17,024 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2098287535] [2024-11-04 15:07:17,024 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:17,025 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:17,025 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:17,026 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:17,027 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-04 15:07:17,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:17,211 INFO L255 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-04 15:07:17,214 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:17,226 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 26 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-04 15:07:17,226 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:17,269 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-04 15:07:17,270 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:17,270 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2098287535] [2024-11-04 15:07:17,270 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2098287535] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:17,270 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:17,270 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 4 [2024-11-04 15:07:17,271 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1130308462] [2024-11-04 15:07:17,271 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:17,271 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-04 15:07:17,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:17,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-04 15:07:17,272 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:17,272 INFO L87 Difference]: Start difference. First operand 70 states and 93 transitions. Second operand has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:17,302 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:17,302 INFO L93 Difference]: Finished difference Result 130 states and 180 transitions. [2024-11-04 15:07:17,303 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-04 15:07:17,303 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 73 [2024-11-04 15:07:17,304 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:17,305 INFO L225 Difference]: With dead ends: 130 [2024-11-04 15:07:17,305 INFO L226 Difference]: Without dead ends: 74 [2024-11-04 15:07:17,306 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:17,306 INFO L432 NwaCegarLoop]: 79 mSDtfsCounter, 2 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 152 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:07:17,307 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 152 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:17,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-04 15:07:17,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2024-11-04 15:07:17,323 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 50 states have (on average 1.28) internal successors, (64), 53 states have internal predecessors, (64), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (17), 12 states have call predecessors, (17), 12 states have call successors, (17) [2024-11-04 15:07:17,324 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2024-11-04 15:07:17,324 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 73 [2024-11-04 15:07:17,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:17,325 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2024-11-04 15:07:17,325 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 14.666666666666666) internal successors, (44), 3 states have internal predecessors, (44), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-04 15:07:17,325 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2024-11-04 15:07:17,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-04 15:07:17,328 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:17,329 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:17,350 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:17,529 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:17,530 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:17,530 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:17,530 INFO L85 PathProgramCache]: Analyzing trace with hash 1595103561, now seen corresponding path program 1 times [2024-11-04 15:07:17,530 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:17,531 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [235311211] [2024-11-04 15:07:17,531 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:17,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:17,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:17,533 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:17,534 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-04 15:07:17,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:17,705 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:07:17,707 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:17,742 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-04 15:07:17,742 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:17,822 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-04 15:07:17,823 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:17,823 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [235311211] [2024-11-04 15:07:17,823 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [235311211] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:17,823 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:17,823 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 15:07:17,823 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [673728702] [2024-11-04 15:07:17,823 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:17,824 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:07:17,824 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:17,824 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:07:17,825 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:07:17,825 INFO L87 Difference]: Start difference. First operand 71 states and 94 transitions. Second operand has 6 states, 5 states have (on average 10.6) internal successors, (53), 5 states have internal predecessors, (53), 3 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-04 15:07:17,873 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:17,874 INFO L93 Difference]: Finished difference Result 121 states and 161 transitions. [2024-11-04 15:07:17,874 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:07:17,874 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 10.6) internal successors, (53), 5 states have internal predecessors, (53), 3 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 81 [2024-11-04 15:07:17,875 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:17,876 INFO L225 Difference]: With dead ends: 121 [2024-11-04 15:07:17,876 INFO L226 Difference]: Without dead ends: 71 [2024-11-04 15:07:17,876 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 155 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:07:17,877 INFO L432 NwaCegarLoop]: 78 mSDtfsCounter, 0 mSDsluCounter, 298 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 376 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:17,877 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 376 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:17,880 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-04 15:07:17,887 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2024-11-04 15:07:17,889 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 50 states have (on average 1.28) internal successors, (64), 53 states have internal predecessors, (64), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (16), 12 states have call predecessors, (16), 12 states have call successors, (16) [2024-11-04 15:07:17,890 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 93 transitions. [2024-11-04 15:07:17,890 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 93 transitions. Word has length 81 [2024-11-04 15:07:17,891 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:17,891 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 93 transitions. [2024-11-04 15:07:17,891 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 10.6) internal successors, (53), 5 states have internal predecessors, (53), 3 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-04 15:07:17,891 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 93 transitions. [2024-11-04 15:07:17,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-11-04 15:07:17,892 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:17,892 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:17,912 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:18,096 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:18,097 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:18,097 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:18,097 INFO L85 PathProgramCache]: Analyzing trace with hash -1338639547, now seen corresponding path program 1 times [2024-11-04 15:07:18,097 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:18,098 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2087669421] [2024-11-04 15:07:18,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:18,098 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:18,098 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:18,099 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:18,100 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-04 15:07:18,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:18,265 INFO L255 TraceCheckSpWp]: Trace formula consists of 247 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 15:07:18,268 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:18,350 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-04 15:07:18,350 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:18,523 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-04 15:07:18,524 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:18,524 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2087669421] [2024-11-04 15:07:18,524 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2087669421] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:18,524 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:18,524 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2024-11-04 15:07:18,524 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1338518967] [2024-11-04 15:07:18,524 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:18,525 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:07:18,525 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:18,525 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:07:18,526 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:07:18,526 INFO L87 Difference]: Start difference. First operand 71 states and 93 transitions. Second operand has 7 states, 6 states have (on average 10.5) internal successors, (63), 7 states have internal predecessors, (63), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-04 15:07:18,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:18,674 INFO L93 Difference]: Finished difference Result 130 states and 169 transitions. [2024-11-04 15:07:18,674 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:07:18,674 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 10.5) internal successors, (63), 7 states have internal predecessors, (63), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 83 [2024-11-04 15:07:18,675 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:18,675 INFO L225 Difference]: With dead ends: 130 [2024-11-04 15:07:18,676 INFO L226 Difference]: Without dead ends: 73 [2024-11-04 15:07:18,676 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 165 GetRequests, 157 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:07:18,677 INFO L432 NwaCegarLoop]: 71 mSDtfsCounter, 23 mSDsluCounter, 293 mSDsCounter, 0 mSdLazyCounter, 82 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 82 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:18,677 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [27 Valid, 364 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 82 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:07:18,678 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-04 15:07:18,684 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2024-11-04 15:07:18,684 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 50 states have (on average 1.26) internal successors, (63), 53 states have internal predecessors, (63), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (16), 12 states have call predecessors, (16), 12 states have call successors, (16) [2024-11-04 15:07:18,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 92 transitions. [2024-11-04 15:07:18,685 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 92 transitions. Word has length 83 [2024-11-04 15:07:18,686 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:18,686 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 92 transitions. [2024-11-04 15:07:18,686 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 10.5) internal successors, (63), 7 states have internal predecessors, (63), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-04 15:07:18,686 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 92 transitions. [2024-11-04 15:07:18,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2024-11-04 15:07:18,687 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:18,687 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:18,706 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2024-11-04 15:07:18,888 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:18,888 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:18,889 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:18,889 INFO L85 PathProgramCache]: Analyzing trace with hash 1040869362, now seen corresponding path program 1 times [2024-11-04 15:07:18,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:18,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [843769394] [2024-11-04 15:07:18,889 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:18,889 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:18,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:18,890 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:18,891 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-04 15:07:19,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:19,058 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 15:07:19,061 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:19,165 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-04 15:07:19,165 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:19,334 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 13 proven. 10 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-04 15:07:19,335 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:19,335 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [843769394] [2024-11-04 15:07:19,335 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [843769394] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:19,335 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:19,335 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 15:07:19,335 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1218347374] [2024-11-04 15:07:19,335 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:19,336 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:07:19,336 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:19,336 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:07:19,336 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 15:07:19,337 INFO L87 Difference]: Start difference. First operand 71 states and 92 transitions. Second operand has 8 states, 7 states have (on average 9.285714285714286) internal successors, (65), 8 states have internal predecessors, (65), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-04 15:07:19,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:19,514 INFO L93 Difference]: Finished difference Result 130 states and 168 transitions. [2024-11-04 15:07:19,515 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 15:07:19,515 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 9.285714285714286) internal successors, (65), 8 states have internal predecessors, (65), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 85 [2024-11-04 15:07:19,516 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:19,517 INFO L225 Difference]: With dead ends: 130 [2024-11-04 15:07:19,517 INFO L226 Difference]: Without dead ends: 72 [2024-11-04 15:07:19,518 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 159 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:07:19,519 INFO L432 NwaCegarLoop]: 68 mSDtfsCounter, 32 mSDsluCounter, 342 mSDsCounter, 0 mSdLazyCounter, 113 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 410 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 113 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:19,519 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 410 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 113 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:07:19,520 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-11-04 15:07:19,525 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 67. [2024-11-04 15:07:19,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 47 states have (on average 1.2553191489361701) internal successors, (59), 49 states have internal predecessors, (59), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2024-11-04 15:07:19,526 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 86 transitions. [2024-11-04 15:07:19,527 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 86 transitions. Word has length 85 [2024-11-04 15:07:19,527 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:19,527 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 86 transitions. [2024-11-04 15:07:19,527 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 9.285714285714286) internal successors, (65), 8 states have internal predecessors, (65), 4 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-04 15:07:19,527 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 86 transitions. [2024-11-04 15:07:19,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2024-11-04 15:07:19,528 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:19,528 INFO L215 NwaCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:19,550 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-04 15:07:19,729 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:19,729 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:19,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:19,730 INFO L85 PathProgramCache]: Analyzing trace with hash -1678268318, now seen corresponding path program 2 times [2024-11-04 15:07:19,730 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:19,730 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [296445421] [2024-11-04 15:07:19,730 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:19,730 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:19,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:19,732 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:19,755 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-04 15:07:19,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:19,933 INFO L255 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:07:19,936 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:19,977 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2024-11-04 15:07:19,978 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:20,068 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 47 trivial. 0 not checked. [2024-11-04 15:07:20,069 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:20,069 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [296445421] [2024-11-04 15:07:20,069 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [296445421] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:20,069 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:20,069 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 15:07:20,069 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2060885268] [2024-11-04 15:07:20,070 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:20,070 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:07:20,070 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:20,071 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:07:20,071 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:20,073 INFO L87 Difference]: Start difference. First operand 67 states and 86 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, (10), 2 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-04 15:07:20,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:20,125 INFO L93 Difference]: Finished difference Result 123 states and 161 transitions. [2024-11-04 15:07:20,126 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:07:20,126 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, (10), 2 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 94 [2024-11-04 15:07:20,127 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:20,128 INFO L225 Difference]: With dead ends: 123 [2024-11-04 15:07:20,128 INFO L226 Difference]: Without dead ends: 70 [2024-11-04 15:07:20,128 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 180 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:20,129 INFO L432 NwaCegarLoop]: 76 mSDtfsCounter, 0 mSDsluCounter, 365 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 441 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:20,129 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 441 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:20,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-04 15:07:20,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 70. [2024-11-04 15:07:20,137 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 49 states have (on average 1.2448979591836735) internal successors, (61), 52 states have internal predecessors, (61), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (17), 12 states have call predecessors, (17), 12 states have call successors, (17) [2024-11-04 15:07:20,137 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 91 transitions. [2024-11-04 15:07:20,138 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 91 transitions. Word has length 94 [2024-11-04 15:07:20,138 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:20,138 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 91 transitions. [2024-11-04 15:07:20,138 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, (10), 2 states have call predecessors, (10), 4 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2024-11-04 15:07:20,138 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 91 transitions. [2024-11-04 15:07:20,139 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-04 15:07:20,139 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:20,140 INFO L215 NwaCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:20,159 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2024-11-04 15:07:20,345 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:20,346 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:20,346 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:20,346 INFO L85 PathProgramCache]: Analyzing trace with hash -1005701739, now seen corresponding path program 1 times [2024-11-04 15:07:20,346 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:20,347 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1971931084] [2024-11-04 15:07:20,347 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:20,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:20,347 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:20,349 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:20,350 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2024-11-04 15:07:20,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:20,540 INFO L255 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:07:20,543 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:20,584 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 31 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-04 15:07:20,584 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:20,671 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 2 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2024-11-04 15:07:20,671 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:20,671 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1971931084] [2024-11-04 15:07:20,671 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1971931084] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:20,672 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:20,672 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 15:07:20,672 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1551084303] [2024-11-04 15:07:20,672 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:20,672 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:07:20,673 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:20,673 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:07:20,673 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:20,673 INFO L87 Difference]: Start difference. First operand 70 states and 91 transitions. Second operand has 7 states, 6 states have (on average 9.333333333333334) internal successors, (56), 6 states have internal predecessors, (56), 3 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-04 15:07:20,719 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:20,719 INFO L93 Difference]: Finished difference Result 119 states and 156 transitions. [2024-11-04 15:07:20,719 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:07:20,719 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 9.333333333333334) internal successors, (56), 6 states have internal predecessors, (56), 3 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 96 [2024-11-04 15:07:20,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:20,721 INFO L225 Difference]: With dead ends: 119 [2024-11-04 15:07:20,721 INFO L226 Difference]: Without dead ends: 70 [2024-11-04 15:07:20,721 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 184 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:20,722 INFO L432 NwaCegarLoop]: 76 mSDtfsCounter, 0 mSDsluCounter, 364 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 440 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:20,722 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 440 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:20,723 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-04 15:07:20,727 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2024-11-04 15:07:20,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 48 states have (on average 1.25) internal successors, (60), 50 states have internal predecessors, (60), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2024-11-04 15:07:20,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 87 transitions. [2024-11-04 15:07:20,728 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 87 transitions. Word has length 96 [2024-11-04 15:07:20,729 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:20,729 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 87 transitions. [2024-11-04 15:07:20,729 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 9.333333333333334) internal successors, (56), 6 states have internal predecessors, (56), 3 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-04 15:07:20,729 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 87 transitions. [2024-11-04 15:07:20,730 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-04 15:07:20,730 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:20,730 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-04 15:07:20,751 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2024-11-04 15:07:20,930 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:20,931 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:20,931 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:20,931 INFO L85 PathProgramCache]: Analyzing trace with hash -1128444350, now seen corresponding path program 1 times [2024-11-04 15:07:20,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:20,932 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [820764976] [2024-11-04 15:07:20,932 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:20,932 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:20,932 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:20,933 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:20,934 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-11-04 15:07:21,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:21,096 INFO L255 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-04 15:07:21,100 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:21,155 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:07:21,160 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:07:25,488 WARN L873 $PredicateComparison]: unable to prove that (or (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (select (select |c_#memory_$Pointer$#2.base| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|) (_ bv0 64)))) (exists ((|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1| (_ BitVec 64)) (|v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1| (_ BitVec 64))) (not (= (_ bv0 64) (select (select |c_#memory_$Pointer$#2.offset| |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.base_BEFORE_CALL_1|) |v_aws_linked_list_is_valid_aws_linked_list_is_valid_deep_~temp~0#1.offset_BEFORE_CALL_1|))))) is different from true [2024-11-04 15:07:25,770 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 41 proven. 1 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2024-11-04 15:07:25,770 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:26,174 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 0 proven. 29 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-04 15:07:26,174 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:26,175 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [820764976] [2024-11-04 15:07:26,175 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [820764976] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:07:26,175 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:07:26,175 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2024-11-04 15:07:26,175 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1460421673] [2024-11-04 15:07:26,175 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:07:26,176 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-04 15:07:26,176 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:26,176 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-04 15:07:26,177 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=199, Unknown=1, NotChecked=28, Total=272 [2024-11-04 15:07:26,177 INFO L87 Difference]: Start difference. First operand 68 states and 87 transitions. Second operand has 17 states, 17 states have (on average 6.235294117647059) internal successors, (106), 17 states have internal predecessors, (106), 5 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2024-11-04 15:07:27,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:27,207 INFO L93 Difference]: Finished difference Result 166 states and 228 transitions. [2024-11-04 15:07:27,208 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 15:07:27,208 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 6.235294117647059) internal successors, (106), 17 states have internal predecessors, (106), 5 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 98 [2024-11-04 15:07:27,209 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:27,210 INFO L225 Difference]: With dead ends: 166 [2024-11-04 15:07:27,210 INFO L226 Difference]: Without dead ends: 112 [2024-11-04 15:07:27,211 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 182 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=76, Invalid=347, Unknown=1, NotChecked=38, Total=462 [2024-11-04 15:07:27,212 INFO L432 NwaCegarLoop]: 77 mSDtfsCounter, 64 mSDsluCounter, 637 mSDsCounter, 0 mSdLazyCounter, 369 mSolverCounterSat, 13 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 66 SdHoareTripleChecker+Valid, 714 SdHoareTripleChecker+Invalid, 651 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 369 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 268 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:27,212 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [66 Valid, 714 Invalid, 651 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 369 Invalid, 1 Unknown, 268 Unchecked, 0.8s Time] [2024-11-04 15:07:27,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2024-11-04 15:07:27,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 86. [2024-11-04 15:07:27,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.28125) internal successors, (82), 66 states have internal predecessors, (82), 14 states have call successors, (14), 6 states have call predecessors, (14), 7 states have return successors, (16), 13 states have call predecessors, (16), 13 states have call successors, (16) [2024-11-04 15:07:27,225 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 112 transitions. [2024-11-04 15:07:27,226 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 112 transitions. Word has length 98 [2024-11-04 15:07:27,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:27,226 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 112 transitions. [2024-11-04 15:07:27,226 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 6.235294117647059) internal successors, (106), 17 states have internal predecessors, (106), 5 states have call successors, (18), 3 states have call predecessors, (18), 3 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2024-11-04 15:07:27,226 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 112 transitions. [2024-11-04 15:07:27,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-04 15:07:27,227 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:27,227 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-04 15:07:27,246 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-11-04 15:07:27,428 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:27,428 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:27,428 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:27,428 INFO L85 PathProgramCache]: Analyzing trace with hash 604075650, now seen corresponding path program 1 times [2024-11-04 15:07:27,429 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:27,429 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1399876811] [2024-11-04 15:07:27,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:27,429 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:27,429 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:27,430 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:07:27,431 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-04 15:07:27,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:27,585 INFO L255 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:07:27,586 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:27,600 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-04 15:07:27,601 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:27,640 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 0 proven. 24 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-04 15:07:27,641 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:27,641 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1399876811] [2024-11-04 15:07:27,641 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1399876811] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:27,641 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:27,641 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:07:27,641 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1176635071] [2024-11-04 15:07:27,641 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:27,642 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:07:27,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:27,642 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:07:27,642 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:27,643 INFO L87 Difference]: Start difference. First operand 86 states and 112 transitions. Second operand has 4 states, 4 states have (on average 12.75) internal successors, (51), 4 states have internal predecessors, (51), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-04 15:07:27,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:27,668 INFO L93 Difference]: Finished difference Result 159 states and 214 transitions. [2024-11-04 15:07:27,669 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:07:27,669 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 12.75) internal successors, (51), 4 states have internal predecessors, (51), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 98 [2024-11-04 15:07:27,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:27,670 INFO L225 Difference]: With dead ends: 159 [2024-11-04 15:07:27,670 INFO L226 Difference]: Without dead ends: 87 [2024-11-04 15:07:27,671 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 192 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:27,671 INFO L432 NwaCegarLoop]: 81 mSDtfsCounter, 0 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 231 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:27,671 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 231 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:27,672 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2024-11-04 15:07:27,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 86. [2024-11-04 15:07:27,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 86 states, 64 states have (on average 1.265625) internal successors, (81), 66 states have internal predecessors, (81), 14 states have call successors, (14), 6 states have call predecessors, (14), 7 states have return successors, (16), 13 states have call predecessors, (16), 13 states have call successors, (16) [2024-11-04 15:07:27,679 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 111 transitions. [2024-11-04 15:07:27,679 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 111 transitions. Word has length 98 [2024-11-04 15:07:27,680 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:27,680 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 111 transitions. [2024-11-04 15:07:27,680 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 12.75) internal successors, (51), 4 states have internal predecessors, (51), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-04 15:07:27,680 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 111 transitions. [2024-11-04 15:07:27,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-04 15:07:27,681 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:27,681 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-04 15:07:27,703 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2024-11-04 15:07:27,882 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:07:27,882 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:27,882 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:27,882 INFO L85 PathProgramCache]: Analyzing trace with hash 1924312770, now seen corresponding path program 1 times [2024-11-04 15:07:27,883 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:27,883 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2057927352] [2024-11-04 15:07:27,883 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:27,883 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:27,883 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:27,884 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:07:27,885 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:07:28,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:28,036 INFO L255 TraceCheckSpWp]: Trace formula consists of 269 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:07:28,038 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:28,053 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 24 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-04 15:07:28,053 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:28,094 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2024-11-04 15:07:28,094 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:28,095 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2057927352] [2024-11-04 15:07:28,095 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2057927352] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:07:28,095 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:07:28,095 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:07:28,095 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [843540109] [2024-11-04 15:07:28,095 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:28,096 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:07:28,096 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:28,096 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:07:28,096 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:28,097 INFO L87 Difference]: Start difference. First operand 86 states and 111 transitions. Second operand has 4 states, 4 states have (on average 13.5) internal successors, (54), 4 states have internal predecessors, (54), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-04 15:07:28,123 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:28,123 INFO L93 Difference]: Finished difference Result 158 states and 213 transitions. [2024-11-04 15:07:28,125 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:07:28,125 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 13.5) internal successors, (54), 4 states have internal predecessors, (54), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 98 [2024-11-04 15:07:28,125 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:28,126 INFO L225 Difference]: With dead ends: 158 [2024-11-04 15:07:28,126 INFO L226 Difference]: Without dead ends: 86 [2024-11-04 15:07:28,127 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 194 GetRequests, 192 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:07:28,127 INFO L432 NwaCegarLoop]: 81 mSDtfsCounter, 0 mSDsluCounter, 151 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 232 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:28,128 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 232 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:28,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-04 15:07:28,134 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 83. [2024-11-04 15:07:28,134 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 61 states have (on average 1.2459016393442623) internal successors, (76), 63 states have internal predecessors, (76), 14 states have call successors, (14), 6 states have call predecessors, (14), 7 states have return successors, (16), 13 states have call predecessors, (16), 13 states have call successors, (16) [2024-11-04 15:07:28,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 106 transitions. [2024-11-04 15:07:28,135 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 106 transitions. Word has length 98 [2024-11-04 15:07:28,136 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:28,136 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 106 transitions. [2024-11-04 15:07:28,136 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 13.5) internal successors, (54), 4 states have internal predecessors, (54), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-04 15:07:28,136 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 106 transitions. [2024-11-04 15:07:28,137 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-04 15:07:28,137 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:28,137 INFO L215 NwaCegarLoop]: trace histogram [4, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:07:28,158 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-04 15:07:28,337 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:07:28,338 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:28,338 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:28,338 INFO L85 PathProgramCache]: Analyzing trace with hash -1438193982, now seen corresponding path program 1 times [2024-11-04 15:07:28,339 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:28,339 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [876528733] [2024-11-04 15:07:28,339 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:28,339 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:28,339 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:28,341 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:07:28,343 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:07:28,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:28,519 INFO L255 TraceCheckSpWp]: Trace formula consists of 285 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:07:28,521 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:28,551 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:07:28,551 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:28,604 INFO L134 CoverageAnalysis]: Checked inductivity of 69 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 15:07:28,605 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:28,605 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [876528733] [2024-11-04 15:07:28,605 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [876528733] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:07:28,605 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:07:28,605 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6, 6] imperfect sequences [] total 8 [2024-11-04 15:07:28,605 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1023040679] [2024-11-04 15:07:28,605 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:28,605 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:07:28,606 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:28,606 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:07:28,606 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:07:28,606 INFO L87 Difference]: Start difference. First operand 83 states and 106 transitions. Second operand has 8 states, 7 states have (on average 6.285714285714286) internal successors, (44), 5 states have internal predecessors, (44), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) [2024-11-04 15:07:28,639 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:28,639 INFO L93 Difference]: Finished difference Result 93 states and 117 transitions. [2024-11-04 15:07:28,639 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:07:28,639 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 6.285714285714286) internal successors, (44), 5 states have internal predecessors, (44), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) Word has length 100 [2024-11-04 15:07:28,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:28,641 INFO L225 Difference]: With dead ends: 93 [2024-11-04 15:07:28,641 INFO L226 Difference]: Without dead ends: 91 [2024-11-04 15:07:28,642 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 192 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:07:28,642 INFO L432 NwaCegarLoop]: 78 mSDtfsCounter, 6 mSDsluCounter, 381 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 459 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:28,642 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 459 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 15:07:28,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-11-04 15:07:28,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 90. [2024-11-04 15:07:28,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 65 states have (on average 1.2307692307692308) internal successors, (80), 68 states have internal predecessors, (80), 15 states have call successors, (15), 7 states have call predecessors, (15), 9 states have return successors, (19), 14 states have call predecessors, (19), 14 states have call successors, (19) [2024-11-04 15:07:28,652 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 114 transitions. [2024-11-04 15:07:28,653 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 114 transitions. Word has length 100 [2024-11-04 15:07:28,653 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:28,653 INFO L471 AbstractCegarLoop]: Abstraction has 90 states and 114 transitions. [2024-11-04 15:07:28,655 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 6.285714285714286) internal successors, (44), 5 states have internal predecessors, (44), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) [2024-11-04 15:07:28,655 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 114 transitions. [2024-11-04 15:07:28,657 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:07:28,657 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:28,657 INFO L215 NwaCegarLoop]: trace histogram [4, 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] [2024-11-04 15:07:28,678 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Ended with exit code 0 [2024-11-04 15:07:28,857 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:07:28,858 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:28,858 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:28,858 INFO L85 PathProgramCache]: Analyzing trace with hash 166988707, now seen corresponding path program 1 times [2024-11-04 15:07:28,858 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:28,858 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1509044886] [2024-11-04 15:07:28,858 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:28,859 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:28,859 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:28,860 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:07:28,860 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:07:29,038 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:29,042 INFO L255 TraceCheckSpWp]: Trace formula consists of 293 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-04 15:07:29,046 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:29,082 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:07:29,086 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:07:30,501 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 35 proven. 25 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-04 15:07:30,502 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:31,265 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 12 proven. 33 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-04 15:07:31,265 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:31,265 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1509044886] [2024-11-04 15:07:31,266 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1509044886] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:07:31,266 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:07:31,266 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 21 [2024-11-04 15:07:31,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1476163895] [2024-11-04 15:07:31,266 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:07:31,267 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-04 15:07:31,267 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:31,268 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-04 15:07:31,268 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2024-11-04 15:07:31,268 INFO L87 Difference]: Start difference. First operand 90 states and 114 transitions. Second operand has 21 states, 21 states have (on average 6.285714285714286) internal successors, (132), 19 states have internal predecessors, (132), 10 states have call successors, (21), 4 states have call predecessors, (21), 7 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-04 15:07:35,736 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:07:39,972 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:07:44,044 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:07:48,080 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:07:50,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:07:50,884 INFO L93 Difference]: Finished difference Result 210 states and 261 transitions. [2024-11-04 15:07:50,884 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 15:07:50,885 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 6.285714285714286) internal successors, (132), 19 states have internal predecessors, (132), 10 states have call successors, (21), 4 states have call predecessors, (21), 7 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) Word has length 106 [2024-11-04 15:07:50,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:07:50,887 INFO L225 Difference]: With dead ends: 210 [2024-11-04 15:07:50,887 INFO L226 Difference]: Without dead ends: 133 [2024-11-04 15:07:50,887 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 221 GetRequests, 187 SyntacticMatches, 7 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 200 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=146, Invalid=666, Unknown=0, NotChecked=0, Total=812 [2024-11-04 15:07:50,888 INFO L432 NwaCegarLoop]: 85 mSDtfsCounter, 91 mSDsluCounter, 715 mSDsCounter, 0 mSdLazyCounter, 464 mSolverCounterSat, 31 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 800 SdHoareTripleChecker+Invalid, 499 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 464 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 19.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:07:50,890 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 800 Invalid, 499 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 464 Invalid, 4 Unknown, 0 Unchecked, 19.0s Time] [2024-11-04 15:07:50,891 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2024-11-04 15:07:50,906 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 131. [2024-11-04 15:07:50,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 100 states have (on average 1.21) internal successors, (121), 103 states have internal predecessors, (121), 17 states have call successors, (17), 11 states have call predecessors, (17), 13 states have return successors, (22), 16 states have call predecessors, (22), 16 states have call successors, (22) [2024-11-04 15:07:50,908 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 160 transitions. [2024-11-04 15:07:50,909 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 160 transitions. Word has length 106 [2024-11-04 15:07:50,911 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:07:50,911 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 160 transitions. [2024-11-04 15:07:50,911 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 6.285714285714286) internal successors, (132), 19 states have internal predecessors, (132), 10 states have call successors, (21), 4 states have call predecessors, (21), 7 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-04 15:07:50,911 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 160 transitions. [2024-11-04 15:07:50,912 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:07:50,912 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:07:50,912 INFO L215 NwaCegarLoop]: trace histogram [4, 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, 1, 1] [2024-11-04 15:07:50,930 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Ended with exit code 0 [2024-11-04 15:07:51,116 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:07:51,116 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:07:51,117 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:07:51,117 INFO L85 PathProgramCache]: Analyzing trace with hash -844128543, now seen corresponding path program 1 times [2024-11-04 15:07:51,117 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:07:51,117 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1848571239] [2024-11-04 15:07:51,117 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:07:51,117 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:07:51,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:07:51,118 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:07:51,119 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:07:51,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:07:51,290 INFO L255 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-04 15:07:51,293 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:07:51,475 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 11 treesize of output 7 [2024-11-04 15:07:51,498 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-04 15:07:51,499 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 1 [2024-11-04 15:07:53,467 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 28 proven. 0 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-04 15:07:53,467 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:07:56,992 INFO L349 Elim1Store]: treesize reduction 19, result has 62.0 percent of original size [2024-11-04 15:07:56,992 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 198 treesize of output 185 [2024-11-04 15:07:57,037 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 15:07:57,037 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 95 treesize of output 97 [2024-11-04 15:07:57,059 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 68 treesize of output 64 [2024-11-04 15:07:57,304 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2024-11-04 15:07:57,321 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 18 [2024-11-04 15:07:57,583 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 22 proven. 0 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2024-11-04 15:07:57,583 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:07:57,583 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1848571239] [2024-11-04 15:07:57,583 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1848571239] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:07:57,583 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:07:57,584 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11, 10] imperfect sequences [] total 19 [2024-11-04 15:07:57,584 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515140906] [2024-11-04 15:07:57,584 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:07:57,585 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-04 15:07:57,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:07:57,585 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-04 15:07:57,586 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=283, Unknown=0, NotChecked=0, Total=342 [2024-11-04 15:07:57,586 INFO L87 Difference]: Start difference. First operand 131 states and 160 transitions. Second operand has 19 states, 19 states have (on average 5.2631578947368425) internal successors, (100), 19 states have internal predecessors, (100), 9 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2024-11-04 15:08:00,080 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:00,080 INFO L93 Difference]: Finished difference Result 319 states and 393 transitions. [2024-11-04 15:08:00,081 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-04 15:08:00,081 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 5.2631578947368425) internal successors, (100), 19 states have internal predecessors, (100), 9 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) Word has length 106 [2024-11-04 15:08:00,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:00,083 INFO L225 Difference]: With dead ends: 319 [2024-11-04 15:08:00,083 INFO L226 Difference]: Without dead ends: 248 [2024-11-04 15:08:00,083 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 186 SyntacticMatches, 8 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=120, Invalid=582, Unknown=0, NotChecked=0, Total=702 [2024-11-04 15:08:00,084 INFO L432 NwaCegarLoop]: 61 mSDtfsCounter, 68 mSDsluCounter, 482 mSDsCounter, 0 mSdLazyCounter, 337 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 543 SdHoareTripleChecker+Invalid, 370 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 337 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:00,086 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 543 Invalid, 370 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 337 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-11-04 15:08:00,087 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2024-11-04 15:08:00,104 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 131. [2024-11-04 15:08:00,104 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 100 states have (on average 1.2) internal successors, (120), 103 states have internal predecessors, (120), 17 states have call successors, (17), 11 states have call predecessors, (17), 13 states have return successors, (22), 16 states have call predecessors, (22), 16 states have call successors, (22) [2024-11-04 15:08:00,105 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 159 transitions. [2024-11-04 15:08:00,106 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 159 transitions. Word has length 106 [2024-11-04 15:08:00,106 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:00,106 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 159 transitions. [2024-11-04 15:08:00,106 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 5.2631578947368425) internal successors, (100), 19 states have internal predecessors, (100), 9 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (18), 9 states have call predecessors, (18), 9 states have call successors, (18) [2024-11-04 15:08:00,106 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 159 transitions. [2024-11-04 15:08:00,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:08:00,107 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:00,108 INFO L215 NwaCegarLoop]: trace histogram [4, 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] [2024-11-04 15:08:00,129 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:08:00,308 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:00,308 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:00,309 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:00,309 INFO L85 PathProgramCache]: Analyzing trace with hash -1865196897, now seen corresponding path program 1 times [2024-11-04 15:08:00,309 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:00,309 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1096659966] [2024-11-04 15:08:00,309 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:00,309 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:00,309 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:00,310 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:08:00,311 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-04 15:08:00,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:00,493 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-04 15:08:00,496 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:00,576 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-04 15:08:00,582 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-04 15:08:03,322 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-04 15:08:03,323 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:08:04,535 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 12 proven. 33 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-04 15:08:04,535 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:08:04,535 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1096659966] [2024-11-04 15:08:04,535 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1096659966] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:08:04,535 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:08:04,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12] total 25 [2024-11-04 15:08:04,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1081601556] [2024-11-04 15:08:04,536 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:08:04,536 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-04 15:08:04,536 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:08:04,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-04 15:08:04,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=508, Unknown=0, NotChecked=0, Total=600 [2024-11-04 15:08:04,537 INFO L87 Difference]: Start difference. First operand 131 states and 159 transitions. Second operand has 25 states, 25 states have (on average 5.16) internal successors, (129), 23 states have internal predecessors, (129), 10 states have call successors, (21), 4 states have call predecessors, (21), 7 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-04 15:08:08,597 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:12,720 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:16,903 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:19,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:19,850 INFO L93 Difference]: Finished difference Result 196 states and 239 transitions. [2024-11-04 15:08:19,850 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 15:08:19,851 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 5.16) internal successors, (129), 23 states have internal predecessors, (129), 10 states have call successors, (21), 4 states have call predecessors, (21), 7 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) Word has length 106 [2024-11-04 15:08:19,851 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:19,852 INFO L225 Difference]: With dead ends: 196 [2024-11-04 15:08:19,852 INFO L226 Difference]: Without dead ends: 131 [2024-11-04 15:08:19,852 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 182 SyntacticMatches, 7 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 250 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=183, Invalid=873, Unknown=0, NotChecked=0, Total=1056 [2024-11-04 15:08:19,853 INFO L432 NwaCegarLoop]: 79 mSDtfsCounter, 76 mSDsluCounter, 775 mSDsCounter, 0 mSdLazyCounter, 561 mSolverCounterSat, 23 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 14.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 854 SdHoareTripleChecker+Invalid, 587 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 561 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 14.6s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:19,853 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 854 Invalid, 587 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 561 Invalid, 3 Unknown, 0 Unchecked, 14.6s Time] [2024-11-04 15:08:19,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2024-11-04 15:08:19,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 131. [2024-11-04 15:08:19,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 100 states have (on average 1.19) internal successors, (119), 103 states have internal predecessors, (119), 17 states have call successors, (17), 11 states have call predecessors, (17), 13 states have return successors, (22), 16 states have call predecessors, (22), 16 states have call successors, (22) [2024-11-04 15:08:19,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 158 transitions. [2024-11-04 15:08:19,873 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 158 transitions. Word has length 106 [2024-11-04 15:08:19,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:19,873 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 158 transitions. [2024-11-04 15:08:19,874 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 5.16) internal successors, (129), 23 states have internal predecessors, (129), 10 states have call successors, (21), 4 states have call predecessors, (21), 7 states have return successors, (20), 9 states have call predecessors, (20), 10 states have call successors, (20) [2024-11-04 15:08:19,874 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 158 transitions. [2024-11-04 15:08:19,874 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:08:19,874 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:19,875 INFO L215 NwaCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:08:19,894 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:08:20,075 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:08:20,076 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:20,076 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:20,076 INFO L85 PathProgramCache]: Analyzing trace with hash 435625693, now seen corresponding path program 1 times [2024-11-04 15:08:20,076 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:20,076 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1894488987] [2024-11-04 15:08:20,076 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:20,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:20,076 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:20,078 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:08:20,082 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:08:20,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:20,271 INFO L255 TraceCheckSpWp]: Trace formula consists of 284 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-04 15:08:20,275 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:20,370 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-04 15:08:22,928 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 28 proven. 34 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-04 15:08:22,929 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:08:25,528 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 122 treesize of output 114 [2024-11-04 15:08:25,577 INFO L134 CoverageAnalysis]: Checked inductivity of 71 backedges. 12 proven. 35 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2024-11-04 15:08:25,577 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:08:25,577 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1894488987] [2024-11-04 15:08:25,577 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1894488987] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:08:25,577 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:08:25,577 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 28 [2024-11-04 15:08:25,577 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1018940261] [2024-11-04 15:08:25,577 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:08:25,578 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-04 15:08:25,578 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:08:25,579 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-04 15:08:25,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=662, Unknown=0, NotChecked=0, Total=756 [2024-11-04 15:08:25,579 INFO L87 Difference]: Start difference. First operand 131 states and 158 transitions. Second operand has 28 states, 28 states have (on average 4.857142857142857) internal successors, (136), 26 states have internal predecessors, (136), 12 states have call successors, (21), 3 states have call predecessors, (21), 7 states have return successors, (20), 11 states have call predecessors, (20), 12 states have call successors, (20) [2024-11-04 15:08:29,638 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 15:08:36,351 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:36,351 INFO L93 Difference]: Finished difference Result 344 states and 431 transitions. [2024-11-04 15:08:36,351 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-04 15:08:36,352 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 4.857142857142857) internal successors, (136), 26 states have internal predecessors, (136), 12 states have call successors, (21), 3 states have call predecessors, (21), 7 states have return successors, (20), 11 states have call predecessors, (20), 12 states have call successors, (20) Word has length 106 [2024-11-04 15:08:36,352 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:36,353 INFO L225 Difference]: With dead ends: 344 [2024-11-04 15:08:36,353 INFO L226 Difference]: Without dead ends: 233 [2024-11-04 15:08:36,354 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 188 SyntacticMatches, 7 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 382 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=350, Invalid=1720, Unknown=0, NotChecked=0, Total=2070 [2024-11-04 15:08:36,355 INFO L432 NwaCegarLoop]: 101 mSDtfsCounter, 251 mSDsluCounter, 1039 mSDsCounter, 0 mSdLazyCounter, 948 mSolverCounterSat, 58 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 267 SdHoareTripleChecker+Valid, 1140 SdHoareTripleChecker+Invalid, 1007 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 948 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:36,355 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [267 Valid, 1140 Invalid, 1007 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 948 Invalid, 1 Unknown, 0 Unchecked, 9.0s Time] [2024-11-04 15:08:36,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2024-11-04 15:08:36,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 203. [2024-11-04 15:08:36,381 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 153 states have (on average 1.196078431372549) internal successors, (183), 159 states have internal predecessors, (183), 28 states have call successors, (28), 16 states have call predecessors, (28), 21 states have return successors, (39), 27 states have call predecessors, (39), 26 states have call successors, (39) [2024-11-04 15:08:36,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 250 transitions. [2024-11-04 15:08:36,382 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 250 transitions. Word has length 106 [2024-11-04 15:08:36,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:36,383 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 250 transitions. [2024-11-04 15:08:36,383 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 28 states have (on average 4.857142857142857) internal successors, (136), 26 states have internal predecessors, (136), 12 states have call successors, (21), 3 states have call predecessors, (21), 7 states have return successors, (20), 11 states have call predecessors, (20), 12 states have call successors, (20) [2024-11-04 15:08:36,383 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 250 transitions. [2024-11-04 15:08:36,384 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2024-11-04 15:08:36,384 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:36,384 INFO L215 NwaCegarLoop]: trace histogram [5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:08:36,405 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:08:36,588 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:08:36,588 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:36,588 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:36,589 INFO L85 PathProgramCache]: Analyzing trace with hash -2065682137, now seen corresponding path program 1 times [2024-11-04 15:08:36,589 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:36,589 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1298981282] [2024-11-04 15:08:36,589 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:36,589 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:36,589 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:36,590 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:08:36,591 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:08:36,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:08:36,793 INFO L255 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:08:36,795 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:08:36,895 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-11-04 15:08:36,896 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:08:37,013 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2024-11-04 15:08:37,013 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:08:37,013 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1298981282] [2024-11-04 15:08:37,013 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1298981282] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:08:37,013 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:08:37,014 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7, 7] imperfect sequences [] total 9 [2024-11-04 15:08:37,014 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1276681222] [2024-11-04 15:08:37,014 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:08:37,014 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-04 15:08:37,014 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:08:37,015 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-04 15:08:37,015 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:08:37,015 INFO L87 Difference]: Start difference. First operand 203 states and 250 transitions. Second operand has 9 states, 8 states have (on average 5.625) internal successors, (45), 6 states have internal predecessors, (45), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) [2024-11-04 15:08:37,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:08:37,145 INFO L93 Difference]: Finished difference Result 217 states and 265 transitions. [2024-11-04 15:08:37,145 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:08:37,145 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 5.625) internal successors, (45), 6 states have internal predecessors, (45), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) Word has length 113 [2024-11-04 15:08:37,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:08:37,147 INFO L225 Difference]: With dead ends: 217 [2024-11-04 15:08:37,147 INFO L226 Difference]: Without dead ends: 215 [2024-11-04 15:08:37,147 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 217 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:08:37,148 INFO L432 NwaCegarLoop]: 79 mSDtfsCounter, 3 mSDsluCounter, 536 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 615 SdHoareTripleChecker+Invalid, 46 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:08:37,148 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [4 Valid, 615 Invalid, 46 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 15:08:37,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2024-11-04 15:08:37,180 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 206. [2024-11-04 15:08:37,180 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 206 states, 155 states have (on average 1.1935483870967742) internal successors, (185), 160 states have internal predecessors, (185), 29 states have call successors, (29), 17 states have call predecessors, (29), 21 states have return successors, (38), 28 states have call predecessors, (38), 27 states have call successors, (38) [2024-11-04 15:08:37,181 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 206 states to 206 states and 252 transitions. [2024-11-04 15:08:37,182 INFO L78 Accepts]: Start accepts. Automaton has 206 states and 252 transitions. Word has length 113 [2024-11-04 15:08:37,182 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:08:37,182 INFO L471 AbstractCegarLoop]: Abstraction has 206 states and 252 transitions. [2024-11-04 15:08:37,182 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 5.625) internal successors, (45), 6 states have internal predecessors, (45), 2 states have call successors, (10), 3 states have call predecessors, (10), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) [2024-11-04 15:08:37,183 INFO L276 IsEmpty]: Start isEmpty. Operand 206 states and 252 transitions. [2024-11-04 15:08:37,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 15:08:37,183 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:08:37,184 INFO L215 NwaCegarLoop]: trace histogram [6, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:08:37,202 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2024-11-04 15:08:37,384 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:08:37,384 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:08:37,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:08:37,385 INFO L85 PathProgramCache]: Analyzing trace with hash 1112769404, now seen corresponding path program 1 times [2024-11-04 15:08:37,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:08:37,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1045496647] [2024-11-04 15:08:37,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:08:37,385 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:08:37,386 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:08:37,387 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:08:37,389 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:08:37,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-04 15:08:37,682 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-04 15:08:37,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-04 15:08:37,892 INFO L130 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found a feasible trace [2024-11-04 15:08:37,892 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-04 15:08:37,893 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-04 15:08:37,917 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:08:38,095 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:08:38,098 INFO L407 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 15:08:38,174 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-04 15:08:38,178 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 04.11 03:08:38 BoogieIcfgContainer [2024-11-04 15:08:38,178 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-04 15:08:38,179 INFO L158 Benchmark]: Toolchain (without parser) took 87435.31ms. Allocated memory was 324.0MB in the beginning and 401.6MB in the end (delta: 77.6MB). Free memory was 269.7MB in the beginning and 171.8MB in the end (delta: 97.9MB). Peak memory consumption was 177.0MB. Max. memory is 8.0GB. [2024-11-04 15:08:38,182 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 200.3MB. Free memory is still 152.7MB. There was no memory consumed. Max. memory is 8.0GB. [2024-11-04 15:08:38,182 INFO L158 Benchmark]: CACSL2BoogieTranslator took 2187.87ms. Allocated memory is still 324.0MB. Free memory was 269.3MB in the beginning and 147.0MB in the end (delta: 122.4MB). Peak memory consumption was 123.2MB. Max. memory is 8.0GB. [2024-11-04 15:08:38,182 INFO L158 Benchmark]: Boogie Procedure Inliner took 114.74ms. Allocated memory is still 324.0MB. Free memory was 147.0MB in the beginning and 140.7MB in the end (delta: 6.3MB). Peak memory consumption was 6.3MB. Max. memory is 8.0GB. [2024-11-04 15:08:38,182 INFO L158 Benchmark]: Boogie Preprocessor took 98.43ms. Allocated memory is still 324.0MB. Free memory was 140.7MB in the beginning and 135.5MB in the end (delta: 5.2MB). Peak memory consumption was 5.2MB. Max. memory is 8.0GB. [2024-11-04 15:08:38,182 INFO L158 Benchmark]: RCFGBuilder took 699.68ms. Allocated memory is still 324.0MB. Free memory was 135.5MB in the beginning and 286.7MB in the end (delta: -151.2MB). Peak memory consumption was 34.6MB. Max. memory is 8.0GB. [2024-11-04 15:08:38,183 INFO L158 Benchmark]: TraceAbstraction took 84328.13ms. Allocated memory was 324.0MB in the beginning and 401.6MB in the end (delta: 77.6MB). Free memory was 285.9MB in the beginning and 171.8MB in the end (delta: 114.1MB). Peak memory consumption was 191.7MB. Max. memory is 8.0GB. [2024-11-04 15:08:38,184 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.13ms. Allocated memory is still 200.3MB. Free memory is still 152.7MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 2187.87ms. Allocated memory is still 324.0MB. Free memory was 269.3MB in the beginning and 147.0MB in the end (delta: 122.4MB). Peak memory consumption was 123.2MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 114.74ms. Allocated memory is still 324.0MB. Free memory was 147.0MB in the beginning and 140.7MB in the end (delta: 6.3MB). Peak memory consumption was 6.3MB. Max. memory is 8.0GB. * Boogie Preprocessor took 98.43ms. Allocated memory is still 324.0MB. Free memory was 140.7MB in the beginning and 135.5MB in the end (delta: 5.2MB). Peak memory consumption was 5.2MB. Max. memory is 8.0GB. * RCFGBuilder took 699.68ms. Allocated memory is still 324.0MB. Free memory was 135.5MB in the beginning and 286.7MB in the end (delta: -151.2MB). Peak memory consumption was 34.6MB. Max. memory is 8.0GB. * TraceAbstraction took 84328.13ms. Allocated memory was 324.0MB in the beginning and 401.6MB in the end (delta: 77.6MB). Free memory was 285.9MB in the beginning and 171.8MB in the end (delta: 114.1MB). Peak memory consumption was 191.7MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - CounterExampleResult [Line: 223]: a call to reach_error is reachable a call to reach_error is reachable We found a FailurePath: [L6901-L6906] static struct aws_allocator s_can_fail_allocator_static = { .mem_acquire = s_can_fail_malloc_allocator, .mem_release = s_can_fail_free_allocator, .mem_realloc = s_can_fail_realloc_allocator, .mem_calloc = s_can_fail_calloc_allocator, }; [L6901-L6906] static struct aws_allocator s_can_fail_allocator_static = { .mem_acquire = s_can_fail_malloc_allocator, .mem_release = s_can_fail_free_allocator, .mem_realloc = s_can_fail_realloc_allocator, .mem_calloc = s_can_fail_calloc_allocator, }; [L6901-L6906] static struct aws_allocator s_can_fail_allocator_static = { .mem_acquire = s_can_fail_malloc_allocator, .mem_release = s_can_fail_free_allocator, .mem_realloc = s_can_fail_realloc_allocator, .mem_calloc = s_can_fail_calloc_allocator, }; [L6901-L6906] static struct aws_allocator s_can_fail_allocator_static = { .mem_acquire = s_can_fail_malloc_allocator, .mem_release = s_can_fail_free_allocator, .mem_realloc = s_can_fail_realloc_allocator, .mem_calloc = s_can_fail_calloc_allocator, }; [L6901-L6906] static struct aws_allocator s_can_fail_allocator_static = { .mem_acquire = s_can_fail_malloc_allocator, .mem_release = s_can_fail_free_allocator, .mem_realloc = s_can_fail_realloc_allocator, .mem_calloc = s_can_fail_calloc_allocator, }; [L6901-L6906] static struct aws_allocator s_can_fail_allocator_static = { .mem_acquire = s_can_fail_malloc_allocator, .mem_release = s_can_fail_free_allocator, .mem_realloc = s_can_fail_realloc_allocator, .mem_calloc = s_can_fail_calloc_allocator, }; [L7326] static __thread int tl_last_error = 0; VAL [s_can_fail_allocator_static={4:0}, tl_last_error=0] [L7360] CALL aws_linked_list_end_harness() [L7344] struct aws_linked_list list; [L7346] CALL ensure_linked_list_is_allocated(&list, 20) [L6743] CALL, EXPR nondet_uint64_t() VAL [s_can_fail_allocator_static={4:0}, tl_last_error=0] [L266] return __VERIFIER_nondet_ulong(); [L6743] RET, EXPR nondet_uint64_t() VAL [list={5:0}, max_length=20, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L6743] size_t length = nondet_uint64_t(); [L6744] CALL assume_abort_if_not(length <= max_length) VAL [\old(cond)=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L211] COND FALSE !(!cond) VAL [\old(cond)=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L6744] RET assume_abort_if_not(length <= max_length) VAL [length=0, list={5:0}, max_length=20, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L6746-L6747] list->head.prev = ((void *)0) [L6749-L6750] list->tail.next = ((void *)0) [L6753] struct aws_linked_list_node *curr = &list->head; [L6755] size_t i = 0; VAL [curr={5:0}, i=0, length=0, list={5:0}, max_length=20, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L6755] COND FALSE !(i < length) VAL [curr={5:0}, list={5:0}, max_length=20, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L6764] curr->next = &list->tail [L6765] list->tail.prev = curr VAL [s_can_fail_allocator_static={4:0}, tl_last_error=0] [L7346] RET ensure_linked_list_is_allocated(&list, 20) [L7349] CALL, EXPR aws_linked_list_is_valid(&list) VAL [s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694] EXPR list && list->head.next VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694] EXPR list && list->head.next [L4694] EXPR list->head.next [L4694] EXPR list && list->head.next VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) [L4694] EXPR list->head.prev [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev [L4696] EXPR list->tail.prev [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) [L4696] EXPR list->tail.next [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] COND TRUE list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) [L4700] CALL, EXPR aws_linked_list_is_valid_deep(list) [L4734] COND FALSE !(!list) [L4740] const struct aws_linked_list_node *temp = &list->head; [L4743-L4746] _Bool head_reaches_tail = 0 ; VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4750] COND TRUE \read(*temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4751] COND FALSE !(temp == &list->tail) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4756] CALL, EXPR aws_linked_list_node_next_is_valid(temp) VAL [\old(node)={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next [L4718] EXPR node->next [L4718] EXPR node && node->next VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next && node->next->prev == node VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next && node->next->prev == node [L4718] EXPR node->next [L4718] EXPR node->next->prev [L4718] EXPR node && node->next && node->next->prev == node VAL [\old(node)={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] return node && node->next && node->next->prev == node; [L4756] RET, EXPR aws_linked_list_node_next_is_valid(temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4756] COND FALSE !(!aws_linked_list_node_next_is_valid(temp)) [L4762] EXPR temp->next [L4762] temp = temp->next [L4750] COND TRUE \read(*temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:16}, tl_last_error=0] [L4751] COND TRUE temp == &list->tail [L4752-L4753] head_reaches_tail = 1 VAL [head_reaches_tail=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4764] return head_reaches_tail; VAL [\result=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4700] RET, EXPR aws_linked_list_is_valid_deep(list) [L4700] return aws_linked_list_is_valid_deep(list); [L7349] RET, EXPR aws_linked_list_is_valid(&list) VAL [list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L7349] CALL assume_abort_if_not(aws_linked_list_is_valid(&list)) VAL [\old(cond)=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L211] COND FALSE !(!cond) VAL [\old(cond)=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L7349] RET assume_abort_if_not(aws_linked_list_is_valid(&list)) VAL [list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L7354] CALL aws_linked_list_end(&list) [L4799] CALL, EXPR aws_linked_list_is_valid(list) VAL [s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694] EXPR list && list->head.next VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694] EXPR list && list->head.next [L4694] EXPR list->head.next [L4694] EXPR list && list->head.next VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) [L4694] EXPR list->head.prev [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev [L4696] EXPR list->tail.prev [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) [L4696] EXPR list->tail.next [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] COND TRUE list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) [L4700] CALL, EXPR aws_linked_list_is_valid_deep(list) [L4734] COND FALSE !(!list) [L4740] const struct aws_linked_list_node *temp = &list->head; [L4743-L4746] _Bool head_reaches_tail = 0 ; VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4750] COND TRUE \read(*temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4751] COND FALSE !(temp == &list->tail) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4756] CALL, EXPR aws_linked_list_node_next_is_valid(temp) VAL [\old(node)={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next [L4718] EXPR node->next [L4718] EXPR node && node->next VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next && node->next->prev == node VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next && node->next->prev == node [L4718] EXPR node->next [L4718] EXPR node->next->prev [L4718] EXPR node && node->next && node->next->prev == node VAL [\old(node)={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] return node && node->next && node->next->prev == node; [L4756] RET, EXPR aws_linked_list_node_next_is_valid(temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4756] COND FALSE !(!aws_linked_list_node_next_is_valid(temp)) [L4762] EXPR temp->next [L4762] temp = temp->next [L4750] COND TRUE \read(*temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:16}, tl_last_error=0] [L4751] COND TRUE temp == &list->tail [L4752-L4753] head_reaches_tail = 1 VAL [head_reaches_tail=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4764] return head_reaches_tail; VAL [\result=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4700] RET, EXPR aws_linked_list_is_valid_deep(list) [L4700] return aws_linked_list_is_valid_deep(list); [L4799] RET, EXPR aws_linked_list_is_valid(list) VAL [list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4799] CALL assume_abort_if_not((aws_linked_list_is_valid(list))) VAL [\old(cond)=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L211] COND FALSE !(!cond) VAL [\old(cond)=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4799] RET assume_abort_if_not((aws_linked_list_is_valid(list))) VAL [list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4800] const struct aws_linked_list_node *rval = &list->tail; VAL [list={5:0}, rval={5:16}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4801] CALL, EXPR aws_linked_list_is_valid(list) VAL [s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694] EXPR list && list->head.next VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694] EXPR list && list->head.next [L4694] EXPR list->head.next [L4694] EXPR list && list->head.next VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) [L4694] EXPR list->head.prev [L4694-L4695] EXPR list && list->head.next && list->head.prev == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev [L4696] EXPR list->tail.prev [L4694-L4696] EXPR list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) [L4696] EXPR list->tail.next [L4694-L4697] list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) VAL [\old(list)={5:0}, list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4694-L4697] COND TRUE list && list->head.next && list->head.prev == ((void *)0) && list->tail.prev && list->tail.next == ((void *)0) [L4700] CALL, EXPR aws_linked_list_is_valid_deep(list) [L4734] COND FALSE !(!list) [L4740] const struct aws_linked_list_node *temp = &list->head; [L4743-L4746] _Bool head_reaches_tail = 0 ; VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4750] COND TRUE \read(*temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4751] COND FALSE !(temp == &list->tail) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4756] CALL, EXPR aws_linked_list_node_next_is_valid(temp) VAL [\old(node)={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next [L4718] EXPR node->next [L4718] EXPR node && node->next VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next && node->next->prev == node VAL [\old(node)={5:0}, node={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] EXPR node && node->next && node->next->prev == node [L4718] EXPR node->next [L4718] EXPR node->next->prev [L4718] EXPR node && node->next && node->next->prev == node VAL [\old(node)={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4718] return node && node->next && node->next->prev == node; [L4756] RET, EXPR aws_linked_list_node_next_is_valid(temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:0}, tl_last_error=0] [L4756] COND FALSE !(!aws_linked_list_node_next_is_valid(temp)) [L4762] EXPR temp->next [L4762] temp = temp->next [L4750] COND TRUE \read(*temp) VAL [head_reaches_tail=0, list={5:0}, s_can_fail_allocator_static={4:0}, temp={5:16}, tl_last_error=0] [L4751] COND TRUE temp == &list->tail [L4752-L4753] head_reaches_tail = 1 VAL [head_reaches_tail=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4764] return head_reaches_tail; VAL [\result=1, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4700] RET, EXPR aws_linked_list_is_valid_deep(list) [L4700] return aws_linked_list_is_valid_deep(list); [L4801] RET, EXPR aws_linked_list_is_valid(list) VAL [list={5:0}, rval={5:16}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4801] CALL __VERIFIER_assert(!((aws_linked_list_is_valid(list)))) VAL [\old(cond)=0, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L223] COND TRUE !cond VAL [\old(cond)=0, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L223] reach_error() VAL [\old(cond)=0, s_can_fail_allocator_static={4:0}, tl_last_error=0] - StatisticsResult: Ultimate Automizer benchmark data CFG has 6 procedures, 68 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 84.2s, OverallIterations: 20, TraceHistogramMax: 6, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 50.5s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 9 mSolverCounterUnknown, 736 SdHoareTripleChecker+Valid, 46.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 665 mSDsluCounter, 8889 SdHoareTripleChecker+Invalid, 45.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 268 IncrementalHoareTripleChecker+Unchecked, 7414 mSDsCounter, 197 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 3327 IncrementalHoareTripleChecker+Invalid, 3801 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 197 mSolverCounterUnsat, 1475 mSDtfsCounter, 3327 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 3480 GetRequests, 3224 SyntacticMatches, 30 SemanticMatches, 226 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 1075 ImplicationChecksByTransitivity, 16.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=206occurred in iteration=19, InterpolantAutomatonStates: 178, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 19 MinimizatonAttempts, 212 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.5s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 25.2s InterpolantComputationTime, 1837 NumberOfCodeBlocks, 1837 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 3404 ConstructedInterpolants, 254 QuantifiedInterpolants, 12524 SizeOfPredicates, 37 NumberOfNonLiveVariables, 4936 ConjunctsInSsa, 194 ConjunctsInUnsatCore, 38 InterpolantComputations, 18 PerfectInterpolantSequences, 1905/2254 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate proved your program to be incorrect! [2024-11-04 15:08:38,264 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...