/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_rend_harness_negated.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 15:09:44,161 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 15:09:44,216 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf [2024-11-04 15:09:44,221 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 15:09:44,221 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 15:09:44,243 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 15:09:44,243 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 15:09:44,243 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 15:09:44,244 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 15:09:44,244 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 15:09:44,244 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 15:09:44,244 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 15:09:44,245 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 15:09:44,246 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 15:09:44,246 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 15:09:44,246 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 15:09:44,247 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 15:09:44,249 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 15:09:44,249 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 15:09:44,249 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 15:09:44,249 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 15:09:44,249 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 15:09:44,250 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 15:09:44,250 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 15:09:44,250 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 15:09:44,250 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 15:09:44,250 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 15:09:44,250 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 15:09:44,251 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 15:09:44,251 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 15:09:44,251 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 15:09:44,251 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:09:44,252 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 15:09:44,252 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 15:09:44,252 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 15:09:44,253 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 15:09:44,253 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 15:09:44,253 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 15:09:44,253 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 15:09:44,253 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 15:09:44,253 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 15:09:44,254 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Trace refinement strategy -> FIXED_PREFERENCES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Allow undefined functions -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMT solver -> External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Command for external solver -> z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:44,420 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 15:09:44,438 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 15:09:44,439 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 15:09:44,440 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 15:09:44,440 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 15:09:44,441 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_rend_harness_negated.i [2024-11-04 15:09:45,585 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 15:09:45,884 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 15:09:45,885 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_rend_harness_negated.i [2024-11-04 15:09:45,907 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0eb1fa233/4916a6da0ddd469e86efc2695c3a8d74/FLAG229f79430 [2024-11-04 15:09:46,166 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0eb1fa233/4916a6da0ddd469e86efc2695c3a8d74 [2024-11-04 15:09:46,168 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 15:09:46,169 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 15:09:46,170 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 15:09:46,170 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 15:09:46,174 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 15:09:46,174 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:09:46" (1/1) ... [2024-11-04 15:09:46,175 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6cd592d6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:46, skipping insertion in model container [2024-11-04 15:09:46,175 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 03:09:46" (1/1) ... [2024-11-04 15:09:46,245 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:09:46,461 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_rend_harness_negated.i[4494,4507] [2024-11-04 15:09:46,467 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_rend_harness_negated.i[4554,4567] [2024-11-04 15:09:46,788 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,850 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,851 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,851 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,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:09:46,864 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,865 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,868 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,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:09:46,868 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,869 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,871 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,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:09:46,877 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,877 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,885 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,886 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,886 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,886 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,887 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,888 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,888 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,888 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,890 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,890 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,891 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,891 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:46,891 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:46,891 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,084 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,085 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,085 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,086 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,175 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,184 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:09:47,205 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 15:09:47,238 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 15:09:47,241 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_rend_harness_negated.i[4494,4507] [2024-11-04 15:09:47,241 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_rend_harness_negated.i[4554,4567] [2024-11-04 15:09:47,261 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,274 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,274 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,274 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,278 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,278 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,279 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,279 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,279 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,279 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,280 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,281 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,281 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,282 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,282 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,285 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,285 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,285 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,285 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,286 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,286 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,286 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,287 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,290 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,290 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,290 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,291 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,291 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,291 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,341 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,341 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,342 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,342 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,378 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 15:09:47,388 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:09:47,394 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 15:09:47,407 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_rend_harness_negated.i[4494,4507] [2024-11-04 15:09:47,407 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_rend_harness_negated.i[4554,4567] [2024-11-04 15:09:47,442 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,442 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,443 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,443 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,443 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,450 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,450 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,451 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,452 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,453 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,453 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,454 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,454 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 15:09:47,516 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 15:09:47,657 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 15:09:47,667 INFO L204 MainTranslator]: Completed translation [2024-11-04 15:09:47,668 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47 WrapperNode [2024-11-04 15:09:47,668 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 15:09:47,668 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 15:09:47,668 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 15:09:47,669 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 15:09:47,676 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:09:47" (1/1) ... [2024-11-04 15:09:47,727 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:09:47" (1/1) ... [2024-11-04 15:09:47,755 INFO L138 Inliner]: procedures = 687, calls = 1038, calls flagged for inlining = 52, calls inlined = 6, statements flattened = 138 [2024-11-04 15:09:47,756 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 15:09:47,756 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 15:09:47,756 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 15:09:47,756 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 15:09:47,764 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,764 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,767 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,779 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:09:47,780 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,780 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,788 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,790 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,793 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,795 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,799 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 15:09:47,799 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 15:09:47,799 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 15:09:47,799 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 15:09:47,800 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (1/1) ... [2024-11-04 15:09:47,804 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 15:09:47,817 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:47,827 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:09:47,836 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:09:47,852 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 15:09:47,852 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 15:09:47,852 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 15:09:47,852 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 15:09:47,852 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 15:09:47,853 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:09:47,853 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-04 15:09:47,853 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 15:09:47,853 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 15:09:47,853 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 15:09:47,853 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 15:09:47,854 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 15:09:47,854 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 15:09:47,854 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 15:09:47,854 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 15:09:47,854 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 15:09:47,854 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 15:09:47,854 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-04 15:09:47,854 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-04 15:09:48,055 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 15:09:48,056 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 15:09:48,273 INFO L? ?]: Removed 54 outVars from TransFormulas that were not future-live. [2024-11-04 15:09:48,273 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 15:09:48,286 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 15:09:48,287 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-04 15:09:48,287 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:09:48 BoogieIcfgContainer [2024-11-04 15:09:48,287 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 15:09:48,288 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 15:09:48,288 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 15:09:48,292 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 15:09:48,292 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 03:09:46" (1/3) ... [2024-11-04 15:09:48,293 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@234ab08 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:09:48, skipping insertion in model container [2024-11-04 15:09:48,293 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 03:09:47" (2/3) ... [2024-11-04 15:09:48,293 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@234ab08 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 03:09:48, skipping insertion in model container [2024-11-04 15:09:48,293 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 03:09:48" (3/3) ... [2024-11-04 15:09:48,294 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_rend_harness_negated.i [2024-11-04 15:09:48,305 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 15:09:48,305 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 15:09:48,350 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 15:09:48,355 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;@62351242, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 15:09:48,355 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 15:09:48,358 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:09:48,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-04 15:09:48,366 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:48,367 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:09:48,368 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:48,371 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:48,371 INFO L85 PathProgramCache]: Analyzing trace with hash -2107862704, now seen corresponding path program 1 times [2024-11-04 15:09:48,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:48,378 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [552350122] [2024-11-04 15:09:48,378 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:48,379 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:48,379 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:48,382 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:09:48,383 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:09:48,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:48,580 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 15:09:48,587 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:48,611 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:09:48,611 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:48,642 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:09:48,643 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:48,643 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [552350122] [2024-11-04 15:09:48,644 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [552350122] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:48,644 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:48,644 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-04 15:09:48,645 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1970830327] [2024-11-04 15:09:48,645 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:48,648 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 15:09:48,648 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:48,663 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 15:09:48,663 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 15:09:48,665 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:09:48,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:48,707 INFO L93 Difference]: Finished difference Result 128 states and 184 transitions. [2024-11-04 15:09:48,708 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 15:09:48,709 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:09:48,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:48,715 INFO L225 Difference]: With dead ends: 128 [2024-11-04 15:09:48,715 INFO L226 Difference]: Without dead ends: 63 [2024-11-04 15:09:48,719 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:09:48,722 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:09:48,722 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:09:48,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-04 15:09:48,753 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2024-11-04 15:09:48,754 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:09:48,758 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 82 transitions. [2024-11-04 15:09:48,759 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 82 transitions. Word has length 68 [2024-11-04 15:09:48,759 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:48,759 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 82 transitions. [2024-11-04 15:09:48,759 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:09:48,760 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 82 transitions. [2024-11-04 15:09:48,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-04 15:09:48,764 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:48,764 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:09:48,780 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:09:48,964 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:09:48,967 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:48,967 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:48,967 INFO L85 PathProgramCache]: Analyzing trace with hash 900796622, now seen corresponding path program 1 times [2024-11-04 15:09:48,967 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:48,967 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1922432363] [2024-11-04 15:09:48,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:48,968 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:48,968 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:48,969 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:09:48,970 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:09:49,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:49,104 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:09:49,108 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:49,166 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:09:49,166 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:49,238 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:09:49,238 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:49,238 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1922432363] [2024-11-04 15:09:49,238 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1922432363] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:49,238 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:49,238 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 15:09:49,239 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1903250347] [2024-11-04 15:09:49,239 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:49,239 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:09:49,240 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:49,240 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:09:49,240 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:09:49,240 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:09:49,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:49,281 INFO L93 Difference]: Finished difference Result 114 states and 152 transitions. [2024-11-04 15:09:49,283 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:09:49,283 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:09:49,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:49,285 INFO L225 Difference]: With dead ends: 114 [2024-11-04 15:09:49,285 INFO L226 Difference]: Without dead ends: 65 [2024-11-04 15:09:49,286 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:09:49,286 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.0s IncrementalHoareTripleChecker+Time [2024-11-04 15:09:49,286 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.0s Time] [2024-11-04 15:09:49,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-11-04 15:09:49,292 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2024-11-04 15:09:49,292 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:09:49,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 86 transitions. [2024-11-04 15:09:49,293 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 86 transitions. Word has length 68 [2024-11-04 15:09:49,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:49,294 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 86 transitions. [2024-11-04 15:09:49,294 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:09:49,294 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 86 transitions. [2024-11-04 15:09:49,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-04 15:09:49,295 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:49,295 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:09:49,310 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:09:49,495 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:09:49,496 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:49,496 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:49,496 INFO L85 PathProgramCache]: Analyzing trace with hash 577933322, now seen corresponding path program 1 times [2024-11-04 15:09:49,496 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:49,496 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [578170861] [2024-11-04 15:09:49,496 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:49,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:49,497 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:49,498 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:09:49,499 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:09:49,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:49,615 INFO L255 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:09:49,618 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:49,679 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:09:49,680 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:49,806 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:09:49,806 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:49,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [578170861] [2024-11-04 15:09:49,807 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [578170861] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:49,807 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:49,807 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2024-11-04 15:09:49,807 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1278768322] [2024-11-04 15:09:49,807 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:49,807 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:09:49,807 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:49,808 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:09:49,808 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:09:49,808 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:09:49,896 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:49,896 INFO L93 Difference]: Finished difference Result 121 states and 163 transitions. [2024-11-04 15:09:49,896 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:09:49,896 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:09:49,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:49,897 INFO L225 Difference]: With dead ends: 121 [2024-11-04 15:09:49,897 INFO L226 Difference]: Without dead ends: 70 [2024-11-04 15:09:49,898 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 132 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:09:49,898 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:09:49,899 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:09:49,899 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-04 15:09:49,908 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2024-11-04 15:09:49,908 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:09:49,909 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 90 transitions. [2024-11-04 15:09:49,909 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 90 transitions. Word has length 70 [2024-11-04 15:09:49,909 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:49,909 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 90 transitions. [2024-11-04 15:09:49,910 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:09:49,910 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 90 transitions. [2024-11-04 15:09:49,911 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-04 15:09:49,911 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:49,911 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:09:49,929 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:09:50,111 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:09:50,115 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:50,116 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:50,116 INFO L85 PathProgramCache]: Analyzing trace with hash -34807881, now seen corresponding path program 1 times [2024-11-04 15:09:50,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:50,116 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [125628589] [2024-11-04 15:09:50,116 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:50,116 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:50,116 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:50,117 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:09:50,118 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:09:50,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:50,241 INFO L255 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 15:09:50,247 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:50,318 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:09:50,318 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:50,454 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:09:50,455 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:50,455 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [125628589] [2024-11-04 15:09:50,455 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [125628589] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:50,455 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:50,455 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 10 [2024-11-04 15:09:50,455 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [323560213] [2024-11-04 15:09:50,455 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:50,456 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:09:50,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:50,456 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:09:50,456 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 15:09:50,456 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:09:50,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:50,602 INFO L93 Difference]: Finished difference Result 133 states and 181 transitions. [2024-11-04 15:09:50,602 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 15:09:50,602 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:09:50,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:50,604 INFO L225 Difference]: With dead ends: 133 [2024-11-04 15:09:50,604 INFO L226 Difference]: Without dead ends: 79 [2024-11-04 15:09:50,605 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:09:50,605 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.1s IncrementalHoareTripleChecker+Time [2024-11-04 15:09:50,606 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.1s Time] [2024-11-04 15:09:50,607 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2024-11-04 15:09:50,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 70. [2024-11-04 15:09:50,612 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:09:50,613 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 93 transitions. [2024-11-04 15:09:50,613 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 93 transitions. Word has length 72 [2024-11-04 15:09:50,613 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:50,613 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 93 transitions. [2024-11-04 15:09:50,613 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:09:50,613 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 93 transitions. [2024-11-04 15:09:50,614 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-04 15:09:50,614 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:50,614 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:09:50,629 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:09:50,815 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:09:50,815 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:50,816 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:50,816 INFO L85 PathProgramCache]: Analyzing trace with hash 387052583, now seen corresponding path program 1 times [2024-11-04 15:09:50,816 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:50,816 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [303526618] [2024-11-04 15:09:50,816 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:50,816 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:50,816 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:50,818 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:09:50,818 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:09:50,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:50,949 INFO L255 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-04 15:09:50,950 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:50,963 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:09:50,963 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:50,992 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:09:50,992 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:50,992 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [303526618] [2024-11-04 15:09:50,992 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [303526618] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:50,992 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:50,992 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 4 [2024-11-04 15:09:50,992 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [523572377] [2024-11-04 15:09:50,992 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:50,993 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-04 15:09:50,993 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:50,993 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-04 15:09:50,993 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:09:50,993 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:09:51,013 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:51,013 INFO L93 Difference]: Finished difference Result 130 states and 180 transitions. [2024-11-04 15:09:51,013 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-04 15:09:51,013 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:09:51,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:51,014 INFO L225 Difference]: With dead ends: 130 [2024-11-04 15:09:51,014 INFO L226 Difference]: Without dead ends: 74 [2024-11-04 15:09:51,015 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:09:51,015 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:09:51,016 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:09:51,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-04 15:09:51,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2024-11-04 15:09:51,026 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:09:51,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 94 transitions. [2024-11-04 15:09:51,026 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 94 transitions. Word has length 73 [2024-11-04 15:09:51,027 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:51,027 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 94 transitions. [2024-11-04 15:09:51,027 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:09:51,027 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 94 transitions. [2024-11-04 15:09:51,031 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 82 [2024-11-04 15:09:51,031 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:51,031 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:09:51,046 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:09:51,231 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:09:51,232 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:51,232 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:51,232 INFO L85 PathProgramCache]: Analyzing trace with hash 1595103561, now seen corresponding path program 1 times [2024-11-04 15:09:51,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:51,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [851761715] [2024-11-04 15:09:51,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:51,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:51,233 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:51,234 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:09:51,236 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:09:51,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:51,379 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:09:51,380 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:51,404 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:09:51,404 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:51,455 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:09:51,455 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:51,456 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [851761715] [2024-11-04 15:09:51,456 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [851761715] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:51,456 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:51,456 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 15:09:51,456 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1736092314] [2024-11-04 15:09:51,456 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:51,456 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 15:09:51,456 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:51,457 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 15:09:51,457 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 15:09:51,457 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:09:51,485 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:51,485 INFO L93 Difference]: Finished difference Result 121 states and 161 transitions. [2024-11-04 15:09:51,485 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:09:51,485 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:09:51,486 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:51,487 INFO L225 Difference]: With dead ends: 121 [2024-11-04 15:09:51,487 INFO L226 Difference]: Without dead ends: 71 [2024-11-04 15:09:51,487 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:09:51,487 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:09:51,488 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:09:51,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2024-11-04 15:09:51,492 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2024-11-04 15:09:51,492 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:09:51,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 93 transitions. [2024-11-04 15:09:51,493 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 93 transitions. Word has length 81 [2024-11-04 15:09:51,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:51,493 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 93 transitions. [2024-11-04 15:09:51,493 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:09:51,493 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 93 transitions. [2024-11-04 15:09:51,494 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-11-04 15:09:51,494 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:51,494 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:09:51,509 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2024-11-04 15:09:51,695 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:09:51,695 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:51,695 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:51,695 INFO L85 PathProgramCache]: Analyzing trace with hash -1338639547, now seen corresponding path program 1 times [2024-11-04 15:09:51,696 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:51,696 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1448521321] [2024-11-04 15:09:51,696 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:51,696 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:51,696 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:51,697 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:09:51,698 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:09:51,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:51,825 INFO L255 TraceCheckSpWp]: Trace formula consists of 247 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 15:09:51,827 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:51,878 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:09:51,878 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:51,993 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:09:51,993 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:51,993 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1448521321] [2024-11-04 15:09:51,993 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1448521321] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:51,994 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:51,994 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2024-11-04 15:09:51,994 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1553519961] [2024-11-04 15:09:51,994 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:51,994 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:09:51,994 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:51,995 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:09:51,995 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:09:51,995 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:09:52,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:52,097 INFO L93 Difference]: Finished difference Result 130 states and 169 transitions. [2024-11-04 15:09:52,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:09:52,098 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:09:52,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:52,099 INFO L225 Difference]: With dead ends: 130 [2024-11-04 15:09:52,099 INFO L226 Difference]: Without dead ends: 73 [2024-11-04 15:09:52,099 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 165 GetRequests, 157 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 15:09:52,100 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:09:52,100 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:09:52,100 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2024-11-04 15:09:52,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2024-11-04 15:09:52,110 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:09:52,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 92 transitions. [2024-11-04 15:09:52,111 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 92 transitions. Word has length 83 [2024-11-04 15:09:52,111 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:52,111 INFO L471 AbstractCegarLoop]: Abstraction has 71 states and 92 transitions. [2024-11-04 15:09:52,111 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:09:52,111 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 92 transitions. [2024-11-04 15:09:52,112 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2024-11-04 15:09:52,112 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:52,112 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:09:52,127 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-04 15:09:52,316 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:09:52,317 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:52,317 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:52,317 INFO L85 PathProgramCache]: Analyzing trace with hash 1040869362, now seen corresponding path program 1 times [2024-11-04 15:09:52,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:52,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1690680586] [2024-11-04 15:09:52,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:52,317 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:52,318 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:52,319 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:09:52,319 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:09:52,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:52,443 INFO L255 TraceCheckSpWp]: Trace formula consists of 251 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 15:09:52,445 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:52,510 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:09:52,510 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:52,645 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:09:52,645 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:52,645 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1690680586] [2024-11-04 15:09:52,645 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1690680586] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:52,645 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:52,645 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 15:09:52,645 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [873076429] [2024-11-04 15:09:52,646 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:52,646 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:09:52,646 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:52,646 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:09:52,646 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 15:09:52,647 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:09:52,775 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:52,775 INFO L93 Difference]: Finished difference Result 130 states and 168 transitions. [2024-11-04 15:09:52,776 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 15:09:52,776 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:09:52,776 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:52,777 INFO L225 Difference]: With dead ends: 130 [2024-11-04 15:09:52,777 INFO L226 Difference]: Without dead ends: 72 [2024-11-04 15:09:52,777 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:09:52,778 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:09:52,778 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:09:52,778 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2024-11-04 15:09:52,788 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 67. [2024-11-04 15:09:52,788 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:09:52,788 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 86 transitions. [2024-11-04 15:09:52,789 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 86 transitions. Word has length 85 [2024-11-04 15:09:52,789 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:52,789 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 86 transitions. [2024-11-04 15:09:52,789 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:09:52,789 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 86 transitions. [2024-11-04 15:09:52,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2024-11-04 15:09:52,790 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:52,790 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:09:52,806 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2024-11-04 15:09:52,990 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:09:52,990 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:52,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:52,991 INFO L85 PathProgramCache]: Analyzing trace with hash -1678268318, now seen corresponding path program 2 times [2024-11-04 15:09:52,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:52,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [640309854] [2024-11-04 15:09:52,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:52,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:52,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:52,992 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:09:52,993 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:09:53,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:53,123 INFO L255 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:09:53,124 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:53,158 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:09:53,158 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:53,217 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:09:53,217 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:53,217 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [640309854] [2024-11-04 15:09:53,218 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [640309854] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:53,218 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:53,218 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 15:09:53,218 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2010776170] [2024-11-04 15:09:53,218 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:53,218 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:09:53,218 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:53,219 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:09:53,219 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:09:53,219 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:09:53,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:53,253 INFO L93 Difference]: Finished difference Result 123 states and 161 transitions. [2024-11-04 15:09:53,253 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:09:53,254 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:09:53,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:53,254 INFO L225 Difference]: With dead ends: 123 [2024-11-04 15:09:53,254 INFO L226 Difference]: Without dead ends: 70 [2024-11-04 15:09:53,255 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:09:53,255 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:09:53,255 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:09:53,256 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-04 15:09:53,259 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 70. [2024-11-04 15:09:53,259 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:09:53,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 91 transitions. [2024-11-04 15:09:53,260 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 91 transitions. Word has length 94 [2024-11-04 15:09:53,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:53,260 INFO L471 AbstractCegarLoop]: Abstraction has 70 states and 91 transitions. [2024-11-04 15:09:53,260 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:09:53,260 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 91 transitions. [2024-11-04 15:09:53,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2024-11-04 15:09:53,261 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:53,261 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:09:53,275 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:09:53,461 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:09:53,461 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:53,462 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:53,462 INFO L85 PathProgramCache]: Analyzing trace with hash -1005701739, now seen corresponding path program 1 times [2024-11-04 15:09:53,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:53,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1405639283] [2024-11-04 15:09:53,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:53,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:53,463 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:53,464 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:09:53,465 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:09:53,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:53,607 INFO L255 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:09:53,609 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:53,638 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:09:53,639 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:53,707 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:09:53,707 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:53,707 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1405639283] [2024-11-04 15:09:53,707 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1405639283] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:09:53,708 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:09:53,708 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 15:09:53,708 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [648743611] [2024-11-04 15:09:53,708 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:09:53,708 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 15:09:53,708 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:53,709 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 15:09:53,709 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:09:53,709 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:09:53,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:53,744 INFO L93 Difference]: Finished difference Result 119 states and 156 transitions. [2024-11-04 15:09:53,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:09:53,746 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:09:53,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:53,747 INFO L225 Difference]: With dead ends: 119 [2024-11-04 15:09:53,747 INFO L226 Difference]: Without dead ends: 70 [2024-11-04 15:09:53,747 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:09:53,748 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:09:53,748 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:09:53,748 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2024-11-04 15:09:53,754 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 68. [2024-11-04 15:09:53,754 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:09:53,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 87 transitions. [2024-11-04 15:09:53,755 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 87 transitions. Word has length 96 [2024-11-04 15:09:53,755 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:53,758 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 87 transitions. [2024-11-04 15:09:53,758 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:09:53,758 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 87 transitions. [2024-11-04 15:09:53,758 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-04 15:09:53,758 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:53,759 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:09:53,775 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:09:53,959 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:09:53,959 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:53,959 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:53,960 INFO L85 PathProgramCache]: Analyzing trace with hash -1128444350, now seen corresponding path program 1 times [2024-11-04 15:09:53,960 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:53,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [493136787] [2024-11-04 15:09:53,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:53,960 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:53,960 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:53,961 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:09:53,962 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:09:54,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:09:54,103 INFO L255 TraceCheckSpWp]: Trace formula consists of 281 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-04 15:09:54,106 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:09:54,146 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:09:54,152 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:09:58,423 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:09:58,636 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:09:58,636 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:09:58,907 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:09:58,907 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:09:58,907 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [493136787] [2024-11-04 15:09:58,907 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [493136787] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:09:58,907 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:09:58,907 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 17 [2024-11-04 15:09:58,907 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [179848738] [2024-11-04 15:09:58,907 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:09:58,908 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-04 15:09:58,908 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:09:58,908 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-04 15:09:58,908 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=199, Unknown=1, NotChecked=28, Total=272 [2024-11-04 15:09:58,909 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:09:59,684 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:09:59,684 INFO L93 Difference]: Finished difference Result 166 states and 228 transitions. [2024-11-04 15:09:59,684 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 15:09:59,685 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:09:59,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:09:59,686 INFO L225 Difference]: With dead ends: 166 [2024-11-04 15:09:59,686 INFO L226 Difference]: Without dead ends: 112 [2024-11-04 15:09:59,687 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 203 GetRequests, 182 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=76, Invalid=347, Unknown=1, NotChecked=38, Total=462 [2024-11-04 15:09:59,687 INFO L432 NwaCegarLoop]: 77 mSDtfsCounter, 64 mSDsluCounter, 637 mSDsCounter, 0 mSdLazyCounter, 369 mSolverCounterSat, 13 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s 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.6s IncrementalHoareTripleChecker+Time [2024-11-04 15:09:59,687 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.6s Time] [2024-11-04 15:09:59,688 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2024-11-04 15:09:59,694 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 86. [2024-11-04 15:09:59,695 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:09:59,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 112 transitions. [2024-11-04 15:09:59,697 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 112 transitions. Word has length 98 [2024-11-04 15:09:59,697 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:09:59,697 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 112 transitions. [2024-11-04 15:09:59,697 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:09:59,697 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 112 transitions. [2024-11-04 15:09:59,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-04 15:09:59,698 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:09:59,698 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:09:59,716 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:09:59,898 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:09:59,899 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:09:59,899 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:09:59,899 INFO L85 PathProgramCache]: Analyzing trace with hash 604075650, now seen corresponding path program 1 times [2024-11-04 15:09:59,899 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:09:59,899 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1328135508] [2024-11-04 15:09:59,899 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:09:59,899 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:09:59,899 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:09:59,900 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:09:59,901 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2024-11-04 15:10:00,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:00,024 INFO L255 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:10:00,026 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:00,033 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:10:00,033 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:00,073 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:10:00,074 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:00,074 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1328135508] [2024-11-04 15:10:00,074 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1328135508] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:00,074 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:00,074 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:10:00,074 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1470310007] [2024-11-04 15:10:00,074 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:00,074 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:10:00,074 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:00,075 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:10:00,075 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:00,075 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:10:00,093 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:00,094 INFO L93 Difference]: Finished difference Result 159 states and 214 transitions. [2024-11-04 15:10:00,094 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:10:00,095 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:10:00,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:00,097 INFO L225 Difference]: With dead ends: 159 [2024-11-04 15:10:00,097 INFO L226 Difference]: Without dead ends: 87 [2024-11-04 15:10:00,097 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:10:00,098 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:10:00,098 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:10:00,098 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2024-11-04 15:10:00,103 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 86. [2024-11-04 15:10:00,103 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:10:00,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 86 states to 86 states and 111 transitions. [2024-11-04 15:10:00,104 INFO L78 Accepts]: Start accepts. Automaton has 86 states and 111 transitions. Word has length 98 [2024-11-04 15:10:00,104 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:00,104 INFO L471 AbstractCegarLoop]: Abstraction has 86 states and 111 transitions. [2024-11-04 15:10:00,104 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:10:00,104 INFO L276 IsEmpty]: Start isEmpty. Operand 86 states and 111 transitions. [2024-11-04 15:10:00,105 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 99 [2024-11-04 15:10:00,105 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:00,105 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:10:00,120 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:10:00,305 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:00,306 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:00,306 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:00,306 INFO L85 PathProgramCache]: Analyzing trace with hash 1924312770, now seen corresponding path program 1 times [2024-11-04 15:10:00,306 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:00,306 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1312604555] [2024-11-04 15:10:00,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:00,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:00,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:00,307 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:00,308 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-04 15:10:00,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:00,446 INFO L255 TraceCheckSpWp]: Trace formula consists of 269 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 15:10:00,448 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:00,456 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:10:00,456 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:00,485 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:10:00,485 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:00,485 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1312604555] [2024-11-04 15:10:00,485 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1312604555] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 15:10:00,485 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 15:10:00,485 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 15:10:00,486 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1850645166] [2024-11-04 15:10:00,486 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:00,486 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 15:10:00,486 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:00,487 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 15:10:00,487 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 15:10:00,487 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:10:00,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:00,505 INFO L93 Difference]: Finished difference Result 158 states and 213 transitions. [2024-11-04 15:10:00,506 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 15:10:00,506 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:10:00,506 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:00,507 INFO L225 Difference]: With dead ends: 158 [2024-11-04 15:10:00,507 INFO L226 Difference]: Without dead ends: 86 [2024-11-04 15:10:00,507 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:10:00,507 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:10:00,508 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:10:00,508 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 86 states. [2024-11-04 15:10:00,513 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 86 to 83. [2024-11-04 15:10:00,514 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:10:00,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 106 transitions. [2024-11-04 15:10:00,514 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 106 transitions. Word has length 98 [2024-11-04 15:10:00,515 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:00,515 INFO L471 AbstractCegarLoop]: Abstraction has 83 states and 106 transitions. [2024-11-04 15:10:00,515 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:10:00,515 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 106 transitions. [2024-11-04 15:10:00,516 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2024-11-04 15:10:00,516 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:00,516 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:10:00,532 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:10:00,716 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:00,716 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:00,717 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:00,717 INFO L85 PathProgramCache]: Analyzing trace with hash -1438193982, now seen corresponding path program 1 times [2024-11-04 15:10:00,717 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:00,717 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1621800453] [2024-11-04 15:10:00,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:00,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:00,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:00,718 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:00,719 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2024-11-04 15:10:00,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:00,852 INFO L255 TraceCheckSpWp]: Trace formula consists of 285 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 15:10:00,853 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:00,878 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:10:00,878 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:00,919 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:10:00,919 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:00,919 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1621800453] [2024-11-04 15:10:00,919 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1621800453] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:10:00,919 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:10:00,919 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6, 6] imperfect sequences [] total 8 [2024-11-04 15:10:00,919 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [967086783] [2024-11-04 15:10:00,919 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:00,920 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 15:10:00,920 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:00,920 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 15:10:00,920 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 15:10:00,920 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:10:00,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:00,947 INFO L93 Difference]: Finished difference Result 93 states and 117 transitions. [2024-11-04 15:10:00,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 15:10:00,948 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:10:00,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:00,948 INFO L225 Difference]: With dead ends: 93 [2024-11-04 15:10:00,948 INFO L226 Difference]: Without dead ends: 91 [2024-11-04 15:10:00,949 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:10:00,949 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:10:00,949 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:10:00,950 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2024-11-04 15:10:00,953 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 90. [2024-11-04 15:10:00,954 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:10:00,954 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 114 transitions. [2024-11-04 15:10:00,954 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 114 transitions. Word has length 100 [2024-11-04 15:10:00,954 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:00,955 INFO L471 AbstractCegarLoop]: Abstraction has 90 states and 114 transitions. [2024-11-04 15:10:00,955 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:10:00,955 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 114 transitions. [2024-11-04 15:10:00,955 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:10:00,955 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:00,955 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:10:00,970 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:10:01,156 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:01,156 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:01,156 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:01,156 INFO L85 PathProgramCache]: Analyzing trace with hash 166988707, now seen corresponding path program 1 times [2024-11-04 15:10:01,156 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:01,157 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1845429641] [2024-11-04 15:10:01,157 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:01,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:01,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:01,158 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:01,159 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2024-11-04 15:10:01,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:01,297 INFO L255 TraceCheckSpWp]: Trace formula consists of 293 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-04 15:10:01,299 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:01,331 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:10:01,335 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:10:02,449 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:10:02,449 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:03,068 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:10:03,068 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:03,068 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1845429641] [2024-11-04 15:10:03,068 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1845429641] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:10:03,068 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:10:03,069 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 10] total 21 [2024-11-04 15:10:03,069 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [601745127] [2024-11-04 15:10:03,069 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:10:03,069 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-04 15:10:03,069 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:03,071 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-04 15:10:03,071 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2024-11-04 15:10:03,072 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:10:07,615 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:10:11,900 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:10:15,960 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:10:19,987 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:10:22,013 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:22,013 INFO L93 Difference]: Finished difference Result 210 states and 261 transitions. [2024-11-04 15:10:22,013 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 15:10:22,014 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:10:22,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:22,015 INFO L225 Difference]: With dead ends: 210 [2024-11-04 15:10:22,015 INFO L226 Difference]: Without dead ends: 133 [2024-11-04 15:10:22,016 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 221 GetRequests, 187 SyntacticMatches, 7 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 200 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=146, Invalid=666, Unknown=0, NotChecked=0, Total=812 [2024-11-04 15:10:22,016 INFO L432 NwaCegarLoop]: 85 mSDtfsCounter, 91 mSDsluCounter, 715 mSDsCounter, 0 mSdLazyCounter, 464 mSolverCounterSat, 31 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 18.4s 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, 18.5s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:22,017 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 800 Invalid, 499 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 464 Invalid, 4 Unknown, 0 Unchecked, 18.5s Time] [2024-11-04 15:10:22,017 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2024-11-04 15:10:22,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 131. [2024-11-04 15:10:22,026 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:10:22,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 160 transitions. [2024-11-04 15:10:22,027 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 160 transitions. Word has length 106 [2024-11-04 15:10:22,027 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:22,027 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 160 transitions. [2024-11-04 15:10:22,027 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:10:22,027 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 160 transitions. [2024-11-04 15:10:22,028 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:10:22,028 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:22,028 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:10:22,047 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:10:22,228 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:22,228 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:22,229 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:22,229 INFO L85 PathProgramCache]: Analyzing trace with hash -844128543, now seen corresponding path program 1 times [2024-11-04 15:10:22,229 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:22,229 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1288763682] [2024-11-04 15:10:22,229 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:22,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:22,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:22,231 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:22,231 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2024-11-04 15:10:22,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:22,372 INFO L255 TraceCheckSpWp]: Trace formula consists of 290 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-04 15:10:22,378 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:22,520 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 7 [2024-11-04 15:10:22,529 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-04 15:10:22,530 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 1 [2024-11-04 15:10:23,739 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:10:23,739 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:24,262 INFO L349 Elim1Store]: treesize reduction 19, result has 62.0 percent of original size [2024-11-04 15:10:24,262 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:10:24,274 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 72 treesize of output 68 [2024-11-04 15:10:24,304 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 15:10:24,304 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 91 treesize of output 93 [2024-11-04 15:10:24,439 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:10:24,459 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:10:24,694 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:10:24,695 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:24,695 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1288763682] [2024-11-04 15:10:24,695 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1288763682] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:10:24,695 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:10:24,695 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11, 10] imperfect sequences [] total 19 [2024-11-04 15:10:24,695 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [866048214] [2024-11-04 15:10:24,695 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:24,695 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-04 15:10:24,696 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:24,696 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-04 15:10:24,696 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=283, Unknown=0, NotChecked=0, Total=342 [2024-11-04 15:10:24,696 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:10:26,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:26,482 INFO L93 Difference]: Finished difference Result 319 states and 393 transitions. [2024-11-04 15:10:26,482 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-04 15:10:26,483 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:10:26,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:26,484 INFO L225 Difference]: With dead ends: 319 [2024-11-04 15:10:26,484 INFO L226 Difference]: Without dead ends: 248 [2024-11-04 15:10:26,485 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 219 GetRequests, 186 SyntacticMatches, 8 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 163 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=120, Invalid=582, Unknown=0, NotChecked=0, Total=702 [2024-11-04 15:10:26,485 INFO L432 NwaCegarLoop]: 61 mSDtfsCounter, 68 mSDsluCounter, 482 mSDsCounter, 0 mSdLazyCounter, 337 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s 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.2s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:26,485 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.2s Time] [2024-11-04 15:10:26,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2024-11-04 15:10:26,496 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 131. [2024-11-04 15:10:26,497 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:10:26,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 159 transitions. [2024-11-04 15:10:26,497 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 159 transitions. Word has length 106 [2024-11-04 15:10:26,498 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:26,498 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 159 transitions. [2024-11-04 15:10:26,498 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:10:26,498 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 159 transitions. [2024-11-04 15:10:26,498 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:10:26,498 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:26,499 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:10:26,514 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:26,699 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:26,699 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:26,699 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:26,699 INFO L85 PathProgramCache]: Analyzing trace with hash -1865196897, now seen corresponding path program 1 times [2024-11-04 15:10:26,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:26,700 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1912851096] [2024-11-04 15:10:26,700 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:26,700 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:26,700 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:26,701 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:26,701 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-11-04 15:10:26,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:26,852 INFO L255 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-04 15:10:26,855 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:26,916 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:10:26,919 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:10:28,896 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:10:28,896 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:29,983 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:10:29,983 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:29,983 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1912851096] [2024-11-04 15:10:29,983 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1912851096] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:10:29,983 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:10:29,983 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12] total 25 [2024-11-04 15:10:29,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [282533260] [2024-11-04 15:10:29,983 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:10:29,984 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-04 15:10:29,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:29,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-04 15:10:29,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=508, Unknown=0, NotChecked=0, Total=600 [2024-11-04 15:10:29,985 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:10:34,050 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:10:38,155 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:10:42,346 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:10:44,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:44,333 INFO L93 Difference]: Finished difference Result 196 states and 239 transitions. [2024-11-04 15:10:44,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 15:10:44,334 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:10:44,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:44,335 INFO L225 Difference]: With dead ends: 196 [2024-11-04 15:10:44,335 INFO L226 Difference]: Without dead ends: 131 [2024-11-04 15:10:44,335 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 182 SyntacticMatches, 7 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 250 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=183, Invalid=873, Unknown=0, NotChecked=0, Total=1056 [2024-11-04 15:10:44,336 INFO L432 NwaCegarLoop]: 79 mSDtfsCounter, 76 mSDsluCounter, 775 mSDsCounter, 0 mSdLazyCounter, 561 mSolverCounterSat, 23 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.7s 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, 13.8s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:44,336 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [79 Valid, 854 Invalid, 587 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 561 Invalid, 3 Unknown, 0 Unchecked, 13.8s Time] [2024-11-04 15:10:44,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 131 states. [2024-11-04 15:10:44,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 131 to 131. [2024-11-04 15:10:44,348 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:10:44,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 158 transitions. [2024-11-04 15:10:44,349 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 158 transitions. Word has length 106 [2024-11-04 15:10:44,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:44,349 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 158 transitions. [2024-11-04 15:10:44,349 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:10:44,350 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 158 transitions. [2024-11-04 15:10:44,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 15:10:44,350 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:44,350 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:10:44,366 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2024-11-04 15:10:44,550 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:44,551 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:44,551 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:44,551 INFO L85 PathProgramCache]: Analyzing trace with hash 435625693, now seen corresponding path program 1 times [2024-11-04 15:10:44,551 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:44,551 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1217586290] [2024-11-04 15:10:44,551 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:44,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:44,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:44,553 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:44,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2024-11-04 15:10:44,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:44,707 INFO L255 TraceCheckSpWp]: Trace formula consists of 284 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-04 15:10:44,712 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:44,788 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 1 [2024-11-04 15:10:46,409 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:10:46,409 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:48,061 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:10:48,089 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:10:48,090 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:48,090 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1217586290] [2024-11-04 15:10:48,090 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1217586290] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 15:10:48,090 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 15:10:48,090 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 28 [2024-11-04 15:10:48,090 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [215953706] [2024-11-04 15:10:48,090 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 15:10:48,090 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2024-11-04 15:10:48,090 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:48,091 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-04 15:10:48,091 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=662, Unknown=0, NotChecked=0, Total=756 [2024-11-04 15:10:48,091 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:10:52,140 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:10:57,151 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:57,151 INFO L93 Difference]: Finished difference Result 344 states and 431 transitions. [2024-11-04 15:10:57,151 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-04 15:10:57,152 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:10:57,152 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:57,153 INFO L225 Difference]: With dead ends: 344 [2024-11-04 15:10:57,153 INFO L226 Difference]: Without dead ends: 233 [2024-11-04 15:10:57,154 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 239 GetRequests, 188 SyntacticMatches, 7 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 382 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=350, Invalid=1720, Unknown=0, NotChecked=0, Total=2070 [2024-11-04 15:10:57,154 INFO L432 NwaCegarLoop]: 101 mSDtfsCounter, 251 mSDsluCounter, 1039 mSDsCounter, 0 mSdLazyCounter, 948 mSolverCounterSat, 58 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.7s 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, 7.9s IncrementalHoareTripleChecker+Time [2024-11-04 15:10:57,154 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [267 Valid, 1140 Invalid, 1007 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 948 Invalid, 1 Unknown, 0 Unchecked, 7.9s Time] [2024-11-04 15:10:57,155 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2024-11-04 15:10:57,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 203. [2024-11-04 15:10:57,178 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:10:57,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 250 transitions. [2024-11-04 15:10:57,179 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 250 transitions. Word has length 106 [2024-11-04 15:10:57,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:57,179 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 250 transitions. [2024-11-04 15:10:57,180 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:10:57,180 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 250 transitions. [2024-11-04 15:10:57,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 114 [2024-11-04 15:10:57,180 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:57,180 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:10:57,195 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2024-11-04 15:10:57,381 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:57,381 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:57,381 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:57,381 INFO L85 PathProgramCache]: Analyzing trace with hash -2065682137, now seen corresponding path program 1 times [2024-11-04 15:10:57,381 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:57,382 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [273201582] [2024-11-04 15:10:57,382 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:57,382 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:57,382 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:57,383 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-04 15:10:57,385 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2024-11-04 15:10:57,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 15:10:57,542 INFO L255 TraceCheckSpWp]: Trace formula consists of 318 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 15:10:57,544 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 15:10:57,605 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:10:57,605 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 15:10:57,712 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:10:57,713 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 15:10:57,713 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [273201582] [2024-11-04 15:10:57,713 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [273201582] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 15:10:57,713 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 15:10:57,713 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7, 7] imperfect sequences [] total 9 [2024-11-04 15:10:57,713 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1808836755] [2024-11-04 15:10:57,713 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 15:10:57,713 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-04 15:10:57,713 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 15:10:57,714 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-04 15:10:57,714 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2024-11-04 15:10:57,714 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:10:57,809 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 15:10:57,809 INFO L93 Difference]: Finished difference Result 217 states and 265 transitions. [2024-11-04 15:10:57,809 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 15:10:57,810 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:10:57,810 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 15:10:57,811 INFO L225 Difference]: With dead ends: 217 [2024-11-04 15:10:57,811 INFO L226 Difference]: Without dead ends: 215 [2024-11-04 15:10:57,811 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:10:57,812 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:10:57,812 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:10:57,812 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 215 states. [2024-11-04 15:10:57,833 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 215 to 206. [2024-11-04 15:10:57,833 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:10:57,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 206 states to 206 states and 252 transitions. [2024-11-04 15:10:57,835 INFO L78 Accepts]: Start accepts. Automaton has 206 states and 252 transitions. Word has length 113 [2024-11-04 15:10:57,835 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 15:10:57,835 INFO L471 AbstractCegarLoop]: Abstraction has 206 states and 252 transitions. [2024-11-04 15:10:57,835 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:10:57,835 INFO L276 IsEmpty]: Start isEmpty. Operand 206 states and 252 transitions. [2024-11-04 15:10:57,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 15:10:57,836 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 15:10:57,836 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:10:57,851 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2024-11-04 15:10:58,036 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:10:58,036 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 15:10:58,037 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 15:10:58,037 INFO L85 PathProgramCache]: Analyzing trace with hash 1112769404, now seen corresponding path program 1 times [2024-11-04 15:10:58,037 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 15:10:58,037 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [103724428] [2024-11-04 15:10:58,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 15:10:58,037 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-04 15:10:58,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 15:10:58,038 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:10:58,039 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:10:58,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-04 15:10:58,309 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-04 15:10:58,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-04 15:10:58,518 INFO L130 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found a feasible trace [2024-11-04 15:10:58,518 INFO L325 BasicCegarLoop]: Counterexample is feasible [2024-11-04 15:10:58,518 INFO L782 garLoopResultBuilder]: Registering result UNSAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-04 15:10:58,539 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:10:58,720 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:10:58,722 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:10:58,781 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2024-11-04 15:10:58,783 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 04.11 03:10:58 BoogieIcfgContainer [2024-11-04 15:10:58,783 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2024-11-04 15:10:58,783 INFO L158 Benchmark]: Toolchain (without parser) took 72614.80ms. Allocated memory was 173.0MB in the beginning and 334.5MB in the end (delta: 161.5MB). Free memory was 112.6MB in the beginning and 274.6MB in the end (delta: -162.0MB). Peak memory consumption was 182.9MB. Max. memory is 8.0GB. [2024-11-04 15:10:58,783 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 173.0MB. Free memory was 127.4MB in the beginning and 127.2MB in the end (delta: 147.3kB). There was no memory consumed. Max. memory is 8.0GB. [2024-11-04 15:10:58,784 INFO L158 Benchmark]: CACSL2BoogieTranslator took 1498.17ms. Allocated memory was 173.0MB in the beginning and 268.4MB in the end (delta: 95.4MB). Free memory was 112.3MB in the beginning and 179.3MB in the end (delta: -67.0MB). Peak memory consumption was 102.6MB. Max. memory is 8.0GB. [2024-11-04 15:10:58,784 INFO L158 Benchmark]: Boogie Procedure Inliner took 87.41ms. Allocated memory is still 268.4MB. Free memory was 179.3MB in the beginning and 173.5MB in the end (delta: 5.8MB). Peak memory consumption was 5.2MB. Max. memory is 8.0GB. [2024-11-04 15:10:58,784 INFO L158 Benchmark]: Boogie Preprocessor took 42.41ms. Allocated memory is still 268.4MB. Free memory was 173.5MB in the beginning and 168.3MB in the end (delta: 5.2MB). Peak memory consumption was 5.2MB. Max. memory is 8.0GB. [2024-11-04 15:10:58,784 INFO L158 Benchmark]: RCFGBuilder took 487.73ms. Allocated memory is still 268.4MB. Free memory was 168.3MB in the beginning and 137.9MB in the end (delta: 30.4MB). Peak memory consumption was 30.4MB. Max. memory is 8.0GB. [2024-11-04 15:10:58,784 INFO L158 Benchmark]: TraceAbstraction took 70494.91ms. Allocated memory was 268.4MB in the beginning and 334.5MB in the end (delta: 66.1MB). Free memory was 137.3MB in the beginning and 274.6MB in the end (delta: -137.2MB). Peak memory consumption was 110.7MB. Max. memory is 8.0GB. [2024-11-04 15:10:58,785 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.09ms. Allocated memory is still 173.0MB. Free memory was 127.4MB in the beginning and 127.2MB in the end (delta: 147.3kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 1498.17ms. Allocated memory was 173.0MB in the beginning and 268.4MB in the end (delta: 95.4MB). Free memory was 112.3MB in the beginning and 179.3MB in the end (delta: -67.0MB). Peak memory consumption was 102.6MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 87.41ms. Allocated memory is still 268.4MB. Free memory was 179.3MB in the beginning and 173.5MB in the end (delta: 5.8MB). Peak memory consumption was 5.2MB. Max. memory is 8.0GB. * Boogie Preprocessor took 42.41ms. Allocated memory is still 268.4MB. Free memory was 173.5MB in the beginning and 168.3MB in the end (delta: 5.2MB). Peak memory consumption was 5.2MB. Max. memory is 8.0GB. * RCFGBuilder took 487.73ms. Allocated memory is still 268.4MB. Free memory was 168.3MB in the beginning and 137.9MB in the end (delta: 30.4MB). Peak memory consumption was 30.4MB. Max. memory is 8.0GB. * TraceAbstraction took 70494.91ms. Allocated memory was 268.4MB in the beginning and 334.5MB in the end (delta: 66.1MB). Free memory was 137.3MB in the beginning and 274.6MB in the end (delta: -137.2MB). Peak memory consumption was 110.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_rend_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_rend(&list) [L4824] 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); [L4824] RET, EXPR aws_linked_list_is_valid(list) VAL [list={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4824] 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] [L4824] 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] [L4825] const struct aws_linked_list_node *rval = &list->head; VAL [list={5:0}, rval={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4826] 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); [L4826] RET, EXPR aws_linked_list_is_valid(list) VAL [list={5:0}, rval={5:0}, s_can_fail_allocator_static={4:0}, tl_last_error=0] [L4826] 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: 70.4s, OverallIterations: 20, TraceHistogramMax: 6, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 45.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 9 mSolverCounterUnknown, 736 SdHoareTripleChecker+Valid, 42.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 665 mSDsluCounter, 8889 SdHoareTripleChecker+Invalid, 41.9s 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, 12.9s 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.2s AutomataMinimizationTime, 19 MinimizatonAttempts, 212 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.4s SsaConstructionTime, 0.8s SatisfiabilityAnalysisTime, 17.1s 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:10:58,829 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...